Hacker News Reader

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.

View on HN

The 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

That's true. A 5 bits header before each number that specifies how many bits a number uses would be enough.

How are you encoding the deltas exactly?

Say the first number is 100, then the following one is 300, then 1000. You'd encode [100, 200, 700].

Reply on news.ycombinator.com