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:
> 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)
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk