Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Sorting 1M 8-digit numbers in 1 MB of RAM (2012)

stackoverflow.com

Post reply on HN
Print view View original

21–30 of 63 posts

Re: Sorting 1M 8-digit numbers in 1 MB of RAM (2012)

#21

Post by bogomipz »

raphlinus wrote: post #12

I'm a fan of the actual (in-RAM, no tricks) problem and its variants. The entropy of the sorted list is 0.96MiB so it is theoretically possible (see https://news.ycombinator.com/item?id=4679756 ), but I've not seen a good writeup of an actual algorithm. My personal favorite variant of this is sorting 1M 32-bit integers using 2MiB of RAM. This is possible and I coded it up for fun a few years ago. Here's the specific…

>"I'm a fan of the actual (in-RAM, no tricks) problem and its variants."

This particular problem as stated on S.O. aside do you consider disk-based sorting one of the tricks? I would be curious to hear some of the other tricks as well as variants of this problem space.

Re: Sorting 1M 8-digit numbers in 1 MB of RAM (2012)

#22

Post by throwaway744678 »

tetris11 wrote: post #18

Hang on, he decrements VALUE only by 1 during the sorting phase, which assumes that the 1M 8 digit numbers are consecutive, which we know they might not he because he said there could be duplicates....

After decreasing VALUE by 1, you should run T (T >> 10000000) times. If VALUE is not found in your stream, it is not transmitted. Similarly, you should always run T times, to account for all duplicates (you can't just 'break' when finding VALUE)

Re: Sorting 1M 8-digit numbers in 1 MB of RAM (2012)

#23

Post by vbezhenar »

gregschlom wrote: post #6
znpy wrote: post #2

I'd sort the input as it arrives, using heap sort. The thing is, you could just not worry about the stream, as it is TCP/IP based. The core idea is to read a number from the stream, append to the array that makes up the heap, and run heap sort. The only important thing is to keep the tcp/ip connection alive. If sorting takes too much, tcp will take care of sending the last sent number again. This might not be super e…

You can't because there's not enough RAM to hold all the numbers. So you'd be sorting the input as it arrives, yes, and then at some point you'd run out of RAM and have to stop processing new numbers.

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.

Re: Sorting 1M 8-digit numbers in 1 MB of RAM (2012)

#24

Post by raphlinus »

bogomipz wrote: post #21
raphlinus wrote: post #12

I'm a fan of the actual (in-RAM, no tricks) problem and its variants. The entropy of the sorted list is 0.96MiB so it is theoretically possible (see https://news.ycombinator.com/item?id=4679756 ), but I've not seen a good writeup of an actual algorithm. My personal favorite variant of this is sorting 1M 32-bit integers using 2MiB of RAM. This is possible and I coded it up for fun a few years ago. Here's the specific…

>"I'm a fan of the actual (in-RAM, no tricks) problem and its variants." This particular problem as stated on S.O. aside do you consider disk-based sorting one of the tricks? I would be curious to hear some of the other tricks as well as variants of this problem space.

I consider it not in-RAM.

There's another variant, iirc sorting telephone numbers, in "Programming Pearls," but it requires a different approach.

Re: Sorting 1M 8-digit numbers in 1 MB of RAM (2012)

#25

Post by mikepurvis »

raphlinus wrote: post #24
bogomipz wrote: post #21

Earlier quoted context omitted.

>"I'm a fan of the actual (in-RAM, no tricks) problem and its variants." This particular problem as stated on S.O. aside do you consider disk-based sorting one of the tricks? I would be curious to hear some of the other tricks as well as variants of this problem space.

I consider it not in-RAM. There's another variant, iirc sorting telephone numbers, in "Programming Pearls," but it requires a different approach.

The classic programming interview version of this question is to infer from "telephone numbers" that they're all unique and so you just allocate the provided memory as a big bitfield, mark all the numbers you have in your input list, then scan through and read them back in order.

Re: Sorting 1M 8-digit numbers in 1 MB of RAM (2012)

#26

Post by tomaszs »

Its easy. 1kk numbers fit almost whole 1MB. So most of the numbers from the range will be there if we assume normal distribution.

So we need to compress the data first in a way we can still count it. So we take a sinus function and mark multipliers where a number does not fit sinus. So we spare 0,5MB of RAM at least. Then we iterate the range, multiply sinus and output sorted numbers.

Rest of the RAM can be used for example for bitcoin mining

Re: Sorting 1M 8-digit numbers in 1 MB of RAM (2012)

#27

Post by jayd16 »

The accepted answer seems prone to losing data on dropped packets, no?

A similar (but I think safer) approach might be to read ahead all the packets to determine what values you can begin to send. Then you could request retransmission. This requires the sender to play nice and buffer all the data fore you but that seems more realistic than assuming the router will do so.

Re: Sorting 1M 8-digit numbers in 1 MB of RAM (2012)

#29

Post by YetAnotherNick »

taberiand wrote: post #7

The accepted solution is some wizardry that works because 1M (just) fits into 1MB... I wonder if in the intervening years 1M hasn't become 2M or more? I'm not really smart enough to come up with such a solution, I'd probably just try and find a way to plug something in between the input or output Ethernet port that has a bit more memory.

1M (ordered) list of numbers requires 3.5MB of RAM(10^6*log_2(10^8) bits). The theoretical lower bound to store unordered numbers is 0.96MB(log_2(comb(10^8+10^6-1, 10^6)) bits)
Post reply on HN