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