我有一台有1mb内存的电脑，没有其他本地存储。我必须使用它通过TCP连接接受100万个8位十进制数字，对它们进行排序，然后通过另一个TCP连接发送排序的列表。
数字列表可能包含重复的，我不能丢弃。代码将放在ROM中，所以我不需要从1 MB中减去我的代码的大小。我已经有了驱动以太网端口和处理TCP/IP连接的代码，它需要2 KB的状态数据，包括1 KB的缓冲区，代码将通过它读取和写入数据。这个问题有解决办法吗?
问答来源:
slashdot.org
cleaton.net
当前回答
如果我们对这些数字一无所知，我们就会受到以下约束:
我们需要在排序之前加载所有的数字， 这组数字是不可压缩的。
如果这些假设成立，则无法执行您的任务，因为您将需要至少26,575,425位的存储空间(3,321,929字节)。
你能跟我们说说你的数据吗?
其他回答
我们可以利用网络堆栈，在我们得到所有数字之前，按顺序发送数字。如果你发送1M的数据，TCP/IP会把它分解成1500字节的数据包，并按照目标发送。每个包将被赋予一个序列号。
我们可以用手来做。在填满内存之前，我们可以对现有的数据进行排序，并将列表发送给目标，但在每个数字周围的序列中留下空洞。然后用同样的方法处理第二个1/2的数字，使用序列中的这些洞。
远端的网络堆栈将按顺序组装结果数据流，然后将其提交给应用程序。
它使用网络来执行归并排序。这是一个完全的黑客，但我是受到之前列出的其他网络黑客的启发。
如果数字的范围是有限的(只能有2个8位数，或者只有10个不同的8位数)，那么你可以编写一个优化的排序算法。但如果你想对所有可能的8位数进行排序，这在内存那么少的情况下是不可能的。
你最多要数到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位。你只需要用一半!
现在的目标是一个实际的解决方案，覆盖所有可能的情况下，输入在8位数范围内，只有1MB的RAM。注:工作正在进行中，明天继续。使用对已排序整型的增量进行算术编码，对于1M个已排序整型，最坏的情况是每个条目花费大约7位(因为99999999/1000000是99，而log2(99)几乎是7位)。
但是你需要将1m个整数排序到7位或8位!级数越短，delta就越大，因此每个元素的比特数就越多。
我正在努力尽可能多地压缩(几乎)在原地。第一批接近250K的整数最多每个需要大约9位。因此结果大约需要275KB。重复使用剩余的空闲内存几次。然后解压缩-就地合并-压缩这些压缩块。这很难，但也是可能的。我认为。
合并后的列表将越来越接近每整数7位的目标。但是我不知道合并循环需要多少次迭代。也许3。
但是算术编码实现的不精确性可能使它不可能实现。如果这个问题是可能的，它将是非常紧张的。
有志愿者吗?
我在这里的建议很大程度上归功于Dan的解决方案
首先，我假设解决方案必须处理所有可能的输入列表。我认为流行的答案并没有做出这样的假设(在我看来这是一个巨大的错误)。
众所周知，任何形式的无损压缩都不会减小所有输入的大小。
所有流行的答案都假设它们能够有效地应用压缩来允许它们有额外的空间。事实上，一个足够大的额外空间块，以未压缩的形式保存他们部分完成的列表的一部分，并允许他们执行排序操作。这只是一个糟糕的假设。
对于这样的解决方案，任何了解如何进行压缩的人都能够设计一些不能很好地压缩该方案的输入数据，并且“解决方案”很可能会由于空间不足而崩溃。
相反，我采用数学方法。我们可能的输出是所有长度为LEN的列表，由0..MAX范围内的元素组成。这里LEN是1,000,000,MAX是100,000,000。
对于任意的LEN和MAX，编码此状态所需的比特数为:
Log2(MAX multichoice LEN)
因此，对于我们的数字，一旦我们完成了接收和排序，我们将需要至少Log2(100,000,000 MC 1,000,000)位来存储我们的结果，以一种能够唯一区分所有可能输出的方式。
这是~= 988kb。所以我们有足够的空间来存放结果。从这个角度来看，这是可能的。
[删除了无意义的漫谈，现在有更好的例子…]
最好的答案在这里。
另一个很好的答案是这里，它基本上使用插入排序作为函数，将列表扩展为一个元素(缓冲一些元素并进行预先排序，以允许一次插入多个元素，节省一些时间)。使用一个很好的压缩状态编码，7位增量的桶
