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

14 浏览
0 Comments

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

我有一台只有1 MB RAM和无其他本地存储设备的计算机。我必须使用它来通过TCP连接接受100万个8位数字，对它们进行排序，然后通过另一个TCP连接发送已排序的列表。

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

问题和答案的来源:

slashdot.org

cleaton.net

admin 更改状态以发布 2023年5月20日
0

2 答案

0 Comments

这里有一份解决该问题的C++代码。

内存限制得到满足的证明：

编辑： 作者没有在这篇帖子或他的博客中给出最大内存需求的证明。由于编码值所需的位数取决于以前编码的值，因此这样的证明可能不是轻而易举的。作者指出，他经过实验得到的最大编码大小是1011732，并随意选择了缓冲区大小为1013000。

typedef unsigned int u32;
namespace WorkArea
{
    static const u32 circularSize = 253250;
    u32 circular[circularSize] = { 0 };         // consumes 1013000 bytes
    static const u32 stageSize = 8000;
    u32 stage[stageSize];                       // consumes 32000 bytes
    ...

这两个数组一共占用1045000字节的存储空间。这留下了1048576-1045000-2×1024= 1528字节的剩余变量和堆栈空间。

在我的Xeon W3520上运行大约需要23秒。如果采用以下Python脚本，可以验证程序的工作，假设程序名为sort1mb.exe：

from subprocess import *
import random
sequence = [random.randint(0, 99999999) for i in xrange(1000000)]
sorter = Popen('sort1mb.exe', stdin=PIPE, stdout=PIPE)
for value in sequence:
    sorter.stdin.write('%08d\n' % value)
sorter.stdin.close()
result = [int(line) for line in sorter.stdout]
print('OK!' if result == sorted(sequence) else 'Error!')

该算法的详细说明可以在以下一系列帖子中找到：

0
0 Comments

目前还没有提到的一个非常狡猾的技巧。我们假设你没有额外的存储数据的方式，但这并不严格正确。

解决问题的一种方法是使用以下可怕的方式，任何情况下都不应该尝试：使用网络流量来存储数据。 我的意思并不是NAS。

你可以使用以下方法仅使用几个字节的RAM来排序数字：

  • 首先取2个变量：COUNTER和VALUE。
  • 首先将所有寄存器设置为0；
  • 每当你接收到一个整数I时，增加COUNTER，并将VALUE设置为max(VALUE, I)；
  • 然后将数据设置为I的ICMP回显请求数据包发送到路由器。擦除I并重复；
  • 每次收到回传的ICMP数据包，你只需要提取整数并再次发送回去。这会产生大量的ICMP请求，在这些请求中来回传递包含整数的数据。

一旦COUNTER达到1000000，你就可以通过这些不断的ICMP请求流获得所有数值，而VALUE现在包含最大的整数。选定某个threshold T >> 1000000。将COUNTER设置为零。每当你收到一个ICMP数据包，增加COUNTER并在另一个回声请求中发送包含的整数I，除非I=VALUE，否则传输到已排序整数的目标。一旦COUNTER=T，将VALUE减少1，将COUNTER重置为零并重复。一旦VALUE达到零，你应该已经将所有整数按照从大到小的顺序传输到目标，并且仅使用了大约47位RAM来存储两个持久变量（以及临时变量所需的任何小量）。

我知道这很可怕，我也知道可能会有各种实际问题，但我认为这可能会让你们中的一些人发笑或者至少感到恐惧。

0