我将利用TCP的重传行为。

让TCP组件创建一个大的接收窗口。 收到一定数量的包，但没有发送ACK。 处理这些传递，创建一些(前缀)压缩数据结构 对最后一个不再需要的数据包发送重复的ack /等待重传超时 转到2 所有数据包被接受

这假设了桶或多次传递的某种好处。

可能是通过对批次/桶进行排序并合并它们。->根树

使用这种技术接受并排序前80%，然后读取后20%，验证后20%不包含将落在最低数字的前20%的数字。然后发送最低的20%的数字，从内存中删除，接受剩下的20%的新数字并合并。**

诀窍是将算法状态表示为“增量计数器”=“+”和“输出计数器”=“!”字符的压缩流，这是一个整数多集。例如，集合{0,3,3,4}将被表示为“!+++!!+!”，后面跟着任意数量的“+”字符。要修改多集，您可以输出字符，每次只保持恒定的解压缩量，并在以压缩形式流回之前进行适当的更改。

细节

我们知道最终集合中恰好有10^6个数字，所以最多有10^6个“!”字符。我们还知道我们的范围大小为10^8，这意味着最多有10^8个“+”字符。10^6 "的排列方式!s在10^8 "+"s中的值是(10^8 + 10^6)选10^6，因此指定某种特定的排列需要大约0.965 MiB '的数据。那太紧了。

我们可以独立对待每个角色而不超出我们的配额。“+”字符正好是“!”字符的100倍，如果我们忘记了它们是相互依赖的，那么每个字符是“+”的概率就简化为100:1。100:101的几率对应于每个字符0.08位，对于几乎相同的~0.965 MiB(忽略依赖关系在这种情况下只有~12位的代价!)

The simplest technique for storing independent characters with known prior probability is Huffman coding. Note that we need an impractically large tree (A huffman tree for blocks of 10 characters has an average cost per block of about 2.4 bits, for a total of ~2.9 Mib. A huffman tree for blocks of 20 characters has an average cost per block of about 3 bits, which is a total of ~1.8 MiB. We're probably going to need a block of size on the order of a hundred, implying more nodes in our tree than all the computer equipment that has ever existed can store.). However, ROM is technically "free" according to the problem and practical solutions that take advantage of the regularity in the tree will look essentially the same.

伪代码

Have a sufficiently large huffman tree (or similar block-by-block compression data) stored in ROM Start with a compressed string of 10^8 "+" characters. To insert the number N, stream out the compressed string until N "+" characters have gone past then insert a "!". Stream the recompressed string back over the previous one as you go, keeping a constant amount of buffered blocks to avoid over/under-runs. Repeat one million times: [input, stream decompress>insert>compress], then decompress to output

基数树表示可以接近于处理这个问题，因为基数树利用了“前缀压缩”的优势。但是很难想象一个基树表表法可以在一个字节中表示单个节点——两个可能是极限。

但是，不管数据是如何表示的，一旦它被排序，它就可以以前缀压缩的形式存储，其中数字10、11和12将由001b、001b、001b表示，表示从前一个数字增加1。那么，也许10101b表示增量5,1101001b表示增量9，以此类推。

谷歌的(坏)方法，从HN线程。存储rle风格的计数。

你的初始数据结构是“99999999:0”(都是零，没有看到任何数字)，然后假设你看到了数字3,866,344，那么你的数据结构就变成了“3866343:0,1:1,96133654:0”，你可以看到数字总是在零位数和1位数之间交替，所以你可以假设奇数代表0位，偶数代表1位。这就变成了(3866343,1,96133654)

他们的问题似乎不包括副本，但让我们假设他们使用“0:1”来表示副本。

大问题#1:1M个整数的插入将花费很长时间。

大问题#2:像所有的普通增量编码解决方案一样，一些分布不能用这种方式覆盖。例如，1m整数，距离为0:99(例如，每个整数+99)。现在考虑相同的情况，但随机距离在0:99的范围内。(注:99999999/1000000 = 99.99)

谷歌的方法既不值得(缓慢)，也不正确。但要为他们辩护，他们的问题可能略有不同。

如果输入流可以接收几次，这就容易多了(没有关于这方面的信息，想法和时间性能问题)。然后，我们可以数小数。有了计数值，就很容易生成输出流。通过计算值来压缩。 这取决于输入流中的内容。

下面是一些可以解决这个问题的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排序问题 使用定点数学的算术编码