4 ms·
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.
by raphlinus 9y ago
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.
- 6nf 9y agoOnly if all your ints are unique I guess?
- raphlinus 9y agoNo, that's not a requirement, as it turns out, though of course it would decrease the entropy even further.
- londons_explore 9y agoIf 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...
- raphlinus 9y agoYes, this is a problem that requires careful specification. You only get streaming access to your input, not random.
- andromeduck 9y agoCouldn't you just do that with radix sort or am I missing something?
- raphlinus 9y agoYes, 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.
- joshuamorton 9y agoBut 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?
- sirclueless 9y agoYou'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.
- joshuamorton 9y agoRight, 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.
- andromeduck 9y agoSo I'm allowed to read/write only once to the backing media? You're right, that does sound impossible. :O
- Franciscouzo 9y agoSure, 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_of_algorithms https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_o...
- Matheus28 9y agoThese need random access to use constant memory, he was talking about streaming access
- Franciscouzo 9y agoYeah, I didn't pay attention that you can't really store 1 million 32 bit integers in 2MiB without encoding/compressing them somehow.
- twouhm 9y agoSo what is the trick?
- lalaland1125 9y agoThe 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)
- _wmd 9y agoIt's the opening problem from Programming Pearls: http://www.fusu.us/2013/06/bitmap-sort.html http://www.fusu.us/2013/06/bitmap-sort.html (edit: better link)
- sirclueless 9y agoHow is this relevant? A bitmap of size 2^32 is 512MB in size and you only have 2MB of memory.
- Matheus28 9y agoA 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.
- deleted 9y ago[deleted]