23 Sep
2018
23 Sep
'18
2:29 p.m.
On 09/23/18 04:21, Lakshay Garg via Boost 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.
Boost.Accumulators does not seem to be actively maintained.
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))
Sounds like you keep two ordered lists (e.g. std::set) of equal size. Then the median is the first element in the second list.