3 ms·
With 10^6 random numbers between 0 and 10^8 almost all operations will be splits, and you'll end up with 8 bytes * 10^6 = 7.6 megabytes. So indeed the chances o
by jules 14y ago
With 10^6 random numbers between 0 and 10^8 almost all operations will be splits, and you'll end up with 8 bytes * 10^6 = 7.6 megabytes. So indeed the chances of this working for a random sequence are extremely slim. You have to have a huge number of coalesces, which is just extremely unlikely when you choose 10^6 random numbers in a range of 10^8. So for almost all inputs this method doesn't work.
I simulated it with a Python program and you get about 10^4 coalesces. That doesn't even begin to make a dent in 10^6, and storing this will still take ~7 megabytes.
- uvdiv 14y agoWith 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.