我有一台有1mb内存的电脑，没有其他本地存储。我必须使用它通过TCP连接接受100万个8位十进制数字，对它们进行排序，然后通过另一个TCP连接发送排序的列表。
数字列表可能包含重复的，我不能丢弃。代码将放在ROM中，所以我不需要从1 MB中减去我的代码的大小。我已经有了驱动以太网端口和处理TCP/IP连接的代码，它需要2 KB的状态数据，包括1 KB的缓冲区，代码将通过它读取和写入数据。这个问题有解决办法吗?
问答来源:
slashdot.org
cleaton.net
当前回答
由于ROM大小不计算，因此除了TCP缓冲区外，不需要任何额外的RAM。只需要实现一个大的有限状态机。每个状态表示读入的多组数字。在读取了一百万个数字之后，只需打印出与所达到的状态相对应的数字。
其他回答
(我原来的答案是错误的，对不起，数学不好，见下面的休息。)
这个怎么样?
前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
: (
我想试试基数树。如果可以将数据存储在树中，那么就可以执行顺序遍历来传输数据。
我不确定你是否能把它装进1MB，但我认为值得一试。
排序在这里是次要问题。正如其他人所说，仅仅存储整数是困难的，并且不能在所有输入上工作，因为每个数字需要27位。
我对此的看法是:只存储连续(排序)整数之间的差异，因为它们很可能很小。然后使用压缩方案，例如，每个输入数字增加2位，来编码数字存储在多少位上。 喜欢的东西:
00 -> 5 bits
01 -> 11 bits
10 -> 19 bits
11 -> 27 bits
在给定的内存限制内，应该能够存储相当数量的可能输入列表。如何选择压缩方案以使其在最大输入数量上工作的数学超出了我的范围。
我希望您能够利用输入的领域特定知识，在此基础上找到足够好的整数压缩方案。
哦，然后，当你收到数据时，你对那个排序的列表进行插入排序。
在10^8的范围内有10^6个值，所以平均每100个码点有一个值。存储第N个点到第(N+1)个点的距离。重复值的跳过值为0。这意味着跳跃平均需要7比特来存储，所以100万个跳跃将很适合我们的800万比特存储空间。
这些跳跃需要被编码成一个比特流，比如通过霍夫曼编码。插入是通过遍历比特流并在新值之后重写。通过遍历并写出隐含值来输出。出于实用性考虑，它可能被做成10^4个列表，每个列表包含10^4个代码点(平均100个值)。
随机数据的霍夫曼树可以通过假设跳跃长度上的泊松分布(均值=方差=100)先验地构建，但可以在输入上保留真实的统计数据，并用于生成处理病理病例的最佳树。
现在的目标是一个实际的解决方案，覆盖所有可能的情况下，输入在8位数范围内，只有1MB的RAM。注:工作正在进行中，明天继续。使用对已排序整型的增量进行算术编码，对于1M个已排序整型，最坏的情况是每个条目花费大约7位(因为99999999/1000000是99，而log2(99)几乎是7位)。
但是你需要将1m个整数排序到7位或8位!级数越短，delta就越大，因此每个元素的比特数就越多。
我正在努力尽可能多地压缩(几乎)在原地。第一批接近250K的整数最多每个需要大约9位。因此结果大约需要275KB。重复使用剩余的空闲内存几次。然后解压缩-就地合并-压缩这些压缩块。这很难，但也是可能的。我认为。
合并后的列表将越来越接近每整数7位的目标。但是我不知道合并循环需要多少次迭代。也许3。
但是算术编码实现的不精确性可能使它不可能实现。如果这个问题是可能的，它将是非常紧张的。
有志愿者吗?
