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

41–50 of 63 posts

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

#41

Post by btilly »

ampdepolymerase wrote: post #35
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…

Why is the entropy of the sorted list smaller?

The entropy of a signal is the logarithm base 2 of the number of signals that you could possibly be trying to send. Because with perfect compression, that is how many bits you need to encode that many different signals.

Since not all lists are sorted, there are more lists of a given size than sorted lists.

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

#43

Post by mikepurvis »

bogomipz wrote: post #36
mikepurvis wrote: post #25

Earlier quoted context omitted.

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.

Interesting is this a counting sort then? Might you or someone else have a link that states the whole interview question?

The original Pearls page seems to have been taken down, but the web archive remembers it:

http://web.archive.org/web/20071012005100/http://www.cs.bell...

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

#45

Post by hyperman1 »

MrStonedOne wrote: post #3

A more practical version of that same solution would be to use some serverless endpoint to do the sorting (or even just the storing).

OK, since we're now in evil question territory: How long should the wire to the router be to store everything? Assuming no buffer in the router and gygabit ethernet.

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

#46

Post by efreak »

Noumenon72 wrote: post #40
bogomipz wrote: post #36

Earlier quoted context omitted.

Interesting is this a counting sort then? Might you or someone else have a link that states the whole interview question?

Seconded, I googled bitfields and Stack Overflow and still don't understand the OP even a little.

For sorting 3,5,8,2,7: you take 0000000000, representing all 10 single digit numbers (0-9), and encode the given numbers into it as 0011010110. Now you just read out each one in order: 2,3,5,7,8. No need to store the actual numbers themselves.

It's possible that I'm getting this wrong, but this is my understanding of it.

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

#47

Post by YetAnotherNick »

dan-robertson wrote: post #33
YetAnotherNick wrote: post #29

Earlier quoted context omitted.

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)

I think your calculation for ordered lists is just wrong. I think the right answer should be about 3.17MB, not 3.5.

Someone wrote 3.5MB, didn't bother to double check but the formula is correct.

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

#48

Post by YetAnotherNick »

ampdepolymerase wrote: post #35
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…

Why is the entropy of the sorted list smaller?

1M (ordered) list of numbers < 10^8 requires 3.16MB 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. Basically calculating number of different possible types of lists, taking its log is the entropy. Both the lists [1, 2] and [2, 1] are same if we don't want the ordering information. In the second case we just need counts of number with property that count[0] + count[1]+...+count[10^8] = 10^6 as counts give perfect information for the sorted list.

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

#50

Post by contravariant »

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…

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

I reckon the easiest way to actually achieve that bound is to use the combinatoric number system. I've seen people refer to arithmetic encoding but I'm not too sure on the exact details, they're probably encoding the gaps between numbers but then there'll be some loss as those aren't IID, using the exponential distribution does seem to get you below the bound though, even if it is extremely annoying to implement.

For the combinatorial number system you basically need to sum (10^100 + 10^6 choose x + k) for all numbers x where k is the position of x in the (sorted) list. This would have been many times easier if you didn't need to take possible repeated values into account, but it is what it is.

If I'm honest both are complicated enough that I worry they'll be nigh impossible to implement without accidentally using 2MB of RAM.

Edit: Actually, just use Golomb-Rice codes for the gaps, if you pick the parameters right you'll need [d/128]+7 bits (rounded to the nearest integer) for a gap of size d, which is good enough. Since every gap uses a whole number of bits you'll just need to update and insert a few bits to update, rather than basically rewriting the whole thing (although you'll still need to shift the entire tail by a few bits).

Post reply on HN