如果数字的范围有限（例如，只能有2个8位数字，或者只有10个不同的8位数字），那么您可以编写一个优化的排序算法。但是，如果您想对所有可能的8位数字进行排序，这在内存量较低的情况下是不可能的。

只有1兆字节和100万字节之间的差异才有可能解决方案。大约有2的幂8093729.5种不同的方法来选择100万允许重复的8位数字，顺序并不重要，因此只有100万字节RAM的机器没有足够的状态来表示所有可能性。但是1M（TCP/IP2k较少）是1022*1024*8=8372224位，因此解决方案是可能的。

第1部分，初始解决方案

这种方法需要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 Singleton，子列表中只有一个条目，接下来的7位保存它。

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

子列表保存一个数字的2次或更多次重复。接下来的7位给出数字。然后是零个或更多值为1的7位条目，后跟一个值为0的7位条目。子列表主体的长度决定了重复的次数。例如，数字12,12将存储为（12,0），数字12,12,12将存储为（12,1,0），12,12,12将存储为（12,1,1,0），依此类推。

我从一个空列表开始，读取一堆数字并将它们存储为32位整数，对新数字进行排序（可能使用堆排序），然后将它们合并到一个新的紧凑排序列表中。重复直到没有更多的数字要读取，然后再次遍历紧凑列表以生成输出。

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

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

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

第2部分，把它塞进1M

为了将上面的解决方案压缩到1M，我需要使紧凑列表格式更加紧凑。我将去掉子列表类型之一，这样就只有3个不同的子列表标头值。然后我可以使用“00”、“01”和“1”作为子列表标头值并保存一些位。子列表类型是：

一个空的子列表，什么都没有。

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

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

子列表由一个数字的2个或多个重复组成。

我的3个子列表标题值将是“A”、“B”和“C”，所以我需要一种表示D型子列表的方法。

假设我有一个C类型子列表标头，后跟3个条目，例如“C[17][101][58]”。这不能是上面描述的有效C类型子列表的一部分，因为第三个条目小于第二个条目，但大于第一个条目。我可以使用这种类型的构造来表示一个D类型子列表。用位术语来说，我有“C{00？？？？}{1？？？？？}{01？？？？}”的任何地方都是不可能的C类型子列表。我将用它来表示一个由3个或更多重复的单个数字组成的子列表。前两个7位字对数字进行编码（下面的“N”位），后跟零个或多个{0100001}字，后跟一个{0100000}字。

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

那只剩下只包含两个重复的单个数字的列表。我将用另一种不可能的C类型子列表模式表示那些列表：“C{0？？？？？？？}{11？？？？？}{10？？？？}”。前2个字中数字的7位有足够的空间，但这种模式比它表示的子列表长，这使得事情变得有点复杂。最后的五个问号可以被认为不是模式的一部分，所以我有：“C{0NNNNNN}{11N？？？？} 10”作为我的模式，要重复的数字存储在“N”中。那就太长了2位。

读取时，遇到“C{0NNNNN}{11N00AB} 10”，输出2个N中的数字实例，最后用A和B覆盖“10”，并将读取指针倒回2位。破坏性读取对该算法来说是可以的，因为每个紧凑列表只被遍历一次。

当写入包含2个重复的单个数字的子列表时，写入“C{0NNNNN} 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个子列表头出现计数和其他几个计数器、指针和我需要的小缓冲区，以及我没有注意到的空间，比如函数调用返回地址和局部变量的堆栈空间，这应该足够了。

第3部分，需要多长时间才能运行？

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

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

来源：

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

请参阅第一个正确答案或后一个带有算术编码的答案下面你可能会发现一些乐趣，但不是100%防弹的解决方案。

http://www.theeggeadventure.com/wikimedia/index.php/Java_Data_Compression

"我运行了一个测试来压缩一百万个连续整数，使用 各种形式的压缩。结果如下：“

None     4000027
Deflate  2006803
Filtered 1391833
BZip2    427067
Lzma     255040

看起来LZMA（Lempel-Ziv-Markov链算法）是一个不错的选择。我准备了一个简单的PoC，但仍有一些细节需要突出显示：

1. 内存是有限的，所以这个想法是预先排序数字并使用 压缩桶（动态大小）作为临时存储
2. 使用预排序更容易实现更好的压缩因子 数据，因此每个存储桶都有一个静态缓冲区（缓冲区中的数字要在LZMA之前排序）
3. 每个存储桶都有一个特定的范围，因此可以对其进行最终排序 每个桶单独
4. 可以正确设置Bucket的大小，因此将有足够的内存来 解压存储的数据并分别对每个存储桶进行最终排序

请注意，附件中的代码是一个POC，它不能用作最终解决方案，它只是演示了使用几个较小的缓冲区以某种最佳方式（可能是压缩的）存储预先排序的数字的想法。LZMA不是作为最终解决方案提出的。它被用作向该PoC引入压缩的最快方式。

请参阅下面的PoC代码（请注意，这只是一个演示，要编译它LZMA-Java将需要）：

public class MemorySortDemo {


static final int NUM_COUNT = 1000000;
static final int NUM_MAX   = 100000000;


static final int BUCKETS      = 5;
static final int DICT_SIZE    = 16 * 1024; // LZMA dictionary size
static final int BUCKET_SIZE  = 1024;
static final int BUFFER_SIZE  = 10 * 1024;
static final int BUCKET_RANGE = NUM_MAX / BUCKETS;


static class Producer {
private Random random = new Random();
public int produce() { return random.nextInt(NUM_MAX); }
}


static class Bucket {
public int size, pointer;
public int[] buffer = new int[BUFFER_SIZE];


public ByteArrayOutputStream tempOut = new ByteArrayOutputStream();
public DataOutputStream tempDataOut = new DataOutputStream(tempOut);
public ByteArrayOutputStream compressedOut = new ByteArrayOutputStream();


public void submitBuffer() throws IOException {
Arrays.sort(buffer, 0, pointer);


for (int j = 0; j < pointer; j++) {
tempDataOut.writeInt(buffer[j]);
size++;
}
pointer = 0;
}


public void write(int value) throws IOException {
if (isBufferFull()) {
submitBuffer();
}
buffer[pointer++] = value;
}


public boolean isBufferFull() {
return pointer == BUFFER_SIZE;
}


public byte[] compressData() throws IOException {
tempDataOut.close();
return compress(tempOut.toByteArray());
}


private byte[] compress(byte[] input) throws IOException {
final BufferedInputStream in = new BufferedInputStream(new ByteArrayInputStream(input));
final DataOutputStream out = new DataOutputStream(new BufferedOutputStream(compressedOut));


final Encoder encoder = new Encoder();
encoder.setEndMarkerMode(true);
encoder.setNumFastBytes(0x20);
encoder.setDictionarySize(DICT_SIZE);
encoder.setMatchFinder(Encoder.EMatchFinderTypeBT4);


ByteArrayOutputStream encoderPrperties = new ByteArrayOutputStream();
encoder.writeCoderProperties(encoderPrperties);
encoderPrperties.flush();
encoderPrperties.close();


encoder.code(in, out, -1, -1, null);
out.flush();
out.close();
in.close();


return encoderPrperties.toByteArray();
}


public int[] decompress(byte[] properties) throws IOException {
InputStream in = new ByteArrayInputStream(compressedOut.toByteArray());
ByteArrayOutputStream data = new ByteArrayOutputStream(10 * 1024);
BufferedOutputStream out = new BufferedOutputStream(data);


Decoder decoder = new Decoder();
decoder.setDecoderProperties(properties);
decoder.code(in, out, 4 * size);


out.flush();
out.close();
in.close();


DataInputStream input = new DataInputStream(new ByteArrayInputStream(data.toByteArray()));
int[] array = new int[size];
for (int k = 0; k < size; k++) {
array[k] = input.readInt();
}


return array;
}
}


static class Sorter {
private Bucket[] bucket = new Bucket[BUCKETS];


public void doSort(Producer p, Consumer c) throws IOException {


for (int i = 0; i < bucket.length; i++) {  // allocate buckets
bucket[i] = new Bucket();
}


for(int i=0; i< NUM_COUNT; i++) {         // produce some data
int value = p.produce();
int bucketId = value/BUCKET_RANGE;
bucket[bucketId].write(value);
c.register(value);
}


for (int i = 0; i < bucket.length; i++) { // submit non-empty buffers
bucket[i].submitBuffer();
}


byte[] compressProperties = null;
for (int i = 0; i < bucket.length; i++) { // compress the data
compressProperties = bucket[i].compressData();
}


printStatistics();


for (int i = 0; i < bucket.length; i++) { // decode & sort buckets one by one
int[] array = bucket[i].decompress(compressProperties);
Arrays.sort(array);


for(int v : array) {
c.consume(v);
}
}
c.finalCheck();
}


public void printStatistics() {
int size = 0;
int sizeCompressed = 0;


for (int i = 0; i < BUCKETS; i++) {
int bucketSize = 4*bucket[i].size;
size += bucketSize;
sizeCompressed += bucket[i].compressedOut.size();


System.out.println("  bucket[" + i
+ "] contains: " + bucket[i].size
+ " numbers, compressed size: " + bucket[i].compressedOut.size()
+ String.format(" compression factor: %.2f", ((double)bucket[i].compressedOut.size())/bucketSize));
}


System.out.println(String.format("Data size: %.2fM",(double)size/(1014*1024))
+ String.format(" compressed %.2fM",(double)sizeCompressed/(1014*1024))
+ String.format(" compression factor %.2f",(double)sizeCompressed/size));
}
}


static class Consumer {
private Set<Integer> values = new HashSet<>();


int v = -1;
public void consume(int value) {
if(v < 0) v = value;


if(v > value) {
throw new IllegalArgumentException("Current value is greater than previous: " + v + " > " + value);
}else{
v = value;
values.remove(value);
}
}


public void register(int value) {
values.add(value);
}


public void finalCheck() {
System.out.println(values.size() > 0 ? "NOT OK: " + values.size() : "OK!");
}
}


public static void main(String[] args) throws IOException {
Producer p = new Producer();
Consumer c = new Consumer();
Sorter sorter = new Sorter();


sorter.doSort(p, c);
}
}

对于随机数，它产生以下内容：

bucket[0] contains: 200357 numbers, compressed size: 353679 compression factor: 0.44
bucket[1] contains: 199465 numbers, compressed size: 352127 compression factor: 0.44
bucket[2] contains: 199682 numbers, compressed size: 352464 compression factor: 0.44
bucket[3] contains: 199949 numbers, compressed size: 352947 compression factor: 0.44
bucket[4] contains: 200547 numbers, compressed size: 353914 compression factor: 0.44
Data size: 3.85M compressed 1.70M compression factor 0.44

对于一个简单的升序序列（使用一个桶），它产生：

bucket[0] contains: 1000000 numbers, compressed size: 256700 compression factor: 0.06
Data size: 3.85M compressed 0.25M compression factor 0.06

编辑

结论：

1. 不要试图愚弄自然
2. 使用更简单的压缩和更低的内存占用
3. 确实需要一些额外的线索。普通的防弹解决方案似乎不可行。

阶段2：增强压缩，最终结论

正如上一节中已经提到的，可以使用任何合适的压缩技术。因此，让我们摆脱LZMA，转而采用更简单更好（如果可能的话）的方法。有很多很好的解决方案，包括算术编码、基数树等。

无论如何，简单但有用的编码方案将比另一个外部库更具说明性，提供一些漂亮的算法。实际的解决方案非常简单：由于存在包含部分排序数据的存储桶，因此可以使用增量而不是数字。

随机输入测试显示略好的结果：

bucket[0] contains: 10103 numbers, compressed size: 13683 compression factor: 0.34
bucket[1] contains: 9885 numbers, compressed size: 13479 compression factor: 0.34
...
bucket[98] contains: 10026 numbers, compressed size: 13612 compression factor: 0.34
bucket[99] contains: 10058 numbers, compressed size: 13701 compression factor: 0.34
Data size: 3.85M compressed 1.31M compression factor 0.34

示例代码

  public static void encode(int[] buffer, int length, BinaryOut output) {
short size = (short)(length & 0x7FFF);


output.write(size);
output.write(buffer[0]);


for(int i=1; i< size; i++) {
int next = buffer[i] - buffer[i-1];
int bits = getBinarySize(next);


int len = bits;


if(bits > 24) {
output.write(3, 2);
len = bits - 24;
}else if(bits > 16) {
output.write(2, 2);
len = bits-16;
}else if(bits > 8) {
output.write(1, 2);
len = bits - 8;
}else{
output.write(0, 2);
}


if (len > 0) {
if ((len % 2) > 0) {
len = len / 2;
output.write(len, 2);
output.write(false);
} else {
len = len / 2 - 1;
output.write(len, 2);
}


output.write(next, bits);
}
}
}


public static short decode(BinaryIn input, int[] buffer, int offset) {
short length = input.readShort();
int value = input.readInt();
buffer[offset] = value;


for (int i = 1; i < length; i++) {
int flag = input.readInt(2);


int bits;
int next = 0;
switch (flag) {
case 0:
bits = 2 * input.readInt(2) + 2;
next = input.readInt(bits);
break;
case 1:
bits = 8 + 2 * input.readInt(2) +2;
next = input.readInt(bits);
break;
case 2:
bits = 16 + 2 * input.readInt(2) +2;
next = input.readInt(bits);
break;
case 3:
bits = 24 + 2 * input.readInt(2) +2;
next = input.readInt(bits);
break;
}


buffer[offset + i] = buffer[offset + i - 1] + next;
}


return length;
}

请注意，这种方法：

1. 不会消耗大量内存
2. 适用于流
3. 没有那么糟糕的结果

可以找到完整的代码这里、BinaryInput和BinaryOutput实现这里

最后结论

没有最终结论：）有时，从元层次的角度向上移动一个级别并审查任务确实是个好主意。

花一些时间在这个任务上很有趣。顺便说一句，下面有很多有趣的答案。感谢您的关注和快乐编码。

如果输入流可以被接收几次，这会容易得多（没有关于这个的信息，想法和时间性能问题）。然后，我们可以计算十进制值。有了计数值，就很容易制作输出流。通过计算值来压缩。 这取决于输入流中的内容。

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

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

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

这个怎么样？

前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位：

• 00表示你没有看到数字。
• 01代表你见过一次
• 1表示您看到了它，接下来的26位是多少次的计数。

我认为这是有效的：如果没有重复，你有一个244k列表。 在最坏的情况下，你看到每个数字两次（如果你看到一个数字三次，它会缩短列表的其余部分），这意味着你已经看到50,000多次，你已经看到了950,000个项目0或1次。

5万*27+95万*2=396.7k。

如果您使用以下编码，则可以进行进一步改进：

0表示您没有看到数字 10代表你看过一次 第11章怎么算

平均而言，这将导致存储280.7k。

编辑：我周日早上的数学是错误的。

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

50万*27+50万*2=1.77M

交替编码导致平均存储

50万*27+50万=1.70M

问题：（

我会尝试基数树。如果您可以将数据存储在树中，那么您可以进行有序遍历来传输数据。

我不确定你是否可以将其放入1MB，但我认为值得一试。

如果数字均匀分布，我们可以使用计数排序。我们应该保留每个数字在数组中重复的次数。 可用空间为：1 MB-3 KB=1045504 B或8364032位 每个数字的位数=8364032/1000000=8 因此，我们可以存储每个数字重复的次数，最大值为2^8-1=255。 使用这种方法，我们有一个额外的364032位未使用，可用于处理数字重复超过255次的情况。例如，我们可以说数字255表示重复大于或等于255。在这种情况下，我们应该存储一系列数字+重复。我们可以处理7745种特殊情况，如下所示：

364032/（位需要表示每个数字+位需要表示100万）= 364032/（27+20）=7745

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

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

您可以通过以下方式对只有几个字节RAM的数字进行排序：

• 首先取两个变量：COUNTER和VALUE。
• 首先将所有寄存器设置为0；
• 每次收到整数I时，递增COUNTER并将VALUE设置为max(VALUE, I)；
• 然后向路由器发送一个数据设置为I的ICMP回声请求数据包。擦除I并重复。
• 每次收到返回的ICMP数据包时，只需提取整数并在另一个回显请求中再次将其发送回来。这会产生大量包含整数的向后和向前切换的ICMP请求。

一旦COUNTER到达1000000，您就可以将所有值存储在持续不断的ICMP请求流中，VALUE现在包含最大整数。选择一些threshold T >> 1000000。将COUNTER设置为零。每次收到ICMP数据包时，递增COUNTER并将包含的整数I发送回另一个回显请求，除非I=VALUE，在这种情况下将其传输到排序整数的目的地。一旦COUNTER=T，将VALUE减去10000000，将COUNTER重置为零并重复。一旦VALUE达到零，你应该按从大到小的顺序将所有整数传输到目标，并且只使用了大约47位的RAM用于两个持久变量（以及临时值所需的任何少量）。

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

在所有可能的输入中，这个问题只有一个解决方案：作弊。

1. 通过TCP读取m个值，其中m接近可以在内存中排序的最大值，可能是n/4。
2. 对250,000（左右）个数字进行排序并输出它们。
3. 重复其他三个季度。
4. 让接收器在处理它们时合并它收到的4个数字列表。（这并不比使用单个列表慢多少。）

由于ROM大小不计算，除了TCP缓冲区之外不需要任何额外的RAM。只需实现一个大的有限状态机。每个状态代表一组读入的数字。读取一百万个数字后，只需打印与达到的状态相对应的数字。

我有一台1M内存的电脑没有其他本地存储

另一种作弊的方法：你可以使用非本地（网络）存储（你的问题并不排除这一点），并调用一个网络服务，该服务可以使用简单的基于磁盘的合并排序（或足够的RAM来对内存进行排序，因为你只需要接受1M数字），而不需要已经给出的（公认非常巧妙的）解决方案。

这可能是作弊，但目前尚不清楚你是在寻找一个现实世界问题的解决方案，还是一个会导致规则弯曲的谜题……如果是后者，那么一个简单的作弊可能会比一个复杂但“真实”的解决方案（正如其他人所指出的，只能用于可压缩输入）获得更好的结果。

您使用的是哪种计算机？它可能没有任何其他“正常”本地存储，但它有视频RAM吗？例如，100万像素x每像素32位（例如）非常接近您所需的数据输入大小。

（我在很大程度上是为了纪念旧的橡子RISC PC，如果您选择低分辨率或低色深屏幕模式，它可以“借用”VRAM来扩展可用的系统RAM！）。这在只有几MB正常RAM的机器上相当有用。

假设这个任务是可能的。就在输出之前，将有一百万个排序数字的内存表示。有多少种不同的这种表示？由于可能会有重复的数字，我们不能使用nCr（选择），但是有一个名为多选的操作适用于多重集。

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

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

然而，如果“1MRAM”意味着一百万字节，那么显然没有足够的空间。增加5%的内存在理论上是可能的，这一事实表明这种表示必须非常有效，而且可能不合理。

在10^8的范围内有10^6个值，因此平均每一百个代码点有一个值。存储从第N个点到第（N+1）个点的距离。重复的值的跳过为0。这意味着跳过平均需要不到7位来存储，因此其中一百万个值将很乐意适合我们的800万位存储。

这些跳过需要被编码成比特流，比如通过Huffman编码。插入是通过迭代比特流并在新值之后重写。通过迭代并写出隐含值来输出。出于实用性，它可能希望像10^4列表一样完成，每个列表覆盖10^4个代码点（和平均100个值）。

一个好的随机数据哈夫曼树可以通过假设泊松分布（均值=方差=100）在跳过的长度上先验地构建，但真实的统计数据可以保留在输入上，并用于生成最佳树来处理病理病例。

我们可以玩网络堆栈，在我们拥有所有数字之前按排序顺序发送数字。如果您发送1M数据，TCP/IP将把它分成1500字节的数据包，并按顺序传输到目标。每个数据包将被赋予一个序列号。

我们可以手工完成。就在我们填满RAM之前，我们可以对我们拥有的内容进行排序并将列表发送给我们的目标，但在每个数字周围的序列中留下漏洞。然后使用序列中的这些孔以相同的方式处理第二个1/2个数字。

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

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

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

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

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

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

我希望你能利用您输入的特定领域知识找到一个足够好的整数压缩格式基于此。

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

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

谷歌的（坏）方法，来自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）

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

我的建议在很大程度上归功于丹的解决方案

首先，我假设解决方案必须处理所有可能的输入列表。我认为流行的答案没有做出这个假设（在我看来这是一个巨大的错误）。

众所周知，任何形式的无损压缩都不会减小所有输入的大小。

所有流行的答案都假设它们能够有效地应用压缩以允许它们额外的空间。事实上，一大块额外的空间足以以未压缩的形式容纳部分完成的列表的某些部分，并允许它们执行排序操作。这只是一个糟糕的假设。

对于这样的解决方案，任何了解如何进行压缩的人都可以设计一些不能很好地压缩该方案的输入数据，并且“解决方案”很可能会由于空间不足而中断。

相反，我采用数学方法。我们可能的输出是长度为LEN的所有列表，由0… MAX范围内的元素组成。这里的LEN是1,000,000，我们的MAX是100,000,000。

对于任意LEN和MAX，编码此状态所需的位数为：

Log2（最大多选LEN）

因此，对于我们的数字，一旦我们完成接收和排序，我们将需要至少Log2（100,000,000 MC 1,000,000）位来存储我们的结果，以唯一区分所有可能的输出。

所以我们实际上有足够的空间来保存我们的结果。从这个角度来看，这是可能的。

[删除了毫无意义的漫无边际，现在有更好的例子…]

最佳答案在这里。

另一个很好的答案在这里，基本上使用插入排序作为函数，将列表扩展一个元素（缓冲一些元素和预排序，允许一次插入多个元素，节省一点时间）。

我会利用TCP的重传行为。

1. 让TCP组件创建一个大的接收窗口。
2. 接收一定数量的数据包而不发送确认字符。
   • 处理传递中的那些创建一些（前缀）压缩数据结构
   • 为最后一个不再需要的数据包发送重复的ack/等待重传超时
   • Goto 2
3. 所有包裹都被接受了

这假设了桶或多次传递的某种好处。

可能是通过对批次/桶进行排序并合并它们。->基数树

使用此技术接受并排序前80%，然后读取最后20%，验证最后20%不包含会落在前20%的最低数字中的数字。然后发送20%的最低数字，从内存中删除，接受其余20%的新数字并合并。**

我认为从组合学的角度思考这个问题的一种方法是：有多少种可能的排序数顺序组合？如果我们给组合0,0,0，…，0代码0,0,0，…，1代码1，和99999999,99999999，…99999999代码N，N是什么？换句话说，结果空间有多大？

一种思考方式是注意到这是求N x M网格中单调路径数量问题的对偶，其中N=1,000,000，M=100,000,000。换句话说，如果你有一个宽1,000,000，高1,000,000的网格，从左下角到右上角有多少条最短路径？最短路径当然只需要你向右移动或向上移动（如果你向下移动或向左移动，你将取消之前完成的进度）。要了解这是我们的数字排序问题的对偶，请观察以下内容：

您可以将路径中的任何水平分支想象为排序中的数字，其中分支的Y位置表示值。

因此，如果路径只是向右一直移动到最后，然后一直跳到顶部，这相当于排序0,0,0，…，0。如果它从一直跳到顶部开始，然后向右移动1,000,000次，这相当于99999999,99999999，…，99999999。一条路径向右移动一次，然后向上移动一次，然后向右移动一次，然后向上移动一次，等等直到最后（然后必须一直跳到顶部），相当于0,1,2,3，…，999999。

幸运的是，这个问题已经解决了，这样的网格有（N+M）选择（M）路径：

（1,000,000+100,000,000）选择（100,000,000）~=2.27*10^2436455

因此，N等于2.27*10^2436455，因此代码0表示0,0,0，…，0，代码2.27*10^2436455和一些变化表示99999999,99999999，…，99999999。

为了存储从0到2.27*10^2436455的所有数字，您需要lg2（2.27*10^2436455）=8.0937*10^6位。

1兆字节=8388608位>8093700位

所以看起来我们至少有足够的空间来存储结果！当然，有趣的是在数字流入时进行排序。不确定最好的方法是给定我们剩下的294908位。我想一个有趣的技术是在每一点假设这是整个排序，找到该排序的代码，然后当你收到一个新数字时返回并更新以前的代码。手挥手。

现在的目标是一个实际的解决方案，涵盖8位范围内所有可能的输入情况，只有1MB的RAM。注意：半成品，明天将继续。使用排序整数的增量的算术编码，1M排序整数的最坏情况将花费每个条目约7位（因为99999999/1000000是99，而log2（99）几乎是7位）。

但是您需要对1m整数进行排序以达到7或8位！较短的系列将具有更大的增量，因此每个元素的位数更多。

我正在尽可能多地获取并（几乎）就地压缩。第一批接近250K的int最多需要大约9位。所以结果大约需要275KB。在剩余的空闲内存中重复几次。然后解压缩-合并-就地压缩那些压缩的块。这是相当困难，但我认为是可能的。

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

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

有志愿者吗？

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

我们在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'分隔，然后我认为我们可以保持差距表示足够短，但它需要更多的分析。

您必须最多计数99,999,999，并在此过程中指示1,000,000个站点。因此，可以使用经过解释的比特流，以便在1表示以增量方式增加计数器，0表示输出数字。如果流中的前8位是00110010，那么到目前为止我们将有0,0,2,2,3。

log(99,999,999 + 1,000,000) / log(2) = 26.59。您的内存中有2^28位。您只需要使用一半！

如果可以多次读取输入文件（你的问题陈述没有说不能），下面的方法应该可以。Benchley的书“Programming Perls”中对此进行了描述。如果我们将每个数字存储在8个字节中，我们可以将250,000个数字存储在1兆字节中。使用一个对输入文件进行40次遍历的程序。在第一次遍历时，它将0到249,999之间的任何整数读入内存，对（最多）250,000个整数进行排序并将它们写入输出文件。第二次遍历将整数从250,000到499,999进行排序，依此类推到第40次遍历，将9,750,000到9,999,999进行排序。

要表示排序数组，可以只存储第一个元素和相邻元素之间的差异。通过这种方式，我们关心的是编码10^6个元素，最多可以加起来10^8。让我们称之为D。要对D的元素进行编码，可以使用霍夫曼代码。可以随时随地创建霍夫曼代码的字典，并且每次在排序数组中插入新项（插入排序）时都会更新数组。请注意，当字典因新项而更改时，整个数组都应该更新以匹配新编码。

如果我们每个唯一元素的数量相等，则编码D每个元素的平均位数最大化。假设D中的元素d1、d2、…、dN每个都出现F次。在这种情况下（在最坏的情况下，我们的输入序列中既有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的情况。如果我们有di从0开始的连续数字，或者di=我-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个唯一值。

你只需要按顺序存储数字之间的差异，并使用编码来压缩这些序列号。我们有2^23位。我们将把它分成6bit块，并让最后一位指示该数字是否扩展到另外6位（5bit加上扩展块）。

因此，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+综述（10,000,000/2^5）*6+综述（10,000,000/2^10）*6+综述（10,000,000/2^15）*6+综述（10,000,000/2^20）*4=7935479。

2^24=8388608.由于8388608>7935479，我们应该很容易有足够的内存。当我们插入新数字时，我们可能还需要一点内存来存储where are的和。然后我们遍历序列，找到在哪里插入新数字，必要时减少下一个差，并正确移位之后的所有内容。

我认为解决方案是结合视频编码的技术，即离散余弦变换。在数字视频中，而不是将视频亮度或颜色的变化记录为常规值，例如110 112 115 116，每个值都从最后一个值中减去（类似于游程长度编码）。110 112 115 116变成110 2 3 1。这些值，2 3 1需要比原始值更少的位。

假设我们创建一个输入值到达套接字时的列表。我们存储在每个元素中，不是值，而是它之前的偏移量。我们边走边排序，所以偏移量只会是正数。但是偏移量可以是8位十进制数字宽，这适合3个字节。每个元素不能是3个字节，所以我们需要打包这些。我们可以使用每个字节的顶部位作为“继续位”，表示下一个字节是数字的一部分，每个字节的较低7位需要组合。零对重复有效。

当列表填满时，数字应该更接近，这意味着平均只有1个字节用于确定到下一个值的距离。7位值和1位偏移（如果方便的话），但可能有一个甜蜜点需要少于8位的“继续”值。

无论如何，我做了一些实验。我使用随机数生成器，我可以将一百万个排序的8位十进制数字拟合到大约1279000个字节中。每个数字之间的平均空间始终为99…

public class Test {
public static void main(String[] args) throws IOException {
// 1 million values
int[] values = new int[1000000];


// create random values up to 8 digits lrong
Random random = new Random();
for (int x=0;x<values.length;x++) {
values[x] = random.nextInt(100000000);
}
Arrays.sort(values);


ByteArrayOutputStream baos = new ByteArrayOutputStream();


int av = 0;
writeCompact(baos, values[0]);     // first value
for (int x=1;x<values.length;x++) {
int v = values[x] - values[x-1];  // difference
av += v;
System.out.println(values[x] + " diff " + v);
writeCompact(baos, v);
}


System.out.println("Average offset " + (av/values.length));
System.out.println("Fits in " + baos.toByteArray().length);
}


public static void writeCompact(OutputStream os, long value) throws IOException {
do {
int b = (int) value & 0x7f;
value = (value & 0x7fffffffffffffffl) >> 7;
os.write(value == 0 ? b : (b | 0x80));
} while (value != 0);
}
}

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

• 我们需要加载所有数字才能对它们进行排序，
• 数字的集合是不可压缩的。

如果这些假设成立，则无法执行您的任务，因为您将需要至少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的赔率对应于~0.08位/字符，总的~0.965 MiB几乎相同（在这种情况下，忽略依赖项的代价只有~12位！）。

存储具有已知先验概率的独立字符的最简单技术是哈夫曼编码。请注意，我们需要一棵不切实际的大树（一个包含10个字符的块的哈夫曼树，每个块的平均成本约为2.4位，总共约为2.9 Mib。一个包含20个字符的块的哈夫曼树，每个块的平均成本约为3位，总共约为1.8 MiB。我们可能需要一个大约100个大小的块，这意味着我们树中的节点比以往所有计算机设备所能存储的还要多。）。然而，根据问题，ROM在技术上是“免费的”，并且利用树中的规律性的实际解决方案看起来基本相同。

伪代码

• 在ROM中存储足够大的霍夫曼树（或类似的逐块压缩数据）
• 从10^8个“+”字符的压缩字符串开始。
• 要插入数字N，请流式输出压缩字符串，直到N个“+”字符过去，然后插入“！”。随时将重新压缩的字符串流式传输到前一个字符串上，保持恒定数量的缓冲块以避免过度/不足运行。
• 重复一百万次：[输入，流解压>插入>压缩]，然后解压到输出

你有没有试过转换成巫术？

我可以看到前后文件大小大幅减少；然后，使用空闲空间按部分工作。也许，再次转换为dec，order，hex，另一个块，转换为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

如果输入流可以被接收几次，这将是很多 更容易（没有关于这个，想法和时间性能问题的信息）。

然后，我们可以计算十进制值。有了计数值，它将是 容易使输出流。通过计算值进行压缩。它 这取决于输入流中的内容。

这是一些工作C++代码解决了这个问题。

内存约束满足的证明：

无论是在这篇文章中还是在他的博客中，都没有作者提供的最大内存需求的证明。由于编码一个值所需的位数取决于之前编码的值，这样的证明可能不是简单的。作者指出，他根据经验偶然发现的最大编码大小是1011732，并任意选择了缓冲区大小1013000。

typedef unsigned int u32;


namespace WorkArea
{
static const u32 circularSize = 253250;
u32 circular[circularSize] = { 0 };         // consumes 1013000 bytes


static const u32 stageSize = 8000;
u32 stage[stageSize];                       // consumes 32000 bytes


...

这两个数组总共占用1045000字节的存储空间。剩下的1048576-1045000-2×1024=1528字节用于剩余变量和堆栈空间。

它在我的Xeon W3520上运行大约23秒。您可以使用以下Python脚本验证程序是否有效，假设程序名称为sort1mb.exe。

from subprocess import *
import random


sequence = [random.randint(0, 99999999) for i in xrange(1000000)]


sorter = Popen('sort1mb.exe', stdin=PIPE, stdout=PIPE)
for value in sequence:
sorter.stdin.write('%08d\n' % value)
sorter.stdin.close()


result = [int(line) for line in sorter.stdout]
print('OK!' if result == sorted(sequence) else 'Error!')

算法的详细解释可以在以下系列帖子中找到：

• 1MB排序解释
• 算术编码和1MB排序问题
• 使用定点数学的算术编码

在接收流时执行这些步骤。

1、设置合理的块大小

伪代码想法：

1. 第一步是找到所有重复项，并将它们与计数一起放入字典并删除它们。
2. 第三步是将存在于算法步骤序列中的数字放入计数器特殊字典中，其中包含第一个数字和它们的步骤，例如n， n+1…， n+2,2n，2n+1,2n+2…
3. 开始在块中压缩一些合理的数字范围，例如每1000或曾经10000剩余的数字，这些数字出现的频率较低。
4. 如果找到一个数字，则解压该范围并将其添加到该范围中，并将其保持未压缩状态一段时间。
5. 否则，只需将该数字添加到一个字节[chunkSize]

接收流时继续前4步。最后一步是如果超出内存则失败，或者在收集到所有数据后开始输出结果，开始对范围进行排序并按顺序吐出结果，并按照需要解压缩的顺序解压缩并在到达它们时对它们进行排序。

这里是此类问题的通用解决方案：

一般程序

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

• 我们从填充上次迭代压缩数据的缓冲区开始。缓冲区如下所示

  |compressed sorted|empty|

• 计算此缓冲区中可以存储的最大数字量，包括压缩和未压缩的数字。将缓冲区分成这两个部分，从压缩数据的空间开始，以未压缩数据结束。缓冲区看起来像

  |compressed sorted|empty|empty|

• 用要排序的数字填充未压缩的部分。缓冲区看起来像

  |compressed sorted|empty|uncompressed unsorted|

• 使用就地排序对新数字进行排序。缓冲区看起来像

  |compressed sorted|empty|uncompressed sorted|

• 在压缩部分中对上一次迭代中任何已经压缩的数据进行右对齐。此时缓冲区被分区

  |empty|compressed sorted|uncompressed sorted|

• 对压缩部分执行流解压缩-重新压缩，合并未压缩部分中的排序数据。旧的压缩部分随着新压缩部分的增长而消耗。缓冲区看起来像

  |compressed sorted|empty|

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

压缩

当然，这种算法只有在实际知道实际压缩的内容之前，才可能计算新排序缓冲区的最终压缩大小时才有效。除此之外，压缩算法需要足够好才能解决实际问题。

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

然后将这些差异编码为一元比特流。此流中的A 1表示“向累加器添加1，A 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设置为量。

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

接下来，需要一些开销来存储记账数据并处理算术编码算法的定点近似中的轻微不准确性，但总的来说，即使有一个可以包含8000个数字的额外缓冲区，该算法也能够适应1MiB的空间，总共1043916字节的空间。

最优性

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