如果输入流可以接收几次，这将是很大的 更简单(没有关于这方面的信息，想法和时间-性能问题)。

然后，我们可以数小数。如果是计数值的话 容易使输出流。通过计算值来压缩。它 这取决于输入流中的内容。

排序在这里是次要问题。正如其他人所说，仅仅存储整数是困难的，并且不能在所有输入上工作，因为每个数字需要27位。

我对此的看法是:只存储连续(排序)整数之间的差异，因为它们很可能很小。然后使用压缩方案，例如，每个输入数字增加2位，来编码数字存储在多少位上。 喜欢的东西:

00 -> 5 bits
01 -> 11 bits
10 -> 19 bits
11 -> 27 bits

在给定的内存限制内，应该能够存储相当数量的可能输入列表。如何选择压缩方案以使其在最大输入数量上工作的数学超出了我的范围。

我希望您能够利用输入的领域特定知识，在此基础上找到足够好的整数压缩方案。

哦，然后，当你收到数据时，你对那个排序的列表进行插入排序。

(我原来的答案是错误的，对不起，数学不好，见下面的休息。)

这个怎么样?

前27位存储您所看到的最小数字，然后是与下一个数字的差值，编码如下:5位存储用于存储差值的位数，然后是差值。使用00000表示您再次看到了该数字。

这是因为插入的数字越多，数字之间的平均差值就越小，所以当你添加更多的数字时，你用更少的比特来存储差值。我想这叫做增量表。

我能想到的最糟糕的情况是所有数字都等距(以100为间隔)，例如假设0是第一个数字:

000000000000000000000000000 00111 1100100
                            ^^^^^^^^^^^^^
                            a million times

27 + 1,000,000 * (5+7) bits = ~ 427k

Reddit来拯救你!

如果你要做的只是把它们排序，这个问题就简单了。它需要122k(100万比特)来存储你看到的数字(如果看到0，则第0位，如果看到2300，则第2300位，等等。

读取数字，将它们存储在位域中，然后在保持计数的同时将位移出。

但是，你必须记住你看过多少。我受到上面的子列表答案的启发，想出了这个方案:

用2位或27位代替1位:

00表示你没有看到这个数字。 01表示你看过一次 1表示你看过，接下来的26位是看了多少次。

我认为这是可行的:如果没有重复，你就有一个244k的列表。 在最坏的情况下，你看到每个数字两次(如果你看到一个数字三次，它会缩短列表的其余部分)，这意味着你不止一次看到了50,000个，你0次或1次看到了950,000个项目。

50,000 * 27 + 950,000 * 2 = 396.7k.

如果你使用以下编码，你可以做进一步的改进:

0表示你没有看到这个数字 10表示你看过一次 11是你计数的方式

这将导致平均280.7k的存储空间。

编辑:我周日早上的数学算错了。

最坏的情况是，我们两次看到50万个数字，所以数学就变成了:

500,000 *27 + 500,000 *2 = 1.77M

交替编码导致平均存储为

500,000 * 27 + 500,000 = 1.70M

: (

我在这里的建议很大程度上归功于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位增量的桶

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

我们可以利用网络堆栈，在我们得到所有数字之前，按顺序发送数字。如果你发送1M的数据，TCP/IP会把它分解成1500字节的数据包，并按照目标发送。每个包将被赋予一个序列号。

我们可以用手来做。在填满内存之前，我们可以对现有的数据进行排序，并将列表发送给目标，但在每个数字周围的序列中留下空洞。然后用同样的方法处理第二个1/2的数字，使用序列中的这些洞。

远端的网络堆栈将按顺序组装结果数据流，然后将其提交给应用程序。

它使用网络来执行归并排序。这是一个完全的黑客，但我是受到之前列出的其他网络黑客的启发。