[computer-go] OT: median of a data stream

[Darren Cook]

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 least half the numbers, but
does anyone know for sure, or know a clever algorithm [2]?

Darren

[1]: In a desperate attempt at on-topic-ness lets pretend they are
thinking times for each move in all games in a large go game collection.

[2]: If I know the number of distinct numbers is relatively small I can
make the histogram and derive the median that way. E.g. 100 distinct
numbers means I just need 100 counters. I also get the mode as a bonus.

-- 
Darren Cook
http://dcook.org/mlsn/ (English-Japanese-German-Chinese free dictionary)
http://dcook.org/work/ (About me and my work)
http://dcook.org/work/charts/  (My flash charting demos)