This problem 20 yrs ago might be worth attempting to solve. Not sure it is worth the complexity and effort. Having said that the thinking & creativity could be reused. Not sure it is a complexity that we solve every day.
Sorting 1M 8-digit numbers in 1 MB of RAM (2012)
11–20 of 63 posts
Re: Sorting 1M 8-digit numbers in 1 MB of RAM (2012)
#12I'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 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.
Re: Sorting 1M 8-digit numbers in 1 MB of RAM (2012)
#13just do an external merge sort https://en.wikipedia.org/wiki/External_sorting#External_merg...
That assumes external storage, which is not given in the problem statement.
Re: Sorting 1M 8-digit numbers in 1 MB of RAM (2012)
#14This problem 20 yrs ago might be worth attempting to solve. Not sure it is worth the complexity and effort. Having said that the thinking & creativity could be reused. Not sure it is a complexity that we solve every day.
But there are for instance modern embedded systems which might be very resource constrained and knowledge like this would be useful there.
Re: Sorting 1M 8-digit numbers in 1 MB of RAM (2012)
#15This problem 20 yrs ago might be worth attempting to solve. Not sure it is worth the complexity and effort. Having said that the thinking & creativity could be reused. Not sure it is a complexity that we solve every day.
Compact / succinct data structures and clever algorithms are still very important when data gets large enough -- consider e.g. a database running complex queries, where a good encoding makes the difference between staying in memory and going to disk. Basically the machines became larger but so have the problems to solve.
Re: Sorting 1M 8-digit numbers in 1 MB of RAM (2012)
#16This problem 20 yrs ago might be worth attempting to solve. Not sure it is worth the complexity and effort. Having said that the thinking & creativity could be reused. Not sure it is a complexity that we solve every day.
Compact / succinct data structures and clever algorithms are still very important when data gets large enough -- consider e.g. a database running complex queries, where a good encoding makes the difference between staying in memory and going to disk. Basically the machines became larger but so have the problems to solve.
Yes but this is far beyond compact, it's squeezing in so close to the edge of what fits that the performance inevitably drops off a cliff.
Re: Sorting 1M 8-digit numbers in 1 MB of RAM (2012)
#17I'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.
[deleted]
Re: Sorting 1M 8-digit numbers in 1 MB of RAM (2012)
#18Hang 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....
Re: Sorting 1M 8-digit numbers in 1 MB of RAM (2012)
#19This is basically an ICMP-based version of sleep sort: https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort
They're both similar and very clever, but they do operate differently. Sleep sort works by setting up a delay and callback based on the values that you are sorting, so timing is crucial. The solution in this topic is using the network as a queue to store values and is constantly throwing them back, only pulling them into the sorted stack when they reach the max threshold. Once an item is pulled down, its value is recorded and isn't echoed out again. The process is repeated until the list is complete. This works without regard to timing.
Re: Sorting 1M 8-digit numbers in 1 MB of RAM (2012)
#20This is basically an ICMP-based version of sleep sort: https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort
"Once COUNTER reaches 1000000, you have all of the values stored in the incessant stream of ICMP requests"
This sounds to me like...