我有一台有1mb内存的电脑，没有其他本地存储。我必须使用它通过TCP连接接受100万个8位十进制数字，对它们进行排序，然后通过另一个TCP连接发送排序的列表。
数字列表可能包含重复的，我不能丢弃。代码将放在ROM中，所以我不需要从1 MB中减去我的代码的大小。我已经有了驱动以太网端口和处理TCP/IP连接的代码，它需要2 KB的状态数据，包括1 KB的缓冲区，代码将通过它读取和写入数据。这个问题有解决办法吗?
问答来源:
slashdot.org
cleaton.net
当前回答
在所有可能的输入中，这个问题只有一个解决方案。作弊。
通过TCP读取m个值，其中m接近内存中可排序的最大值，可能是n/4。 对250,000(大约)个数字进行排序并输出。 重复做另外3个四分之三。 让接收方在处理时合并接收到的4个数字列表。(这并不比使用单个列表慢多少。)
其他回答
基数树表示可以接近于处理这个问题，因为基数树利用了“前缀压缩”的优势。但是很难想象一个基树表表法可以在一个字节中表示单个节点——两个可能是极限。
但是，不管数据是如何表示的，一旦它被排序，它就可以以前缀压缩的形式存储，其中数字10、11和12将由001b、001b、001b表示，表示从前一个数字增加1。那么，也许10101b表示增量5,1101001b表示增量9，以此类推。
(我原来的答案是错误的，对不起，数学不好，见下面的休息。)
这个怎么样?
前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
: (
现在的目标是一个实际的解决方案，覆盖所有可能的情况下，输入在8位数范围内，只有1MB的RAM。注:工作正在进行中，明天继续。使用对已排序整型的增量进行算术编码，对于1M个已排序整型，最坏的情况是每个条目花费大约7位(因为99999999/1000000是99，而log2(99)几乎是7位)。
但是你需要将1m个整数排序到7位或8位!级数越短，delta就越大，因此每个元素的比特数就越多。
我正在努力尽可能多地压缩(几乎)在原地。第一批接近250K的整数最多每个需要大约9位。因此结果大约需要275KB。重复使用剩余的空闲内存几次。然后解压缩-就地合并-压缩这些压缩块。这很难，但也是可能的。我认为。
合并后的列表将越来越接近每整数7位的目标。但是我不知道合并循环需要多少次迭代。也许3。
但是算术编码实现的不精确性可能使它不可能实现。如果这个问题是可能的，它将是非常紧张的。
有志愿者吗?
如果输入流可以接收几次，这就容易多了(没有关于这方面的信息，想法和时间性能问题)。然后，我们可以数小数。有了计数值，就很容易生成输出流。通过计算值来压缩。 这取决于输入流中的内容。
排序在这里是次要问题。正如其他人所说，仅仅存储整数是困难的，并且不能在所有输入上工作，因为每个数字需要27位。
我对此的看法是:只存储连续(排序)整数之间的差异，因为它们很可能很小。然后使用压缩方案，例如，每个输入数字增加2位，来编码数字存储在多少位上。 喜欢的东西:
00 -> 5 bits
01 -> 11 bits
10 -> 19 bits
11 -> 27 bits
在给定的内存限制内，应该能够存储相当数量的可能输入列表。如何选择压缩方案以使其在最大输入数量上工作的数学超出了我的范围。
我希望您能够利用输入的领域特定知识，在此基础上找到足够好的整数压缩方案。
哦，然后，当你收到数据时，你对那个排序的列表进行插入排序。
