使用1MB RAM对100万个8位小数进行排序

要表示排序后的数组，只需存储第一个元素和相邻元素之间的差异。以这种方式，我们关注的是编码最多可达到10^8的10^6个元素。让我们称其为D。要对D的元素进行编码，可以使用Huffman code。可以即时创建Huffman代码的字典，并在每次向排序数组中插入新项（插入排序）时更新数组。请注意，当字典因新项而更改时，整个数组应更新以匹配新编码。
如果每个唯一元素具有相同数量，则编码D的每个元素的平均比特数将被最大化。假设在D中出现F次的元素d1，d2，...，dN。在这种情况下（最坏情况下，输入序列中同时存在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 的情况。如果我们从0开始使用连续的数字作为 di，即 di= i-1，则会发生这种情况，因此

10^8=sum(1<=i<=N) F. di = sum(1<=i<=N) (10^6/N) (i-1) = (10^6/N) N (N-1)/2

即。

N ≤ 201。对于这种情况，平均比特数为log2（201）= 7.6511，这意味着我们需要大约1字节来保存排序后的数组中的每个输入元素。请注意，这并不意味着D一般情况下不能有超过201个元素。它只是表明如果D的元素是均匀分布的，则不能有超过201个唯一值。

如果输入流可以接收少数几次，那么这将会更容易（关于此事的信息不详，想法和时间性能问题）。然后，我们可以计算小数值。通过计算值来压缩输出流。这取决于输入流中包含什么内容。

我们有1 MB - 3 KB RAM = 2^23 - 3*2^13 bits = 8388608 - 24576 = 8364032 bits可用。

我们在10^8范围内给出了10^6个数字。这给出了平均间隔约为100 < 2^7 = 128

首先考虑更简单的问题，即当所有间隔都小于128时，数字相对均匀分布。这很容易。只需存储第一个数字和7位间隔：

(27位) + 10^6个7位间隔数字= 7000027位所需

请注意，重复的数字具有0间隔。

但是如果我们有大于127的间隔呢？

好的，假设表示间隔大小<127，但是127的间隔大小后面跟着实际间隔长度的连续8位编码：

 10xxxxxx xxxxxxxx                       = 127 .. 16,383
 110xxxxx xxxxxxxx xxxxxxxx              = 16384 .. 2,097,151

等等。

请注意，此数字表示描述了它自己的长度，因此我们知道下一个间隙数字何时开始。

仅具有小间隙<127，这仍然需要7000027位。

最多可以有（10 ^ 8）/（2 ^ 7）= 781250个23位间隙数字，需要额外的16 * 781,250 = 12,500,000位，这太多了。我们需要一种更紧凑且缓慢增加的间隙表示。

平均间隙大小为100，因此如果我们将它们重新排序为 [100, 99, 101, 98, 102, ..., 2, 198, 1, 199, 0, 200, 201, 202, ...] 并使用稠密二进制斐波那契基编码对其进行索引，不包含零对（例如，11011 = 8 + 5 + 2 + 1 = 16），用“00”分隔数字，那么我认为我们可以使间隙表示足够短，但需要进行更多分析。

如果输入流可以接收几次，这将会更容易（没有关于此的信息，想法和时间性能问题）。然后，我们可以计算小数值。通过计算值进行压缩，就可以轻松制作输出流。这取决于输入流中会有什么内容。

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

我的想法是：仅存储连续（排序）整数之间的差异，因为它们很可能很小。然后使用压缩方案，例如每个输入数字额外2位比特，以编码数字存储的位数。 类似于：

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

在给定的内存限制下，应该可以存储相当数量的可能输入列表。如何选择压缩方案以使其适用于最大数量的输入，这方面的数学知识超出了我的能力范围。

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

然后，在接收数据时对该排序列表进行插入排序。

现在的目标是找到一个实际的解决方案，用1MB的RAM覆盖8位数字范围内所有可能的情况。注意：正在进行中，明天将继续。使用排序整数的增量的算术编码，对于1M个排序整数的最坏情况每个条目大约需要7位（因为99999999/1000000是99，log2（99）几乎是7位）。

但是你需要将1m个整数排序才能达到7或8位！较短的序列会有更大的增量，因此每个元素需要更多的位。

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

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

但是算术编码实现的不精确可能会使其不可能。如果这个问题有可能解决，那么它将非常紧张。

有志愿者吗？

您只需存储序列中数字之间的差异，并使用编码来压缩这些序列数字。我们有2^23个比特。我们将其分成6位块，并让最后一位指示数字是否延伸到另外6位（5位加延伸块）。

因此，000010是1，000100是2。000001100000是128。现在，我们考虑表示数字序列差异的最坏情况，最高达到了10,000,000。可能有10,000,000/ 2 ^ 5大于 2 ^ 5 的差异，10,000,000/ 2 ^ 10大于 2 ^ 10 的差异和10,000,000/ 2 ^ 15大于 2 ^ 15的差异等等。

因此，我们添加要表示序列所需的比特数。我们有1,000,000 * 6 + roundup(10,000,000 / 2 ^ 5) * 6 + roundup(10,000,000 / 2 ^ 10) * 6 + roundup(10,000,000 / 2 ^ 15) * 6 + roundup(10,000,000 / 2 ^ 20) * 4 = 7935479。

2的24次方等于8388608。由于8388608大于7935479，我们应该有足够的内存。我们可能需要另外一点内存来存储插入新数字时的位置和总和。然后我们遍历整个序列，找到插入新数字的位置，必要时减小下一个差值，并将其后面的所有内容向右移动。

如果我们对这些数字一无所知，我们会受到以下限制：

• 我们需要在排序之前加载所有数字，
• 数字集不可压缩。

如果这些假设成立，那么您将需要至少26,575,425位存储空间（3,321,929字节）才能完成您的任务。

您能告诉我们有关您的数据的更多信息吗？

诀窍在于将算法状态（即整数多重集）表示为压缩的“递增计数器”=“+”和“输出计数器”=“！”字符流。例如，集合{0,3,3,4}将表示为“!+++!!+!”，后面跟任意数量的“+”字符。要修改多重集，您需要流出这些字符，并保留每次仅有常量数量的解压缩，然后在流回压缩形式之前进行原地更改。

我们知道最终集合中恰好有10^6个数字，因此最多有10^6个"!"字符。我们还知道我们的范围大小为10^8，这意味着最多有10^8个"+"字符。在10^8个"+"字符中排列10^6个"!"的方式是(10^8 + 10^6) choose 10^6，因此指定某个特定的排列需要~0.965 MiB的数据。这将是一个严格的限制。

我们可以将每个字符视为独立的，而不超过我们的配额。 "+"字符比"!"字符多100倍，这简化为如果我们忘记它们是相关的，则每个字符成为"+"的几率为100：1。 100：101的几率对应于每个字符{{link1：〜0.08位}}, 几乎相同的总计{{link2：〜0.965 MiB}}（在这种情况下忽略依赖关系只有{{link3：〜12位}}的成本！）。
存储已知先验概率的独立字符的最简单技术是Huffman编码。请注意，我们需要一个不切实际的大树（10个字符块的哈夫曼树每个块的平均成本约为2.4位，总共约为~2.9 Mib。20个字符块的哈夫曼树每个块的平均成本约为3位，总共约为~1.8 MiB。我们可能需要一个大小约为一百的块，这意味着我们的树中的节点比所有曾经存在过的计算机设备都多）。然而，根据问题，ROM在技术上是“免费”的，并且利用树中的规律的实际解决方案看起来基本相同。
伪代码

• 在ROM中存储足够大的哈夫曼树（或类似的块压缩数据）
• 从一个包含10^8个“+”字符的压缩字符串开始。
• 要插入数字N，流式输出压缩字符串，直到N个“+”字符过去，然后插入“!”。在进行操作时，将重新压缩的字符串流回先前的字符串上，并保持恒定数量的缓冲块以避免溢出/欠流。
• 重复一百万次：[输入、流式解压>插入>压缩]，然后解压缩输出。

在接收流时执行以下步骤。

1. 设置一些合理的块大小

伪代码思路：

1. 第一步是找到所有重复项，并将它们放入一个字典中，包括其计数并将其删除。
2. 第二步是将存在于算法步骤序列中的数字按其步骤顺序放置，并将它们放入特殊字典计数器中，例如n、n+1、n+2、2n、2n+1、2n+2等。
3. 开始压缩一些合理的数字范围，例如每1000或每10000个出现较少的数字重复。
4. 如果发现数字，则解压该范围并将其添加到范围中，并将其保持未压缩状态更长时间。
5. 否则，只需将该数字添加到byte[chunkSize]中。

在接收流时继续前4个步骤。最后一步要么失败（如果超过内存限制），要么在收集所有数据后开始输出结果，即按顺序开始排序范围并输出结果，对需要解压缩的范围进行解压缩并在到达它们时进行排序。