Re:Sorting 1 million 8-digit decimal numbers in 1MB of RAM
by teeja on Sunday October 21, 2012 @03:09PM
(#4680471)
Compressed bucket-ranges works fine for random date, but if the data are skewed in some way (e.g. normal-curve shaped), the bucket-sizes must be adjustable.
An alternative method is to use one bucket into which all values below a limit (e.g. 20,000,000) are sorted as they arrive, and compress all the rest. When 10^6 values have arrived, transmit the bucket and then reuse the empty bucket repeatedly to sort the compressed values.
An alternative method is to use one bucket into which all values below a limit (e.g. 20,000,000) are sorted as they arrive, and compress all the rest. When 10^6 values have arrived, transmit the bucket and then reuse the empty bucket repeatedly to sort the compressed values.