Re: [boost] Median in Boost.Accumulators

Subject: Re: [boost] Median in Boost.Accumulators
From: Lakshay Garg (lakshayg373_at_[hidden])
Date: 2018-09-23 15:58:24

On Sun, 23 Sep 2018 at 08:39, Zach Laine via Boost
<boost_at_[hidden]> wrote:
>
> On Sat, Sep 22, 2018 at 9:22 PM Lakshay Garg via Boost <
> boost_at_[hidden]> wrote:
>
> > I rolled up my custom implementation of the algorithm and
> > used it for my project. I wanted to check if people on
> > this list might be interested in such an implementation
> > for Boost.Accumulators in which case I can try to adapt my
> > implementation and send a PR.
> >
> > Performance characteristics: For a stream of n numbers, the
> > memory required is O(n). Median can be queried at any point
> > of time in O(1) and adding all the elements costs O(nlog(n))
> >
>
> 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