[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: master 792ba71: Add a new function 'buffer-line-statistics'
From: |
Lars Ingebrigtsen |
Subject: |
Re: master 792ba71: Add a new function 'buffer-line-statistics' |
Date: |
Tue, 12 Jan 2021 19:39:54 +0100 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/28.0.50 (gnu/linux) |
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