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

[hidden email]> wrote:

>

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

[hidden email]> wrote:

>>

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

>> <

[hidden email]> 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)

_______________________________________________

Unsubscribe & other changes:

http://lists.boost.org/mailman/listinfo.cgi/boost