Re: [boost] Median in Boost.Accumulators

Subject: Re: [boost] Median in Boost.Accumulators
From: Zach Laine (whatwasthataddress_at_[hidden])
Date: 2018-09-23 15:39:19

On Sat, Sep 22, 2018 at 9:22 PM Lakshay Garg via Boost <
boost_at_[hidden]> wrote:

> Hello Boost
>
> Some time ago, I needed to compute the exact median for
> a stream of elements and after using Boost.Accumulators,
> realized that it only provides an approximation of the
> median and not the exact number.
>
> 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.

Zach