[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Stefan Monnier
Subject: Re: master 792ba71: Add a new function 'buffer-line-statistics'
Date: Tue, 12 Jan 2021 14:54:23 -0500
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/28.0.50 (gnu/linux)

>>   https://www.stat.cmu.edu/~ryantibs/papers/median.pdf
> I used this one:
>   https://www.cse.wustl.edu/~jain/papers/ftp/psqr.pdf


FWIW, last time I needed a fast approximation of the median was in the
`src/profiler.c` code, and I just used the approach you can see in
`approximate_median` (basically, the approximate median I used is the
median of 3 (recursive) approximate medians).

So, it's O(N) worst case time complexity and O(log N) worst case
(stack) space complexity.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]