On Sun, 23 Sep 2018 at 08:39, Zach Laine via Boost
On Sat, Sep 22, 2018 at 9:22 PM Lakshay Garg via Boost < boost@lists.boost.org> wrote:
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.
The reason for not using std::nth_element was because I wanted to be able to query the median at any point of the sequence very efficiently. Had I used std::nth_element, I would have needed O(n) time for obtaining the median. For a case where I need to compute median after every single element, this would have required O(n^2) time for a sequence of length n. Here is my implementation in case you would like to have a look: https://gist.github.com/lakshayg/d27f29b4634cbfea3fc48c21b7b608ef