你用的是哪种电脑?它可能没有任何其他“正常”的本地存储，但它是否有视频RAM，例如?100万像素x每像素32位(比如说)非常接近你所需的数据输入大小。

(我主要是问旧的Acorn RISC PC的内存，如果你选择低分辨率或低颜色深度的屏幕模式，它可以“借用”VRAM来扩展可用的系统RAM !)这在只有几MB普通RAM的机器上非常有用。

在所有可能的输入中，这个问题只有一个解决方案。作弊。

通过TCP读取m个值，其中m接近内存中可排序的最大值，可能是n/4。 对250,000(大约)个数字进行排序并输出。 重复做另外3个四分之三。 让接收方在处理时合并接收到的4个数字列表。(这并不比使用单个列表慢多少。)

To represent the sorted array one can just store the first element and the difference between adjacent elements. In this way we are concerned with encoding 10^6 elements that can sum up to at most 10^8. Let's call this D. To encode the elements of D one can use a Huffman code. The dictionary for the Huffman code can be created on the go and the array updated every time a new item is inserted in the sorted array (insertion sort). Note that when the dictionary changes because of a new item the whole array should be updated to match the new encoding.

如果每个唯一元素的数量相等，则编码D中每个元素的平均比特数将最大化。比如元素d1 d2…， dN在D中各出现F次。在这种情况下(最坏的情况是输入序列中同时有0和10^8)我们有

sum（1<=i<=N） F. di = 10^8

在哪里

sum(1<=i<=N) F=10^6，或F=10^6/N，归一化频率将是p= F/10^=1/N

平均比特数为-log2(1/P) = log2(N)。在这种情况下，我们应该找到使n最大化的情况，这发生在di从0开始的连续数，或者di= i-1时

10 ^ 8 =(1 < =我< = N) f . di =(1 < =我< = N) (10 ^ 6 / N)(张)= (10 ^ 6 / N) N (N - 1) / 2

i.e.

N <= 201。在这种情况下，平均比特数是log2(201)=7.6511，这意味着我们将需要大约1字节的每个输入元素来保存排序的数组。注意，这并不意味着D一般不能有超过201个元素。它只是说明，如果D的元素是均匀分布的，那么D的唯一值不可能超过201个。

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

在10^8的范围内有10^6个值，所以平均每100个码点有一个值。存储第N个点到第(N+1)个点的距离。重复值的跳过值为0。这意味着跳跃平均需要7比特来存储，所以100万个跳跃将很适合我们的800万比特存储空间。

这些跳跃需要被编码成一个比特流，比如通过霍夫曼编码。插入是通过遍历比特流并在新值之后重写。通过遍历并写出隐含值来输出。出于实用性考虑，它可能被做成10^4个列表，每个列表包含10^4个代码点(平均100个值)。

随机数据的霍夫曼树可以通过假设跳跃长度上的泊松分布(均值=方差=100)先验地构建，但可以在输入上保留真实的统计数据，并用于生成处理病理病例的最佳树。

诀窍是将算法状态表示为“增量计数器”=“+”和“输出计数器”=“!”字符的压缩流，这是一个整数多集。例如，集合{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