3 ms·
A list of deltas should do it. In the worst case, the deltas would use log2[2^32/1000000] * 1000000 bits, so about 1.5 MB. Plus some space because of base 128 e
by Matheus28 9y ago
A list of deltas should do it. In the worst case, the deltas would use log2[2^32/1000000] * 1000000 bits, so about 1.5 MB. Plus some space because of base 128 encoding (it increases size up to 37/32, rounded up per byte).
I got a worst case of exactly 2 MB (1.907 MiB) (all deltas being 4294, so the list is 0, 4294, 8588...), but maybe it's possible to get better than that.
It would be uber slow though, probably n^2.
- sirclueless 9y agoHow are you encoding the deltas exactly?
- Matheus28 9y agoSay the first number is 100, then the following one is 300, then 1000. You'd encode [100, 200, 700].
- lalaland1125 9y agoThe idea is good, but base128 won't work. The worst case scenario is around 250k offsets of 2^14 (requiring 3 bytes each) and 750k offsets of 2^7 (requiring 2 bytes each). That's 2.25 MB
- Matheus28 9y agoThat's true. A 5 bits header before each number that specifies how many bits a number uses would be enough.