使用1MB RAM对100万个8位小数进行排序

Question

使用1MB RAM对100万个8位小数进行排序

761

我有一台只有1MB RAM和没有其他本地存储的电脑。我必须使用它通过TCP连接接受100万个8位十进制数，对它们进行排序，然后通过另一个TCP连接发送已排序的列表。

这个数字列表可能包含重复项，我不能丢弃它们。代码将被放在ROM中，因此我不需要将我的代码大小从1MB中减去。我已经有了驱动以太网端口和处理TCP/IP连接的代码，并且它需要2KB的状态数据，包括1KB的缓冲区，通过该缓冲区代码将读取和写入数据。有没有解决这个问题的方法？

问题和答案来源：

slashdot.org

cleaton.net

- Favourite Onwuemene

49

一百万个八位小数的数字（最小27位整数二进制）> 1MB内存。 - Mr47

16

1M的RAM意味着2^20个字节？在这种架构中一个字节包含多少位？“1百万8位十进制数字”中的“百万”是指国际单位制中的一百万（10^6）吗？什么是8位十进制数？是小于10^8的自然数，其小数表示法有8位数字但不包括小数点，还是其他什么？ - user395760

15

需要翻译的内容：1 million 8 decimal digit numbers or 1 million 8 bit numbers?一百万个8位十进制数字或者一百万个8位二进制数字？ - Patrick White

15

这让我想起了《Dr Dobb's Journal》杂志上的一篇文章（大约在1998-2001年间），作者在读取电话号码时使用了插入排序来进行排序：那是我第一次意识到，有时较慢的算法可能更快... - Adrien Plisson

111

还有一种解决方案还没有被提到：购买具有2MB RAM的硬件。这不应该更加昂贵，而且会让问题变得容易得多。 - Daniel Wagner

显示剩余13条评论

36个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Alexander Nassian · Answer 1

如果数字的范围是有限的（例如，只能是模2 8位数字，或者只有10个不同的8位数字），那么您可以编写一个优化的排序算法。但是，如果您想对所有可能的8位数字进行排序，则使用这么少的内存是不可能的。

- Christoph Bartoschek · Answer 2

由于ROM大小不计算，因此除了TCP缓冲区之外，不需要任何额外的RAM。只需实现一个大型有限状态机。每个状态表示读取的数字的多重集合。在读取一百万个数字后，只需打印与达到的状态相对应的数字即可。

- mjfrazer · Answer 3

-2

你需要计数，最多到99,999,999，并在途中指示1,000,000个停止点。因此，可以使用位流，其被解释为1表示增加计数器，0表示输出数字。如果流中的前8位是00110010，则我们迄今为止有0、0、2、2、3。

log(99,999,999 + 1,000,000) / log(2) = 26.59。你的内存中有2^28位。你只需要使用一半！

- mjfrazer

如果所有数字都是99,999,999，你需要相同数量的1位才能到达第一个0位。这远远超出了分配的1 MB内存。 - StapleGun

是的，我脑抽了，把1MB当作2^28位而不是2^23位。 - mjfrazer

好的，这是我的第二次尝试。 - mjfrazer

好的，这是我的第二次尝试。您可以将间隙编码为可变长度字段中前一个间隙的增量。平均增量为100，并且假设1M个数字的正态分布，其中一些％的数字将具有100-32和100 + 31之间的间隙宽度，我们可以将其编码为6位带符号整数。我们将此间隙编码为0xxxxxx，其中x是从100开始的2s补码间隙偏移量。这使用每个数字7位。对于我们想要不同间隙的罕见情况，我们将其编码为一串表示比特数减1的1，一个零和间隙的流，例如1110bbbbbbbb。 - mjfrazer

如果存在许多大大小小的间隙导致病态行为，您可以指示第二个编码方案，该方案将使用0xxxx来编码0-15的间隙，10xxxxx（7位）来编码16-47的间隙，110xxxxxx（9位）来编码48-111的间隙，以此类推。由于您的平均间隙必须为100，因此您需要不同的编码模式来描述围绕100分布的间隙。 - mjfrazer

- Marichyasana · Answer 4

如果可以多次读取输入文件（您的问题陈述没有说不能），则以下方法应该有效。它在Benchley的书“Programming Perls”中有描述。如果我们将每个数字存储在8个字节中，我们可以在一个兆字节中存储250,000个数字。使用一个程序对输入文件进行40次遍历。在第一次遍历中，它会将0到249,999之间的任何整数读入内存，对（最多）250,000个整数进行排序，并将它们写入输出文件。第二次遍历对250,000到499,999之间的整数进行排序，以此类推，直到第40次遍历，将9,750,000到9,999,999进行排序。

- Phyxle · Answer 5

如果数字均匀分布，我们可以使用计数排序。我们应该在一个数组中保留每个数字重复的次数。可用空间为：1 MB - 3 KB = 1045504 B或8364032位每个数字的位数= 8364032/1000000 = 8 因此，我们可以将每个数字重复的次数存储到最大值2^8-1=255。使用这种方法，我们有额外的364032位未使用，可以用来处理一个数字重复超过255次的情况。例如，我们可以说数字255表示重复大于或等于255。在这种情况下，我们应该存储一系列数字+重复。如下所示，我们可以处理7745个特殊情况：

364032 /（表示每个数字所需的位数+表示100万所需的位数）= 364032 /（27 + 20）= 7745

- user319660 · Answer 6

你尝试过将其转换成十六进制吗？

我可以看到在处理前后文件大小有显著的减少；然后，利用空闲空间进行分段处理。也许可以将其再次转换成十进制，排序，转换成十六进制，处理另一个块，再转换成十进制，排序...

抱歉，我不知道这是否可行。

# for i in {1..10000};do echo $(od -N1 -An -i /dev/urandom) ; done > 10000numbers
# for i in $(cat 10000numbers ); do printf '%x\n' $i; done > 10000numbers_hex
# ls -lah total 100K
drwxr-xr-x  2 diego diego 4,0K oct 22 22:32 .
drwx------ 39 diego diego  12K oct 22 22:31 ..
-rw-r--r--  1 diego diego  29K oct 22 22:33 10000numbers_hex
-rw-r--r--  1 diego diego  35K oct 22 22:31 10000numbers