Boost logo

Boost :

Subject: Re: [boost] Median in Boost.Accumulators
From: Lakshay Garg (lakshayg373_at_[hidden])
Date: 2018-09-23 20:03:57


On Sat, 22 Sep 2018 at 19:21, Lakshay Garg <lakshayg373_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))
>

I looked up the problem of computing median of a stream on SO
and found a few more approaches which are efficient in a rolling
window scenario.

https://stackoverflow.com/questions/10657503/find-running-median-from-a-stream-of-integers

I can try and implement one of those if we decide to have this
in the accumulators library.


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk