4 ms·

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://new

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 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 encoding I used for the sorted list: A '0' bit followed by 12 bits of payload generates a number which is those 12 bits added to a global state counter. A '1' bit increments the global state counter by 2^12. It's easy to work out the memory requirements (it's constant for all sorted lists of the same length): 2^20 bits for the '1' bits (to reach a maximum value of 2^32) plus 10^6 * 13 bits for the integers. This is exactly 1,756,072 bytes, which leaves plenty of extra space. ETA: unfortunately a simple adaptation of this technique doesn't quite work for this problem; the optimum payload size for 1e6 integers up to 1e8 is 6 bits, but even with that the representation takes 1046kiB, and the budget is 1024kiB.

bogomipz 7y ago
>"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.
- raphlinus 7y ago
  I consider it not in-RAM. There's another variant, iirc sorting telephone numbers, in "Programming Pearls," but it requires a different approach.
  - mikepurvis 7y ago
    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.
    - bogomipz 7y ago
      Interesting is this a counting sort then? Might you or someone else have a link that states the whole interview question?
      - Noumenon72 7y ago
        Seconded, I googled bitfields and Stack Overflow and still don't understand the OP even a little.
        efreak 7y ago
        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.
      - mikepurvis 7y ago
        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-labs.com/cm/cs/pearls/cto.html http://web.archive.org/web/20071012005100/http://www.cs.bell...
      - dntbnmpls 7y ago
        > Interesting is this a counting sort then? Not really as all the input values are unique. So counting wouldn't do any good. It's basically using a bitfield long enough to encompass all possible values and then switching the bit of the input value. As an example, if you are dealing with 3 digit numbers, then the max possible value is 999 and the min possible is 0. So you need a bitfield that is 1000 bits long. And if your input values are 999, 2, 123 and 7. Then you set the 999th bit, 2nd bit, 123rd bit and the 7th bit. Now when you read the bitfield from the 0th bit to the 999th bit, you will find 4 set bits - the 2nd bit, the 7th bit, the 123rd bit and the 999th bit. So instead of viewing them as ordinal numbers but cardinal numbers, we get 2, 7, 123 and 999 which is sorted. Another way to view it is as setting the positions in an array. Instead of bits, lets say you have an array of 1000 ints all initialized to 0. Lets call this array MyBitArray. And if your input values are 999, 2, 123 and 7 then MyBitArray[999] = 1; MyBitArray[2] = 1; MyBitArray[123] = 1; MyBitArray[7] = 1; Now if you pass through the array in order and check for the indices with the value set to 1, you'll see that indexes 2, 7, 123 and 999 are set to 1 which incidentally gives you your sorted list. The difference between the array example and the bit example is that the bit example is much more space efficient. But the overall idea is the same.
ampdepolymerase 7y ago
Why is the entropy of the sorted list smaller?
- Koshkin 7y ago
  Because it's easier to compress (compared to when its contents is in a random order).
- btilly 7y ago
  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.
- YetAnotherNick 7y ago
  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.
adito 7y ago
> 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. Is it possible for you to share the code? Still don't quite get how that encoding related/helps in sorting the numbers.
contravariant 7y ago
>The entropy of the sorted list is 0.96MiB so it is theoretically possible (see https://news.ycombinator.com/item?id=4679756 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).
yread 7y ago
Interesting, sort of bucket sort using a linked list if I understand correctly. How do you determine the optimal number of bits - 12 for 32bit and 6 for 1e8 = 30bit?
aasasd 7y ago
I think the second solution from SO is almost the same as yours, including having begun with Golomb coding: http://preshing.com/20121026/1mb-sorting-explained http://preshing.com/20121026/1mb-sorting-explained However, they explain that Golomb coding isn't quite enough for the 1M case and switch to arithmetic coding instead.
- contravariant 7y ago
  Ah seems I was a bit too optimistic with my estimation of the number of bits. Shame, that means a simple solution is pretty much impossible.

bogomipz 7y ago

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

raphlinus 7y ago
I consider it not in-RAM. There's another variant, iirc sorting telephone numbers, in "Programming Pearls," but it requires a different approach.
- mikepurvis 7y ago
  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.
  - bogomipz 7y ago
    Interesting is this a counting sort then? Might you or someone else have a link that states the whole interview question?
    - Noumenon72 7y ago
      Seconded, I googled bitfields and Stack Overflow and still don't understand the OP even a little.
      - efreak 7y ago
        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.
    - mikepurvis 7y ago
      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-labs.com/cm/cs/pearls/cto.html http://web.archive.org/web/20071012005100/http://www.cs.bell...
    - dntbnmpls 7y ago
      > Interesting is this a counting sort then? Not really as all the input values are unique. So counting wouldn't do any good. It's basically using a bitfield long enough to encompass all possible values and then switching the bit of the input value. As an example, if you are dealing with 3 digit numbers, then the max possible value is 999 and the min possible is 0. So you need a bitfield that is 1000 bits long. And if your input values are 999, 2, 123 and 7. Then you set the 999th bit, 2nd bit, 123rd bit and the 7th bit. Now when you read the bitfield from the 0th bit to the 999th bit, you will find 4 set bits - the 2nd bit, the 7th bit, the 123rd bit and the 999th bit. So instead of viewing them as ordinal numbers but cardinal numbers, we get 2, 7, 123 and 999 which is sorted. Another way to view it is as setting the positions in an array. Instead of bits, lets say you have an array of 1000 ints all initialized to 0. Lets call this array MyBitArray. And if your input values are 999, 2, 123 and 7 then MyBitArray[999] = 1; MyBitArray[2] = 1; MyBitArray[123] = 1; MyBitArray[7] = 1; Now if you pass through the array in order and check for the indices with the value set to 1, you'll see that indexes 2, 7, 123 and 999 are set to 1 which incidentally gives you your sorted list. The difference between the array example and the bit example is that the bit example is much more space efficient. But the overall idea is the same.

ampdepolymerase 7y ago

Why is the entropy of the sorted list smaller?

Koshkin 7y ago
Because it's easier to compress (compared to when its contents is in a random order).
btilly 7y ago
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.
YetAnotherNick 7y ago
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.

adito 7y ago

> 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. Is it possible for you to share the code? Still don't quite get how that encoding related/helps in sorting the numbers.

contravariant 7y ago

>The entropy of the sorted list is 0.96MiB so it is theoretically possible (see https://news.ycombinator.com/item?id=4679756 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).

yread 7y ago

Interesting, sort of bucket sort using a linked list if I understand correctly. How do you determine the optimal number of bits - 12 for 32bit and 6 for 1e8 = 30bit?

aasasd 7y ago

I think the second solution from SO is almost the same as yours, including having begun with Golomb coding: http://preshing.com/20121026/1mb-sorting-explained http://preshing.com/20121026/1mb-sorting-explained However, they explain that Golomb coding isn't quite enough for the 1M case and switch to arithmetic coding instead.

contravariant 7y ago
Ah seems I was a bit too optimistic with my estimation of the number of bits. Shame, that means a simple solution is pretty much impossible.