现在的目标是一个实际的解决方案，覆盖所有可能的情况下，输入在8位数范围内，只有1MB的RAM。注:工作正在进行中，明天继续。使用对已排序整型的增量进行算术编码，对于1M个已排序整型，最坏的情况是每个条目花费大约7位(因为99999999/1000000是99，而log2(99)几乎是7位)。

但是你需要将1m个整数排序到7位或8位!级数越短，delta就越大，因此每个元素的比特数就越多。

我正在努力尽可能多地压缩(几乎)在原地。第一批接近250K的整数最多每个需要大约9位。因此结果大约需要275KB。重复使用剩余的空闲内存几次。然后解压缩-就地合并-压缩这些压缩块。这很难，但也是可能的。我认为。

合并后的列表将越来越接近每整数7位的目标。但是我不知道合并循环需要多少次迭代。也许3。

但是算术编码实现的不精确性可能使它不可能实现。如果这个问题是可能的，它将是非常紧张的。

有志愿者吗?

If it is possible to read the input file more than once (your problem statement doesn't say it can't), the following should work. It is described in Benchley's book "Programming Perls." If we store each number in 8 bytes we can store 250,000 numbers in one megabyte. Use a program that makes 40 passes over the input file. On the first pass it reads into memory any integer between 0 and 249,999, sorts the (at most) 250,000 integers and writes them to the output file. The second pass sorts the integers from 250,000 to 499,999 and so on to the 40th pass, which sorts 9,750,000 to 9,999,999.

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

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

假设这个任务是可能的。在输出之前，内存中会有一个百万个排序数字的表示。有多少种不同的表示法?由于可能有重复的数字，我们不能使用nCr(选择)，但有一种叫做multichoose的操作，它适用于多集。

在0..99,999,999范围内有22e2436455种方法来选择一百万个数字。 这需要8,093,730位来表示每个可能的组合，或1,011,717字节。

所以理论上是可能的，如果你能想出一个合理(足够)的数字排序表。例如，一个疯狂的表示可能需要一个10MB的查找表或数千行代码。

但是，如果“1M RAM”意味着100万个字节，那么显然没有足够的空间。事实上，多5%的内存使它在理论上成为可能，这对我来说意味着表示必须非常有效，可能是不理智的。

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

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

到目前为止，这里还没有提到一个相当狡猾的技巧。我们假设您没有额外的方法来存储数据，但严格来说这并不正确。

解决问题的一种方法是做以下可怕的事情，任何人在任何情况下都不应该尝试:使用网络流量存储数据。不，我指的不是NAS。

你可以用以下方法对只有几个字节内存的数字进行排序:

首先取两个变量:COUNTER和VALUE。 首先将所有寄存器设置为0; 每次你收到一个整数I，增加COUNTER并将VALUE设置为max(VALUE, I); 然后向路由器发送数据集为I的ICMP echo请求报文。擦掉I，重复。 每次收到返回的ICMP包时，只需提取整数并在另一个回显请求中再次发送出去。这将产生大量的ICMP请求，其中包含整数。

Once COUNTER reaches 1000000, you have all of the values stored in the incessant stream of ICMP requests, and VALUE now contains the maximum integer. Pick some threshold T >> 1000000. Set COUNTER to zero. Every time you receive an ICMP packet, increment COUNTER and send the contained integer I back out in another echo request, unless I=VALUE, in which case transmit it to the destination for the sorted integers. Once COUNTER=T, decrement VALUE by 1, reset COUNTER to zero and repeat. Once VALUE reaches zero you should have transmitted all integers in order from largest to smallest to the destination, and have only used about 47 bits of RAM for the two persistent variables (and whatever small amount you need for the temporary values).

我知道这很可怕，我知道可能会有各种各样的实际问题，但我想这可能会让你们中的一些人发笑，或者至少会吓到你们。