algorithm - 使用 1 MB RAM 对 100 万个 8 位十进制数字进行排序

Question

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

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

问答来源:

slashdot.org

cleaton.net

Answer 1

到目前为止，这里还没有提到一个相当狡猾的技巧。我们假设您没有额外的方法来存储数据，但事实并非如此。

解决你的问题的一种方法是做以下可怕的事情，任何人在任何情况下都不应该尝试这样做:使用网络流量来存储数据。不，我不是指 NAS。

您可以通过以下方式仅用几个字节的 RAM 对数字进行排序:

• 首先获取 2 个变量:COUNTER 和 VALUE。
• 首先将所有寄存器设置为0；
• 每次收到整数 I 时，增加 COUNTER 并将 VALUE 设置为 max(VALUE, I);
• 然后向路由器发送数据设置为I的ICMP回显请求数据包。删除 I 并重复。
• 每次收到返回的 ICMP 数据包时，您只需提取整数并在另一个回显请求中再次将其发回。这会产生大量包含整数的 ICMP 请求来回移动。

一旦 COUNTER 达到 1000000，您就可以将所有值存储在不间断的 ICMP 请求流中，并且 VALUE 现在包含最大值整数。选择一些阈值 T >> 1000000。将 COUNTER 设置为零。每次收到 ICMP 数据包时，递增 COUNTER 并在另一个回显请求中发送包含的整数 I，除非 I=VALUE，在在这种情况下，将其传输到已排序整数的目的地。一旦 COUNTER=T，将 VALUE 减 1，将 COUNTER 重置为零并重复。一旦 VALUE 达到零，您应该已经将所有整数按从大到小的顺序传输到目的地，并且只为两个持久变量使用了大约 47 位 RAM(以及您需要的任何少量 RAM临时值)。

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