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 <
> 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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk