Hacker News Reader

Comment by raphlinus | Hacker News Reader

This is quite related to the problem of sorting a million 32 bit integers using only 2M of RAM (and no disk). It can be done.

View on HN

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.

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].

So what is the trick?

It's the opening problem from Programming Pearls: http://www.fusu.us/2013/06/bitmap-sort.html

(edit: better link)

How is this relevant? A bitmap of size 2^32 is 512MB in size and you only have 2MB of memory.

The trick is that you only need to store the unordered list of seen integers as your state while you sort. This takes about 1.5MB or so. The reduction in space comes from the fact that you don't have to store the order (for example, you could store the numbers sorted and only record offsets. That saves space because the offsets will be smaller)

If I only have 8 bytes of ram and a program counter I can do it...

For (I=0; I<1<<31; I++) For (J=0; J<1e6; J++) If (input[J]==I) print(I);

Shoddy runtime, but hey...

Yes, this is a problem that requires careful specification. You only get streaming access to your input, not random.

Couldn't you just do that with radix sort or am I missing something?

Yes, you're missing something. Radix sort, like most sorting algorithms, requires storing the intermediate results in memory. This problem seems impossible at first blush because storing 1 million 4-byte integers would seem to require 4M of RAM, and only 2M is available.

But if I pick my buckets right, I can store only the lsb in each bucket.

Or more efficient, dynamically construct an implicit trie/heap type thing, where each leaf is the count of times that int appears (and the int itself is encoded in the location)

That feels really, really handwavy but promising?

You're sort of on the right track, but of course you have to encode those counts very carefully because 1M counts will exceed 2MB of memory unless you work hard.

Right, you can't store them as ints. 1 million bits is the max you need, but like this whole thing is just super tricky because you can't just address things normally anywhere, since that's too big.

So I'm allowed to read/write only once to the backing media?

You're right, that does sound impossible. :O

Only if all your ints are unique I guess?

No, that's not a requirement, as it turns out, though of course it would decrease the entropy even further.

Sure, just pick a sorting algorithm that uses constant memory and the optimal O(n lg n) time complexity:

https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_o...

These need random access to use constant memory, he was talking about streaming access

Yeah, I didn't pay attention that you can't really store 1 million 32 bit integers in 2MiB without encoding/compressing them somehow.

Reply on news.ycombinator.com