我有一台有1mb内存的电脑，没有其他本地存储。我必须使用它通过TCP连接接受100万个8位十进制数字，对它们进行排序，然后通过另一个TCP连接发送排序的列表。
数字列表可能包含重复的，我不能丢弃。代码将放在ROM中，所以我不需要从1 MB中减去我的代码的大小。我已经有了驱动以太网端口和处理TCP/IP连接的代码，它需要2 KB的状态数据，包括1 KB的缓冲区，代码将通过它读取和写入数据。这个问题有解决办法吗?
问答来源:
slashdot.org
cleaton.net
当前回答
我将利用TCP的重传行为。
让TCP组件创建一个大的接收窗口。 收到一定数量的包，但没有发送ACK。 处理这些传递，创建一些(前缀)压缩数据结构 对最后一个不再需要的数据包发送重复的ack /等待重传超时 转到2 所有数据包被接受
这假设了桶或多次传递的某种好处。
可能是通过对批次/桶进行排序并合并它们。->根树
使用这种技术接受并排序前80%，然后读取后20%，验证后20%不包含将落在最低数字的前20%的数字。然后发送最低的20%的数字，从内存中删除，接受剩下的20%的新数字并合并。**
其他回答
如果输入流可以接收几次，这就容易多了(没有关于这方面的信息，想法和时间性能问题)。然后，我们可以数小数。有了计数值，就很容易生成输出流。通过计算值来压缩。 这取决于输入流中的内容。
我在这里的建议很大程度上归功于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位增量的桶
下面是一些可以解决这个问题的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排序问题 使用定点数学的算术编码
你最多要数到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位。你只需要用一半!
我将利用TCP的重传行为。
让TCP组件创建一个大的接收窗口。 收到一定数量的包，但没有发送ACK。 处理这些传递，创建一些(前缀)压缩数据结构 对最后一个不再需要的数据包发送重复的ack /等待重传超时 转到2 所有数据包被接受
这假设了桶或多次传递的某种好处。
可能是通过对批次/桶进行排序并合并它们。->根树
使用这种技术接受并排序前80%，然后读取后20%，验证后20%不包含将落在最低数字的前20%的数字。然后发送最低的20%的数字，从内存中删除，接受剩下的20%的新数字并合并。**
