Sorting 1M 8-digit numbers in 1 MB of RAM (2012) • Hacker News Board

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

#61

Post by contravariant » Mon, Mar 30, 2020, 6:16 PM UTC

aasasd wrote: post #54

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 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 However, they explain that Golomb coding isn't quite enough for the 1M case and switch to arithmetic coding instead.

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.

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

#62

Post by tomaszs » Mon, Mar 30, 2020, 7:56 PM UTC

saagarjha wrote: post #31

tomaszs wrote: post #26

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…

Bitcoin mining hinges on computing hashes, though.

It was a figure of speech. Still my way is valid

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

#63

Post by ADefenestrator » Tue, Mar 31, 2020, 5:08 AM UTC

jayd16 wrote: post #27

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.

"prone to" is putting it mildly. ICMP echo requests tend to be processed by the often relatively anemic control plane CPU rather than ASICS and are at the bottom of the heap in terms priority. If you send a router 1MB of ICMP echo requests, it's virtually guaranteed to drop some or even most of them.