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

1–10 of 63 posts

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

#2

Post by znpy »

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

This could also be done in batches (4kb? 8kb?) -- we don't know about network speed or latencies, so we might work on that.

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

#5

Post by pixelmonkey »

This question is not the same as -- but has a similar feel to -- the first programming problem in the classic book "Programming Pearls"[1]. You can read it on O'Reilly Safari these days[2].

Even if you don't read the book, that first chapter, "Cracking the Oyster", is worth a read. It's a fun problem.

[1]: https://amzn.to/2vWkZ0D

[2]: https://learning.oreilly.com/library/view/programming-pearls...

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

#6

Post by gregschlom »

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.

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

#7

Post by taberiand »

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.

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

#9

Post by raverbashing »

I think you can assume 8-digit numbers can be stored in 27 bits

The relationship between cardinality of the codomain and image of the numbers is approximately 100

I would try to convert incoming numbers into pairs/tuples of N + differences (which can be done using less bits)

Post reply on HN