Re: master 792ba71: Add a new function 'buffer-line-statistics'

[Lars Ingebrigtsen]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> I must admit to not being fully cognizant of Knuth, but doesn't this
> compute the average rather than the mean?

Arithmetic mean, which is the meanest of the mean.

> 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's the median, and that's what I also thought, but it turns out that
you can approximate the median to the desired accuracy with much less
than O(N) space:

  https://www.stat.cmu.edu/~ryantibs/papers/median.pdf

Which we can consider if somebody wants it.  :-)

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no