3 ms·
Since 10^12 is way way bigger than a 2^32, it's either the average of the numbers, or a strange degenerate case. (10^11 1's followed by 10^11 3s). just calcula
by jfoutz 17y ago
Since 10^12 is way way bigger than a 2^32, it's either the average of the numbers, or a strange degenerate case. (10^11 1's followed by 10^11 3s).
just calculate the average, and remember the item closest to the current average.
- roundsquare 17y agoEh? Thats not true. The only time this would work is if the distribution of the numbers was symmetric (or close to symmetric). If you have 1 --> 599,999,999,999 times 4 --> 1 time 10 --> 400,000,000,000 times Your average will be about 4.6 (a little higher) and your algorithm will return 4 as the answer when it should be 1.
- jfoutz 17y agoYeah, I commented right before bed. I thought of a bunch of problems with the average while trying to get to sleep. I was thinking since the size of an outlier is constrained by fitting in 4 bytes, there must be a way to show the median is in some band of numbers around the average. I didn't think of a particularly useful algorithm though. Thanks.
- eru 17y agoCalculating the average is in O(n). Calculating the median is in O(n).
- roundsquare 17y agoActually, even be worse here. E.g. if all the numbers are positive you will get an overflow pretty quick, so you'll need a better datatype. So if you are dealing with b-bit numbers you'd need O(n * log(bn)) to calculate the average. (Usually this doesn't matter, but since n >> b it does). Edit: Notwithstanding my earlier comment that average doesn't work, merely commenting on the run time of average.
- bravura 17y agoOr, you could compute the average as follows: m <-- m - (1/t) (m - x_t) This will compute the exact historical average. I like to use 2/t instead of 1/t to get a moving average over a non-stationary distribution, which favors the more recent events.
- deleted 17y ago[deleted]
- eru 17y agoPlease keep numerical errors in mind. They accumulate.