From mboxrd@z Thu Jan  1 00:00:00 1970
Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail
From: Eli Zaretskii <eliz@gnu.org>
Newsgroups: gmane.emacs.devel
Subject: Re: master 792ba71: Add a new function 'buffer-line-statistics'
Date: Tue, 12 Jan 2021 20:43:35 +0200
Message-ID: <83h7nmc7xk.fsf@gnu.org>
References: <20210112174748.18372.29339@vcs0.savannah.gnu.org>
 <20210112174750.5928220B2C@vcs0.savannah.gnu.org>
 <jwveeiq2ffk.fsf-monnier+emacs@gnu.org> <83mtxec87u.fsf@gnu.org>
Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214";
	logging-data="5535"; mail-complaints-to="usenet@ciao.gmane.io"
Cc: larsi@gnus.org, emacs-devel@gnu.org
To: monnier@iro.umontreal.ca
Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Tue Jan 12 19:46:29 2021
Return-path: <emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org>
Envelope-to: ged-emacs-devel@m.gmane-mx.org
Original-Received: from lists.gnu.org ([209.51.188.17])
	by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
	(Exim 4.92)
	(envelope-from <emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org>)
	id 1kzOgX-0001J0-CO
	for ged-emacs-devel@m.gmane-mx.org; Tue, 12 Jan 2021 19:46:29 +0100
Original-Received: from localhost ([::1]:46430 helo=lists1p.gnu.org)
	by lists.gnu.org with esmtp (Exim 4.90_1)
	(envelope-from <emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org>)
	id 1kzOgW-00038w-AE
	for ged-emacs-devel@m.gmane-mx.org; Tue, 12 Jan 2021 13:46:28 -0500
Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:57094)
 by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
 (Exim 4.90_1) (envelope-from <eliz@gnu.org>) id 1kzOda-0000RH-UI
 for emacs-devel@gnu.org; Tue, 12 Jan 2021 13:43:32 -0500
Original-Received: from fencepost.gnu.org ([2001:470:142:3::e]:37708)
 by eggs.gnu.org with esmtp (Exim 4.90_1)
 (envelope-from <eliz@gnu.org>)
 id 1kzOdY-0001Ae-OB; Tue, 12 Jan 2021 13:43:26 -0500
Original-Received: from 84.94.185.95.cable.012.net.il ([84.94.185.95]:3758
 helo=home-c4e4a596f7)
 by fencepost.gnu.org with esmtpsa (TLS1.2:RSA_AES_256_CBC_SHA1:256)
 (Exim 4.82) (envelope-from <eliz@gnu.org>)
 id 1kzOdW-0004RK-CQ; Tue, 12 Jan 2021 13:43:24 -0500
In-Reply-To: <83mtxec87u.fsf@gnu.org> (message from Eli Zaretskii on Tue, 12
 Jan 2021 20:37:25 +0200)
X-BeenThere: emacs-devel@gnu.org
X-Mailman-Version: 2.1.23
Precedence: list
List-Id: "Emacs development discussions." <emacs-devel.gnu.org>
List-Unsubscribe: <https://lists.gnu.org/mailman/options/emacs-devel>,
 <mailto:emacs-devel-request@gnu.org?subject=unsubscribe>
List-Archive: <https://lists.gnu.org/archive/html/emacs-devel>
List-Post: <mailto:emacs-devel@gnu.org>
List-Help: <mailto:emacs-devel-request@gnu.org?subject=help>
List-Subscribe: <https://lists.gnu.org/mailman/listinfo/emacs-devel>,
 <mailto:emacs-devel-request@gnu.org?subject=subscribe>
Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org
Original-Sender: "Emacs-devel"
 <emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org>
Xref: news.gmane.io gmane.emacs.devel:263019
Archived-At: <http://permalink.gmane.org/gmane.emacs.devel/263019>

> Date: Tue, 12 Jan 2021 20:37:25 +0200
> From: Eli Zaretskii <eliz@gnu.org>
> Cc: larsi@gnus.org, emacs-devel@gnu.org
> 
> > From: Stefan Monnier <monnier@iro.umontreal.ca>
> > Date: Tue, 12 Jan 2021 13:15:25 -0500
> > Cc: Lars Ingebrigtsen <larsi@gnus.org>
> > 
> > I thought computing the mean was necessarily O(N) in space (like
> > keeping the full sequence of line lengths so you can sort it and then
> > pick the middle point).
> 
> That the median, not the mean.  "Mean" and "average" are identical.

Btw, there are algorithms for true sequential estimation of the
median, without keeping all the samples in memory.  But they are
somewhat complex, and I'm not sure this case justifies such
complexity, as we shouldn't care in this case about the lack of
robustness of the average as a statistic.