Apologies for the off-topic post, but I know lots of people here are
interested in statistics and algorithms.
Calculating the mean of a stream of numbers [1] is easy: just keep track
of the sum and the count, and divide at the end. But what about the
median? I think I always need to buffer at
On 8/16/07, Darren Cook [EMAIL PROTECTED] wrote:
Apologies for the off-topic post, but I know lots of people here are
interested in statistics and algorithms.
Calculating the mean of a stream of numbers [1] is easy: just keep track
of the sum and the count, and divide at the end. But what
On 8/16/07, Darren Cook [EMAIL PROTECTED] wrote:
Calculating the mean of a stream of numbers [1] is easy: just keep track
of the sum and the count, and divide at the end. But what about the
median?
I think I always need to buffer at least half the numbers
A counter for each unique value
You can use a binary tree. In each node you store the number
of child nodes in the left subtree. (maybe also for the right subtree)
If you want to handle duplicates, you could add yet another counter to the
nodes.
Finding the median is easy. As a bonus, you can also find the value
for *any* rank
