Re: [boost] Median in Boost.Accumulators

On Sun, 23 Sep 2018 at 11:59, Zach Laine wrote:

On Sun, Sep 23, 2018 at 10:59 AM Lakshay Garg wrote:

...

On Sun, 23 Sep 2018 at 08:39, Zach Laine via Boost wrote:

...

Could you compare and contrast this with the standard library's way of computing a median, std::nth_element()? Yout just give it N/2 for 'n', and it computes the median.

The reason for not using std::nth_element was because I wanted to be able to query the median at any point of the sequence very efficiently. Had I used std::nth_element, I would have needed O(n) time for obtaining the median. For a case where I need to compute median after every single element, this would have required O(n^2) time for a sequence of length n. Here is my implementation in case you would like to have a look:

https://gist.github.com/lakshayg/d27f29b4634cbfea3fc48c21b7b608ef

I missed that the first time, thanks.

Your implementation does not seem to support a windowed working set (one element at a time is added and the oldest one removed). Is that right?

Yes, that is correct. This approach does not support a window.

Also, what if I don't actually call get() very often?

If get() is not called very often, then I guess just using a plain vector and calling nth_element on it would be the best approach.

Is there any way to take advantage of make_heap()'s O(n) characteristics, and avoid doing an O(n) push_heap() n times? I can't think of one offhand, just curious.

The complexity of push_heap is actually O(log(n)) and not O(n)