COUNTER和VALUE。
2. 首先将所有寄存器设置为0；
3. 每次接收到整数I时，增加COUNTER并将VALUE设置为max(VALUE, I)；
4. 然后发送一个数据设置为I的ICMP回显请求包到路由器。删除I并重复此过程。
5. 每次接收到返回的ICMP数据包时，您只需要提取整数并再次在另一个回显请求中发送它。这会产生大量来回穿梭的ICMP请求，其中包含整数。COUNTER达到1000000，您就可以通过不断的ICMP请求获得所有值，并且VALUE现在包含最大的整数。选择一些threshold T >> 1000000，将COUNTER设置为零。每次接收到ICMP数据包时，增加COUNTER并将包含的整数I发送回另一个回显请求中，除非I=VALUE，在这种情况下将其传输到排序后的整数目标。一旦COUNTER=T，将VALUE减少1，将COUNTER重置为零并重复此过程。一旦VALUE达到零，您应该已经按从大到小的顺序传输了所有整数到目标，并且只使用了约47位RAM来存储两个持久变量（以及任何需要的少量临时值）。这里有一些可行的 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!')
这个算法的详细解释可以在以下一系列文章中找到：
(n+m)!/(n!m!)），所以你一定是正确的。也许我的估计是一个差值需要b位来存储，实际上显然差值为0时并不需要0位来存储。” - Ben Jackson让我们先解决压缩问题。已经有一些相关测试可用：
http://www.theeggeadventure.com/wikimedia/index.php/Java_Data_Compression
“我进行了一项测试，使用各种压缩方式对一百万个连续整数进行压缩。结果如下：”None 4000027
Deflate 2006803
Filtered 1391833
BZip2 427067
Lzma 255040
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
编辑
结论：
第二阶段：增强型压缩，最终结论
如前一节所述，可以使用任何适合的压缩技术。因此，我们可以放弃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;
}
完整代码可以在这里找到，BinaryInput和BinaryOutput实现可以在这里找到。
最终结论
没有最终结论 :) 有时候从元级别的角度审视任务是一个非常好的想法。
花费一些时间来完成这个任务很有趣。顺便说一下，下面有很多有趣的答案。感谢您的关注，祝您编程愉快。
只因1兆字节和100万字节之间的差异，才有此解决方案。有约2的8093729.5次方种选择1百万个8位数字（允许重复且顺序不重要）的不同方式，因此只拥有1百万字节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兆字节。
4个可能的子列表头值如下：
00 空的子列表，没有后续内容。
01 单元素列表，子列表中只有一个条目，下一个7位存储该条目。
10 子列表至少包含2个不同的数字。这些条目以非递减的顺序存储，但最后一个条目小于或等于第一个条目。这样可以识别子列表的结尾。例如，数字2、4、6将存储为（4,6,2）。数字2、2、3、4、4将存储为（2,3,4,4,2）。
11 子列表包含两个或更多个单个数字的重复。下一个7位给出了该数字。然后是零个或多个带有值1的7位条目，后跟一个具有值0的7位条目。子列表主体的长度规定了重复次数。例如，数字12、12将存储为（12,0），数字12、12、12将存储为（12,1,0），数字12、12、12、12将存储为（12,1,1,0）等等。
我从空列表开始，读入一堆数字并将它们存储为32位整数，原地排序新数字（可能使用堆排序），然后将它们合并到一个新的紧凑排序列表中。重复此操作，直到没有更多的数字可读取，然后再次遍历紧凑列表以生成输出。
下面的行表示在列表合并操作开始之前的内存状态。 "O"是保存已排序的32位整数的区域。 "X"是保存旧紧凑列表的区域。 "="表示用于紧凑列表的扩展空间，每个“O”中有7位整数。 "Z"是其他随机开销。
ZZZOOOOOOOOOOOOOOOOOOOOOOOOOO==========XXXXXXXXXXXXXXXXXXXXXXXXXX
合并例程从最左边的“O”和最左边的“X”开始读取，并从最左边的“=”开始写入。直到合并所有新整数，写指针才会捕捉到紧凑列表读取指针，因为两个指针对于每个子列表前进2位并且对于旧紧凑列表中的每个条目前进7位，并且有足够的额外空间用于新数字的7位条目。
第二部分，把它压缩成1M
为了将上述解决方案压缩到1M，我需要使紧凑列表格式更加紧凑。我会摆脱其中一种子列表类型，这样就只有3种不同的可能的子列表头值了。然后我可以使用“00”，“01”和“1”作为子列表头值并节省一些位。子列表类型是：
A 空的子列表，没有任何内容跟随。
B 单例，子列表中只有一个条目，下一个7位保存它。
C 子列表至少包含2个不同的数字。 条目按非递减顺序存储，除了最后一个条目小于或等于第一个条目。这允许确定子列表的末尾。例如，数字2,4,6将存储为（4,6,2）。数字2,2,3,4,4将存储为（2,3,4,4,2）。
D 子列表由单个数字的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.
这里只剩下只包含单个数字2次重复的列表。我将使用另一个不可能的C类型子列表模式表示它们："C{0??????}{11?????}{10?????}"。前两个字中有足够空间存储7位数字，但是该模式比所表示的子列表更长，这使得事情变得有些复杂。末尾的五个问号可以被认为不是模式的一部分，因此我的模式为："C{0NNNNNN}{11N????}10"，其中要重复的数字存储在“N”中。这多出了2位。
我需要借用2位，并从该模式中未使用的4位中归还它们。在读取时，当遇到“C{0NNNNNN}{11N00AB}10”时，输出“N”中的2个实例，用A和B位覆盖末尾的“10”，并将读指针向后退回2位。对于这个算法来说，破坏性读取是可以的，因为每个紧凑列表只被处理一次。
在写入单个数字2次重复的子列表时，写入“C{0NNNNNN}11N00”，并将借用的位计数器设置为2。在借用位计数器非零的每次写入时，每写入1位就会减少1，当计数器达到零时，写入“10”。因此，接下来写入的2位将进入A和B位，然后“10”将被放置在末尾。
对于3个子列表头值，我使用“00”、“01”和“1”，并将“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
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字节来完全填充紧凑列表，那么剩下的空间是8764-4096 = 4668字节来存储内存映射中的“Z”。
对于10个子列表头映射表、30个子列表头出现计数和其他少量计数器、指针和小缓冲区，应该足够了。还有一些被用作函数调用返回地址和本地变量堆栈空间等我没有注意到的空间。
第三部分，需要多长时间才能运行？
使用空紧凑列表时，1位列表头将用于一个空子列表，并且列表的起始大小将为781250位。在最坏的情况下，列表每增加一个数字就会增长8位，因此每个32位数字需要40位的自由空间放置在列表缓冲区顶部，然后进行排序和合并。在最坏的情况下，更改子列表头映射会导致2 * 781250 + 7 * entries - 781250 / 3位的空间使用率。
采用在列表中有至少800000个数字之后每五次合并更改子列表头映射的策略，最坏情况下运行将涉及大约30M的紧凑列表读写活动。
来源：
Gilmanov的答案在假设上非常错误。它基于一百万个连续整数的一个无意义的度量进行推测。这意味着没有间隙。然而，那些随机间隙，即使很小，也会使它成为一个糟糕的想法。
自己试试。获取1百万个随机的27位整数、排序、用7-Zip、xz或任何LZMA压缩，结果超过1.5 MB。前提是对连续数字的压缩。即使delta编码也需要超过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
我认为从组合学的角度来看，可以考虑有多少可能的排序数列组合？如果我们给定了组合0,0,0,...,0对应的码为0，组合0,0,0,...,1对应的码为1，以及组合99999999, 99999999, ... 99999999对应的码为N，则N是多少？换句话说，结果空间有多大？
那么，一种思考这个问题的方式是注意到这是一个双射函数问题，即在 N × M 的网格中找到单调路径的数量，其中 N = 1,000,000，M = 100,000,000。换句话说，如果你有一个宽为1,000,000和高为100,000,000的网格，从左下角到右上角有多少最短路径？当然，最短路径要求您只能向右或向上移动（如果向下或向左移动，您将会撤销之前完成的进展）。为了看到这是我们数字排序问题的双射函数，观察以下内容：
你可以将路径中任何水平段想象为排序中的数字，其中该段的Y位置表示值。
因此，如果路径简单地向右移动到末尾，然后一路跳到顶部，那相当于排序0,0,0,...,0。如果它开始跳到顶部，然后向右移动1,000,000次，那就相当于99999999,99999999,..., 99999999。一条路径先向右移动一次，然后向上移动一次，再向右移动一次，再向上移动一次，以此类推直到末尾（然后必须跳到顶部），相当于排序0,1,2,3,...,999999。
幸运的是，这个问题已经解决了，这样的网格有(N + M) Choose (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位。我想一个有趣的技术是在每个点上假设那是整个排序，找到该排序的代码，然后在接收到新数字时返回并更新先前的代码。挥手挥手。
在这里，我的建议借鉴了Dan的解决方案。
首先，我假设该解决方案必须处理所有可能的输入列表。我认为流行的答案并没有做出这个假设（在我看来这是一个巨大的错误）。
众所周知，无损压缩的形式将不能减小所有输入的大小。
所有流行的答案都假定他们能够应用足够有效的压缩来为他们提供额外的空间。实际上，需要足够大的额外空间以未压缩形式保存部分完成的列表，并允许它们执行排序操作。这只是一个糟糕的假设。
对于这样的解决方案，任何了解它们如何进行压缩的人都能够设计一些不适合此方案的输入数据，因此“解决方案”最有可能因为用尽空间而失败。
相反，我采用数学方法。我们的可能输出是长度为LEN，由范围为0..MAX中的元素组成的所有列表。这里LEN为1,000,000，MAX为100,000,000。
对于任意LEN和MAX，编码此状态所需的位数为：
Log2（MAX Multichoose LEN）
因此，对于我们的数字，一旦我们完成接收和排序，我们将需要至少Log2（100,000,000 MC 1,000,000）位来以可以唯一地区分所有可能的输出的方式存储我们的结果。
这是约等于988kb。因此，我们实际上有足够的空间来保存我们的结果。从这个角度来看，它是可能的。
[删除了毫无意义的胡言乱语，现在有更好的示例...]
最佳答案在这里。
另一个很好的答案在这里，基本上使用插入排序作为将列表扩展一个元素的函数（缓冲一些元素并进行预排序，以允许一次性插入多个元素，节省了一些时间）。还使用了一个漂亮而紧凑的状态编码，七位增量的桶。
这样怎么样？
前27位存储你见过的最小数字，然后是下一个数字与它的差，编码如下：使用5位存储差值所需的位数，然后是差值。使用00000表示再次看到该数字。
这种方法可行的原因是随着插入更多数字，数字之间的平均差值会降低，因此添加更多数字时，用于存储差异的位数也会减少。我相信这被称为增量列表。
我能想到的最坏情况是所有数字等间距（间隔100），例如假设0是第一个数字：
000000000000000000000000000 00111 1100100
^^^^^^^^^^^^^
a million times
27 + 1,000,000 * (5+7) bits = ~ 427k
对于所有可能的输入，有一个解决方案。作弊。