Re: [boost] Median in Boost.Accumulators

Subject: Re: [boost] Median in Boost.Accumulators
From: Lakshay Garg (lakshayg373_at_[hidden])
Date: 2018-09-23 19:44:27

On Sun, 23 Sep 2018 at 11:59, Zach Laine <whatwasthataddress_at_[hidden]> wrote:
>
> On Sun, Sep 23, 2018 at 10:59 AM Lakshay Garg <lakshayg373_at_[hidden]> wrote:
>>
>> On Sun, 23 Sep 2018 at 08:39, Zach Laine via Boost
>> <boost_at_[hidden]> 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)