Find running median from a stream of integers
stackoverflow.com
Find running median from a stream of integers
1–10 of 29 posts
Re: Find running median from a stream of integers
#2Heap sounds like overkill to find the middle value in a running list. What's wrong with simple stack and keeping track of how many integers you've received?
Re: Find running median from a stream of integers
#3Heap sounds like overkill to find the middle value in a running list. What's wrong with simple stack and keeping track of how many integers you've received?
I'm not sure what you have in mind (perhaps finding the mean? but why the stack?) but that would not work for median.
Re: Find running median from a stream of integers
#4This is kind of a weird problem, because it requires you to keep all the numbers in memory, so the "streaming" aspect is a lot less useful. And then once you have the list in memory there are linear median finding algorithms. The only way out that I can see is if you expect the incoming data to follow a normal distribution you can short-circuit the entire problem and just calculate the mean.
EDIT: One could construct a "Counted B-Tree" which is a pretty straightforward augmentation of the B-Tree (quick google result: http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtre...). The insertion cost would still be of complexity log(n), the median could also be retrieved cheaply, and the data is kept sorted, but it takes more space.
Re: Find running median from a stream of integers
#5This is kind of a weird problem, because it requires you to keep all the numbers in memory, so the "streaming" aspect is a lot less useful. And then once you have the list in memory there are linear median finding algorithms. The only way out that I can see is if you expect the incoming data to follow a normal distribution you can short-circuit the entire problem and just calculate the mean. EDIT: One could construct…
Depending on the application, you could keep a limited number of samples in memory and "below" or "above" those samples would simply be a counter of how many samples fall into either range. This would only work for applications where you expected the median to only vary in a limited fashion, and only after the system had been "primed".
For example, at any point in time, only store 100-1000 samples in memory, tree'd into "greater than median" and "less than median", additionally in each side of the tree store the number of samples that are in that tree but were purged do to the samples in memory requirement. When each new sample comes in, balance the tree to find the median.
I think this would work as long as a the median didn't have drastic movements up or down e.g. 1000 samples in a row Even if you did expect wide variations you could use a similar approach but instead of purging samples into a counter you could serialize them to disk, or even have 3 layers, memory -> disk -> purge to counter.
EDIT: now that I think about this for more than 10 seconds, you may need to track the first derivative of median movement to determine how many samples to keep on a given side also.
Re: Find running median from a stream of integers
#6Here is a clever algorithm to find the median of a stream of integers by using just one variable:
The idea is to maintain a floating median. Start with an arbitrary number, say 0. If the incoming number is greater than the estimate, num += 1, else num -= 1.
It is easy to prove that for a large enough stream, assuming the stream is drawn from iid samples, this would converge to the median, by central limit theorem.
Using two variables instead of one, you could converge faster. So instead of incrementing/decrementing by one, you store how big your leap is, and have a schedule to change it.
Re: Find running median from a stream of integers
#7[deleted]
Re: Find running median from a stream of integers
#8Here is a clever algorithm to find the median of a stream of integers by using just one variable: The idea is to maintain a floating median. Start with an arbitrary number, say 0. If the incoming number is greater than the estimate, num += 1, else num -= 1. It is easy to prove that for a large enough stream, assuming the stream is drawn from iid samples, this would converge to the median, by central limit theorem. Us…
> It is easy to prove that...
Reminds me of a similar comment in the margin of a old book: http://en.wikipedia.org/wiki/Fermats_Last_Theorem. :)
But it does sound both plausible and brilliant. How do you prove it (in broad terms)?
Re: Find running median from a stream of integers
#9Heap sounds like overkill to find the middle value in a running list. What's wrong with simple stack and keeping track of how many integers you've received?
What's wrong with simple stack and keeping track of how many integers you've received?
I'm sorry, but I have absolutely no idea what you are talking about. Perhaps you could describe your solution a bit more.
Re: Find running median from a stream of integers
#10Here is a clever algorithm to find the median of a stream of integers by using just one variable: The idea is to maintain a floating median. Start with an arbitrary number, say 0. If the incoming number is greater than the estimate, num += 1, else num -= 1. It is easy to prove that for a large enough stream, assuming the stream is drawn from iid samples, this would converge to the median, by central limit theorem. Us…
> It is easy to prove that... Reminds me of a similar comment in the margin of a old book: http://en.wikipedia.org/wiki/Fermats_Last_Theorem . :) But it does sound both plausible and brilliant. How do you prove it (in broad terms)?
[deleted]