2 ms·
With 10^6 random numbers between 0 and 10^8 almost all operations will be splits, Right. and you'll end up with 8 bytes x 10^6 = 7.6 megabytes. Not if you en
by uvdiv 14y ago
With 10^6 random numbers between 0 and 10^8 almost all operations will be splits,
Right.
and you'll end up with 8 bytes x 10^6 = 7.6 megabytes.
Not if you encode cleverly. The successive differences will be on the scale of 10^8/10^6 = 100, which is a very small number. It takes 7 bits to store, or at least 8 bits in a variable-width encoding.
- jules 14y agoSure, if you encode cleverly. That is the essential difficulty of the problem which he glosses over (note that he explicitly says that he will store the differences as 4 byte numbers). Getting it under 1.5MB (or even 1.1MB) is probably easy, but I have yet to see an encoding which is sufficiently compact to fit in 1MB.