3 ms·
There's enough RAM to hold all the numbers. You just have to invent the representation to store all the numbers in the available RAM. Naive representation using
by vbezhenar 7y ago
There's enough RAM to hold all the numbers. You just have to invent the representation to store all the numbers in the available RAM. Naive representation using 27 bits per number won't hold them all indeed. But if you would store them ordered and store difference rather than number using variable bit encoding, it would take less space.
Just simple math: imagine that you have to store numbers 0, 100, 200, ..., 99 999 900 as a worst case scenario. As you're going to store the differences, you'll need to store "0" and then "100" 999999 times. If you would be able to represent "100" with 8 bits, you'll be able to keep your data inside 1 MiB limit. One simple encoding: 1xxxxxx for 7 bits; 01xxxxxxxx for 8 bits; 001xxxxxxxxx for 9 bits, etc. It should be enough for this task, although you could invent better encodings.
- ecpottinger 7y agoThat my idea too. It is very unlikely that the numbers are spread apart enough that you can't store the deltas in compact forms. Example starting your base as zero if the first number 100 you can store that in 1 byte, use the high bit to flag a larger number so if the next number is say 10000 you can store it in two bytes. But let's say the next number is 3000, you need to update the first delta, insert the new number and continue on. You probably can store most numbers that way.