On Sat, Sep 22, 2018 at 9:22 PM Lakshay Garg via Boost < boost@lists.boost.org> 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