3 ms·

i think that's the clearest answer i've seen. really, it's pretty much equivalent to the other answers, but at least for me it's by far the easiest to grasp.

i think that's the clearest answer i've seen. really, it's pretty much equivalent to the other answers, but at least for me it's by far the easiest to grasp. although i guess that may be because the idea is simply becoming familiar after reading the others. the best "high level" explanation, i think, is that you are compressing the sorted numbers, which are therefore not random, and so concerns about the incompressibility of random streams are completely irrelevant.

mlvljr 14y ago
Or, rather, this is about compressing random sets == compressing random arrays with w/o being order precise. Is the number of all possible distinct sets of 1 million 1..10^8 numbers less or equal to 2^(8 * 1024 * 1024)? And if yes, is there a way to transform the buffer from one intermediate state (representing the "not yet fully" received stream) into another utilizing a small amount of registers?