我有一台有1mb内存的电脑，没有其他本地存储。我必须使用它通过TCP连接接受100万个8位十进制数字，对它们进行排序，然后通过另一个TCP连接发送排序的列表。
数字列表可能包含重复的，我不能丢弃。代码将放在ROM中，所以我不需要从1 MB中减去我的代码的大小。我已经有了驱动以太网端口和处理TCP/IP连接的代码，它需要2 KB的状态数据，包括1 KB的缓冲区，代码将通过它读取和写入数据。这个问题有解决办法吗?
问答来源:
slashdot.org
cleaton.net
当前回答
我想试试基数树。如果可以将数据存储在树中，那么就可以执行顺序遍历来传输数据。
我不确定你是否能把它装进1MB，但我认为值得一试。
其他回答
如果我们对这些数字一无所知，我们就会受到以下约束:
我们需要在排序之前加载所有的数字， 这组数字是不可压缩的。
如果这些假设成立，则无法执行您的任务，因为您将需要至少26,575,425位的存储空间(3,321,929字节)。
你能跟我们说说你的数据吗?
谷歌的(坏)方法，从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)
谷歌的方法既不值得(缓慢)，也不正确。但要为他们辩护，他们的问题可能略有不同。
如果输入流可以接收几次，这就容易多了(没有关于这方面的信息，想法和时间性能问题)。然后，我们可以数小数。有了计数值，就很容易生成输出流。通过计算值来压缩。 这取决于输入流中的内容。
您只需要按顺序存储数字之间的差异，并使用编码来压缩这些序列号。我们有2^23位。我们将它分成6位块，让最后一位表示这个数字是否扩展到另外6位(5位加上扩展块)。
因此，000010是1,000100是2。000001100000表示128。现在，我们考虑用最坏的类型来表示不超过10,000,000的数字序列的差异。可能有10000000 /2^5的差异大于2^5,10000000 /2^10的差异大于2^10,10000000 /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，我们应该很容易有足够的内存。我们可能还需要一点内存来存储插入新数字时的和。然后我们遍历这个序列，找到插入新数字的位置，如果必要的话减少下一个差值，并将它之后的所有内容都右移。
如果输入流可以接收几次，这将是很大的 更简单(没有关于这方面的信息，想法和时间-性能问题)。
然后，我们可以数小数。如果是计数值的话 容易使输出流。通过计算值来压缩。它 这取决于输入流中的内容。
