Boost logo

Boost :

Subject: [boost] Median in Boost.Accumulators
From: Lakshay Garg (lakshayg373_at_[hidden])
Date: 2018-09-23 02:21:16


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))

Lakshay


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