我有一台有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个数字列表。(这并不比使用单个列表慢多少。)
其他回答
If the numbers are evenly distributed we can use Counting sort. We should keep the number of times that each number is repeated in an array. Available space is: 1 MB - 3 KB = 1045504 B or 8364032 bits Number of bits per number= 8364032/1000000 = 8 Therefore, we can store the number of times each number is repeated to the maximum of 2^8-1=255. Using this approach we have an extra 364032 bits unused that can be used to handle cases where a number is repeated more than 255 times. For example we can say a number 255 indicates a repetition greater than or equal to 255. In this case we should store a sequence of numbers+repetitions. We can handle 7745 special cases as shown bellow:
364032/(表示每个数字所需的位数+表示100万所需的位数)= 364032 / (27+20)=7745
您只需要按顺序存储数字之间的差异，并使用编码来压缩这些序列号。我们有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，我们应该很容易有足够的内存。我们可能还需要一点内存来存储插入新数字时的和。然后我们遍历这个序列，找到插入新数字的位置，如果必要的话减少下一个差值，并将它之后的所有内容都右移。
如果我们对这些数字一无所知，我们就会受到以下约束:
我们需要在排序之前加载所有的数字， 这组数字是不可压缩的。
如果这些假设成立，则无法执行您的任务，因为您将需要至少26,575,425位的存储空间(3,321,929字节)。
你能跟我们说说你的数据吗?
在接收流时执行这些步骤。
首先设置一些合理的块大小
伪代码思想:
The first step would be to find all the duplicates and stick them in a dictionary with its count and remove them. The third step would be to place number that exist in sequence of their algorithmic steps and place them in counters special dictionaries with the first number and their step like n, n+1..., n+2, 2n, 2n+1, 2n+2... Begin to compress in chunks some reasonable ranges of number like every 1000 or ever 10000 the remaining numbers that appear less often to repeat. Uncompress that range if a number is found and add it to the range and leave it uncompressed for a while longer. Otherwise just add that number to a byte[chunkSize]
在接收流时继续执行前4步。最后一步是，如果超出内存，则失败，或者在收集完所有数据后开始输出结果，即开始对范围进行排序，并按顺序输出结果，然后按需要解压缩的顺序解压结果，并在得到它们时对它们进行排序。
我将利用TCP的重传行为。
让TCP组件创建一个大的接收窗口。 收到一定数量的包，但没有发送ACK。 处理这些传递，创建一些(前缀)压缩数据结构 对最后一个不再需要的数据包发送重复的ack /等待重传超时 转到2 所有数据包被接受
这假设了桶或多次传递的某种好处。
可能是通过对批次/桶进行排序并合并它们。->根树
使用这种技术接受并排序前80%，然后读取后20%，验证后20%不包含将落在最低数字的前20%的数字。然后发送最低的20%的数字，从内存中删除，接受剩下的20%的新数字并合并。**
