If the numbers are evenly distributed we can use Counting sort. We should keep the number of times that each number is repeated in an array. Available space is: 1 MB - 3 KB = 1045504 B or 8364032 bits Number of bits per number= 8364032/1000000 = 8 Therefore, we can store the number of times each number is repeated to the maximum of 2^8-1=255. Using this approach we have an extra 364032 bits unused that can be used to handle cases where a number is repeated more than 255 times. For example we can say a number 255 indicates a repetition greater than or equal to 255. In this case we should store a sequence of numbers+repetitions. We can handle 7745 special cases as shown bellow:

364032/(表示每个数字所需的位数+表示100万所需的位数)= 364032 / (27+20)=7745

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

Gilmanov的答案在假设上是非常错误的。它开始基于毫无意义的一百万个连续整数进行推测。这意味着没有差距。这些随机的间隙，不管有多小，真的是一个糟糕的主意。

你自己试试。获得100万个27位随机整数，对它们排序，用7-Zip, xz压缩，任何你想要的LZMA。结果超过1.5 MB。上面的前提是连续数字的压缩。即使是增量编码也超过1.1 MB。没关系，这使用了超过100 MB的RAM进行压缩。因此，即使压缩的整数也不适合这个问题，更不用说运行时RAM的使用了。

让我难过的是，人们竟然投票支持漂亮的图像和合理化。

#include <stdint.h>
#include <stdlib.h>
#include <time.h>

int32_t ints[1000000]; // Random 27-bit integers

int cmpi32(const void *a, const void *b) {
    return ( *(int32_t *)a - *(int32_t *)b );
}

int main() {
    int32_t *pi = ints; // Pointer to input ints (REPLACE W/ read from net)

    // Fill pseudo-random integers of 27 bits
    srand(time(NULL));
    for (int i = 0; i < 1000000; i++)
        ints[i] = rand() & ((1<<27) - 1); // Random 32 bits masked to 27 bits

    qsort(ints, 1000000, sizeof (ints[0]), cmpi32); // Sort 1000000 int32s

    // Now delta encode, optional, store differences to previous int
    for (int i = 1, prev = ints[0]; i < 1000000; i++) {
        ints[i] -= prev;
        prev    += ints[i];
    }

    FILE *f = fopen("ints.bin", "w");
    fwrite(ints, 4, 1000000, f);
    fclose(f);
    exit(0);

}

现在用LZMA压缩ints.bin…

    $ xz -f --keep ints.bin       # 100 MB RAM
    $ 7z a ints.bin.7z ints.bin   # 130 MB RAM
    $ ls -lh ints.bin*
        3.8M ints.bin
        1.1M ints.bin.7z
        1.2M ints.bin.xz

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

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

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

解决问题的一种方法是做以下可怕的事情，任何人在任何情况下都不应该尝试:使用网络流量存储数据。不，我指的不是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).

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

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

这个怎么样?

前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

: (