谷歌的(坏)方法，从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)

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

你试过转换成十六进制吗?

我可以看到前后文件大小都有了很大的减小;然后，用自由空间分步计算。也许，再次转换为dec, order，十六进制，另一个块，转换为dec, order…

对不起. .我不知道是否可行

# for i in {1..10000};do echo $(od -N1 -An -i /dev/urandom) ; done > 10000numbers
# for i in $(cat 10000numbers ); do printf '%x\n' $i; done > 10000numbers_hex
# ls -lah total 100K
drwxr-xr-x  2 diego diego 4,0K oct 22 22:32 .
drwx------ 39 diego diego  12K oct 22 22:31 ..
-rw-r--r--  1 diego diego  29K oct 22 22:33 10000numbers_hex
-rw-r--r--  1 diego diego  35K oct 22 22:31 10000numbers

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

下面是这类问题的一般解决方案:

一般程序

所采取的方法如下。该算法在一个32位字的缓冲区上操作。它在循环中执行以下过程:

We start with a buffer filled with compressed data from the last iteration. The buffer looks like this |compressed sorted|empty| Calculate the maximum amount of numbers that can be stored in this buffer, both compressed and uncompressed. Split the buffer into these two sections, beginning with the space for compressed data, ending with the uncompressed data. The buffer looks like |compressed sorted|empty|empty| Fill the uncompressed section with numbers to be sorted. The buffer looks like |compressed sorted|empty|uncompressed unsorted| Sort the new numbers with an in-place sort. The buffer looks like |compressed sorted|empty|uncompressed sorted| Right-align any already compressed data from the previous iteration in the compressed section. At this point the buffer is partitioned |empty|compressed sorted|uncompressed sorted| Perform a streaming decompression-recompression on the compressed section, merging in the sorted data in the uncompressed section. The old compressed section is consumed as the new compressed section grows. The buffer looks like |compressed sorted|empty|

执行此过程，直到所有数字都已排序。

压缩

当然，这种算法只有在知道实际要压缩什么之前，才有可能计算出新排序缓冲区的最终压缩大小。其次，压缩算法需要足够好来解决实际问题。

所使用的方法使用三个步骤。首先，算法将始终存储排序序列，因此我们可以只存储连续条目之间的差异。每个差值都在[0,99999999]的范围内。

这些差异随后被编码为一元比特流。这个流中的1表示“向累加器添加1,0表示“将累加器作为一个条目发出，并重置”。所以差N由N个1和1个0表示。

所有差异的和将接近算法支持的最大值，所有差异的计数将接近算法中插入的值的数量。这意味着我们期望流在最后包含最大值1和计数0。这允许我们计算流中0和1的期望概率。即，0的概率为count/(count+maxval)， 1的概率为maxval/(count+maxval)。

我们使用这些概率来定义这个比特流上的算术编码模型。这个算术代码将在最佳空间中精确地编码1和0的数量。我们可以计算该模型对于任何中间位流所使用的空间:bits = encoded * log2(1 + amount / maxval) + maxval * log2(1 + maxval / amount)。若要计算算法所需的总空间，请将encoded设置为amount。

为了不需要大量的迭代，可以向缓冲区添加少量开销。这将确保算法将至少对适合这个开销的数量进行操作，因为到目前为止，算法最大的时间成本是每个周期的算术编码压缩和解压缩。

除此之外，在算术编码算法的定点近似中，存储簿记数据和处理轻微的不准确性是需要一些开销的，但总的来说，即使使用可以包含8000个数字的额外缓冲区，该算法也能够容纳1MiB的空间，总共1043916字节的空间。

最优

除了减少算法的开销外，理论上不可能得到更小的结果。为了仅仅包含最终结果的熵，1011717个字节是必要的。如果我们减去为提高效率而增加的额外缓冲区，该算法使用1011916字节来存储最终结果+开销。

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

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

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

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

解决方案可能只是因为1兆字节和100万字节之间的差异。大约有2的8093729.5次方种不同的方法来选择100万个允许重复的8位数，顺序不重要，所以一台只有100万字节RAM的机器没有足够的状态来表示所有的可能性。但是1M (TCP/IP少2k)是1022*1024*8 = 8372224位，所以解决方案是可能的。

第一部分，初始解

这个方法需要1M多一点，我稍后会改进它以适应1M。

我将把0到99999999范围内的数字的紧凑排序列表存储为7位数字的子列表序列。第一个子列表包含从0到127的数字，第二个子列表包含从128到255的数字，等等。100000000/128正好是781250，因此需要781250个这样的子列表。

每个子列表由一个2位的子列表头和一个子列表体组成。子列表主体为每个子列表条目占用7位。所有子列表都连接在一起，并且这种格式可以确定一个子列表的结束位置和下一个子列表的开始位置。一个完全填充的列表所需的总存储空间是2*781250 + 7*1000000 = 8562500位，大约是1.021 m -字节。

4个可能的子列表头值是:

00空子列表，后面什么都没有。

01单例，在子列表中只有一个条目，并且接下来的7位保存它。

子列表至少包含两个不同的数字。除了最后一个条目小于或等于第一个条目外，条目以非递减顺序存储。这允许识别子列表的结尾。例如，数字2,4,6将被存储为(4,6,2)。数字2,2,3,4,4将被存储为(2,3,4,2)。

子列表包含单个数字的2个或更多重复。接下来的7位给出数字。然后是0个或多个值为1的7位条目，后面是一个值为0的7位条目。子列表体的长度决定了重复的次数。例如，数字12,12将存储为(12,0)，数字12,12,12将存储为(12,1,0)，数字12,12,12,12将存储为(12,1,1,0)，以此类推。

我从一个空列表开始，读入一堆数字并将它们存储为32位整数，对新数字进行排序(可能使用heapsort)，然后将它们合并到一个新的紧凑排序列表中。重复该操作，直到不再需要读取数字为止，然后再次遍历紧凑列表以生成输出。

下面的行表示列表合并操作开始前的内存。“O”是存放已排序的32位整数的区域。“X”是存放旧紧凑列表的区域。“=”符号是紧凑列表的扩展空间，“O”中的每个整数对应7位。“Z”是其他随机的开销。

ZZZOOOOOOOOOOOOOOOOOOOOOOOOOO==========XXXXXXXXXXXXXXXXXXXXXXXXXX

合并例程从最左边的“O”和最左边的“X”开始读取，并从最左边的“=”开始写入。直到所有的新整数被合并，写指针才会捕获紧凑列表的读指针，因为这两个指针为每个子列表前进2位，为旧紧凑列表中的每个条目前进7位，并且有足够的额外空间容纳新数字的7位条目。

第二部分，把它塞进1M

为了将上面的解决方案压缩到1M，我需要使紧凑列表的格式更紧凑一点。我将去掉其中一个子列表类型，这样就只有3个不同的子列表头值。然后我可以使用“00”，“01”和“1”作为子列表头值，并节省一些比特。子列表类型为:

空子列表，后面什么都没有。

B单例，在子列表中只有一个条目，接下来的7位保存它。

子列表至少包含2个不同的数字。除了最后一个条目小于或等于第一个条目外，条目以非递减顺序存储。这允许识别子列表的结尾。例如，数字2,4,6将被存储为(4,6,2)。数字2,2,3,4,4将被存储为(2,3,4,2)。

子列表由单个数字的2个或2个以上的重复组成。

我的3个子列表头值将是“A”，“B”和“C”，所以我需要一种方法来表示d类型的子列表。

Suppose I have the C-type sublist header followed by 3 entries, such as "C[17][101][58]". This can't be part of a valid C-type sublist as described above, since the third entry is less than the second but more than the first. I can use this type of construct to represent a D-type sublist. In bit terms, anywhere I have "C{00?????}{1??????}{01?????}" is an impossible C-type sublist. I'll use this to represent a sublist consisting of 3 or more repetitions of a single number. The first two 7-bit words encode the number (the "N" bits below) and are followed by zero or more {0100001} words followed by a {0100000} word.

For example, 3 repetitions: "C{00NNNNN}{1NN0000}{0100000}", 4 repetitions: "C{00NNNNN}{1NN0000}{0100001}{0100000}", and so on.

That just leaves lists that hold exactly 2 repetitions of a single number. I'll represent those with another impossible C-type sublist pattern: "C{0??????}{11?????}{10?????}". There's plenty of room for the 7 bits of the number in the first 2 words, but this pattern is longer than the sublist that it represents, which makes things a bit more complex. The five question-marks at the end can be considered not part of the pattern, so I have: "C{0NNNNNN}{11N????}10" as my pattern, with the number to be repeated stored in the "N"s. That's 2 bits too long.

我将不得不借2位，然后从这个模式中4位未使用的位中还钱。读取时，遇到“C{0NNNNNN}{11N00AB}10”时，输出“N”中数字的2个实例，用A位和B位覆盖最后的“10”，并将读指针倒回2位。对于这个算法，破坏性读取是可以的，因为每个紧凑列表只遍历一次。

当写入一个重复2次的单个数字的子列表时，写入“C{0NNNNNN}11N00”并将借来的比特计数器设置为2。在每次写入借位计数器非零的时候，它会为写入的每一位减数，当计数器为零时写入“10”。因此，接下来写入的2位将进入槽A和槽B，然后“10”将被放到最后。

用“00”、“01”和“1”表示3个子列表头值，我可以将“1”分配给最流行的子列表类型。我需要一个小表来将子列表标题值映射到子列表类型，并且我需要每个子列表类型的出现计数器，以便我知道最好的子列表标题映射是什么。

当所有子列表类型都同样流行时，就会出现完全填充的紧凑列表的最坏情况最小表示。在这种情况下，我为每3个子列表头保存1位，因此列表大小为2*781250 + 7*1000000 - 781250/3 = 8302083.3位。四舍五入到32位的字边界，即8302112位，或1037764字节。

1M减去TCP/IP状态和缓冲区的2k是1022*1024 = 1046528字节，剩下8764字节可供使用。

但是改变子列表头映射的过程如何呢?在下面的内存映射中，“Z”是随机开销，“=”是空闲空间，“X”是紧凑列表。

ZZZ=====XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

从最左边的“X”开始读，从最左边的“=”开始写，然后往右写。当它完成时，压缩列表将会变得更短，它将会在内存的错误一端:

ZZZXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX=======

所以我需要把它向右分流

ZZZ=======XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

在头映射变化过程中，多达1/3的子列表头将从1位变为2位。在最坏的情况下，这些都将位于列表的头部，因此在开始之前，我至少需要781250/3位的空闲存储空间，这使我回到了紧凑列表的前一个版本的内存要求:(

为了解决这个问题，我将781250子列表分成10个子列表组，每个子列表组78125子列表。每个组都有自己独立的子列表头映射。用字母A到J表示组:

ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ

在子列表头映射变化期间，每个子列表组缩小或保持不变:

ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAA=====BBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABB=====CCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCC======DDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDD======EEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEE======FFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFF======GGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGG=======HHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHH=======IJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHI=======JJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ=======
ZZZ=======AAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ

映射更改期间子列表组临时扩展的最坏情况是78125/3 = 26042位，小于4k。如果我允许4k加上1037764字节用于完全填充的紧凑列表，那么内存映射中的“Z”就剩下8764 - 4096 = 4668字节。

对于10个子列表头映射表、30个子列表头出现计数和我需要的其他几个计数器、指针和小缓冲区，以及我已经不注意使用的空间，比如函数调用返回地址和局部变量的堆栈空间，这些应该足够了。

第三部分，运行需要多长时间?

对于空的紧凑列表，1位的列表头将用于空的子列表，列表的起始大小将是781250位。在最坏的情况下，每增加一个数字，列表就增长8位，因此32 + 8 = 40位的空闲空间需要将每个32位数字放在列表缓冲区的顶部，然后排序和合并。在最坏的情况下，更改子列表报头映射将导致占用2*781250 + 7*entries - 781250/3位的空间。

如果策略是在列表中至少有800000个数字的情况下，每5次合并后更改子列表头映射，那么最坏的情况下运行将涉及大约30M的紧凑列表读写活动。

来源:

http://nick.cleaton.net/ramsortsol.html