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.