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

[dhillismail at netscape.net]

> [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.
> 

???? If you anticipate a relatively small number of distinct values but don't know how many or the range, you can store the histogram in a hash table. If you use a dynamically resizable hash table (like in C#) , then you may see a savings when your guess is right but won't drop information on the floor when it isn't.

>?I also get the mode as a bonus.

???? And the standard deviation as well.

???? If you were certain that the median itself had to lie within a small range of values, then you could maintain a binary counter for each of those possible values. If the values were floats, you could use a reasonable quantization and interpolate at the end.

- Dave Hillis

________________________________________________________________________
Check Out the new free AIM(R) Mail -- Unlimited storage and industry-leading spam and email virus protection.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://computer-go.org/pipermail/computer-go/attachments/20070816/315a16c2/attachment.htm