我有一台有1mb内存的电脑，没有其他本地存储。我必须使用它通过TCP连接接受100万个8位十进制数字，对它们进行排序，然后通过另一个TCP连接发送排序的列表。
数字列表可能包含重复的，我不能丢弃。代码将放在ROM中，所以我不需要从1 MB中减去我的代码的大小。我已经有了驱动以太网端口和处理TCP/IP连接的代码，它需要2 KB的状态数据，包括1 KB的缓冲区，代码将通过它读取和写入数据。这个问题有解决办法吗?
问答来源:
slashdot.org
cleaton.net
当前回答
如果输入流可以接收几次，这就容易多了(没有关于这方面的信息，想法和时间性能问题)。然后，我们可以数小数。有了计数值，就很容易生成输出流。通过计算值来压缩。 这取决于输入流中的内容。
其他回答
你用的是哪种电脑?它可能没有任何其他“正常”的本地存储，但它是否有视频RAM，例如?100万像素x每像素32位(比如说)非常接近你所需的数据输入大小。
(我主要是问旧的Acorn RISC PC的内存，如果你选择低分辨率或低颜色深度的屏幕模式，它可以“借用”VRAM来扩展可用的系统RAM !)这在只有几MB普通RAM的机器上非常有用。
我们可以利用网络堆栈，在我们得到所有数字之前，按顺序发送数字。如果你发送1M的数据，TCP/IP会把它分解成1500字节的数据包，并按照目标发送。每个包将被赋予一个序列号。
我们可以用手来做。在填满内存之前，我们可以对现有的数据进行排序，并将列表发送给目标，但在每个数字周围的序列中留下空洞。然后用同样的方法处理第二个1/2的数字，使用序列中的这些洞。
远端的网络堆栈将按顺序组装结果数据流，然后将其提交给应用程序。
它使用网络来执行归并排序。这是一个完全的黑客，但我是受到之前列出的其他网络黑客的启发。
下面是一些可以解决这个问题的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字节作为剩余变量和堆栈空间。
它在我的至强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!')
该算法的详细解释可以在以下一系列帖子中找到:
1MB排序说明 算术编码与1MB排序问题 使用定点数学的算术编码
排序在这里是次要问题。正如其他人所说，仅仅存储整数是困难的，并且不能在所有输入上工作，因为每个数字需要27位。
我对此的看法是:只存储连续(排序)整数之间的差异，因为它们很可能很小。然后使用压缩方案，例如，每个输入数字增加2位，来编码数字存储在多少位上。 喜欢的东西:
00 -> 5 bits
01 -> 11 bits
10 -> 19 bits
11 -> 27 bits
在给定的内存限制内，应该能够存储相当数量的可能输入列表。如何选择压缩方案以使其在最大输入数量上工作的数学超出了我的范围。
我希望您能够利用输入的领域特定知识，在此基础上找到足够好的整数压缩方案。
哦，然后，当你收到数据时，你对那个排序的列表进行插入排序。
If it is possible to read the input file more than once (your problem statement doesn't say it can't), the following should work. It is described in Benchley's book "Programming Perls." If we store each number in 8 bytes we can store 250,000 numbers in one megabyte. Use a program that makes 40 passes over the input file. On the first pass it reads into memory any integer between 0 and 249,999, sorts the (at most) 250,000 integers and writes them to the output file. The second pass sorts the integers from 250,000 to 499,999 and so on to the 40th pass, which sorts 9,750,000 to 9,999,999.
