我有一台有1mb内存的电脑,没有其他本地存储。我必须使用它通过TCP连接接受100万个8位十进制数字,对它们进行排序,然后通过另一个TCP连接发送排序的列表。

数字列表可能包含重复的,我不能丢弃。代码将放在ROM中,所以我不需要从1 MB中减去我的代码的大小。我已经有了驱动以太网端口和处理TCP/IP连接的代码,它需要2 KB的状态数据,包括1 KB的缓冲区,代码将通过它读取和写入数据。这个问题有解决办法吗?

问答来源:

slashdot.org

cleaton.net


当前回答

由于ROM大小不计算,因此除了TCP缓冲区外,不需要任何额外的RAM。只需要实现一个大的有限状态机。每个状态表示读入的多组数字。在读取了一百万个数字之后,只需打印出与所达到的状态相对应的数字。

其他回答

如果输入流可以接收几次,这就容易多了(没有关于这方面的信息,想法和时间性能问题)。然后,我们可以数小数。有了计数值,就很容易生成输出流。通过计算值来压缩。 这取决于输入流中的内容。

我们可以利用网络堆栈,在我们得到所有数字之前,按顺序发送数字。如果你发送1M的数据,TCP/IP会把它分解成1500字节的数据包,并按照目标发送。每个包将被赋予一个序列号。

我们可以用手来做。在填满内存之前,我们可以对现有的数据进行排序,并将列表发送给目标,但在每个数字周围的序列中留下空洞。然后用同样的方法处理第二个1/2的数字,使用序列中的这些洞。

远端的网络堆栈将按顺序组装结果数据流,然后将其提交给应用程序。

它使用网络来执行归并排序。这是一个完全的黑客,但我是受到之前列出的其他网络黑客的启发。

如果我们对这些数字一无所知,我们就会受到以下约束:

我们需要在排序之前加载所有的数字, 这组数字是不可压缩的。

如果这些假设成立,则无法执行您的任务,因为您将需要至少26,575,425位的存储空间(3,321,929字节)。

你能跟我们说说你的数据吗?

To represent the sorted array one can just store the first element and the difference between adjacent elements. In this way we are concerned with encoding 10^6 elements that can sum up to at most 10^8. Let's call this D. To encode the elements of D one can use a Huffman code. The dictionary for the Huffman code can be created on the go and the array updated every time a new item is inserted in the sorted array (insertion sort). Note that when the dictionary changes because of a new item the whole array should be updated to match the new encoding.

如果每个唯一元素的数量相等,则编码D中每个元素的平均比特数将最大化。比如元素d1 d2…, dN在D中各出现F次。在这种情况下(最坏的情况是输入序列中同时有0和10^8)我们有

sum(1<=i<=N) F. di = 10^8

在哪里

sum(1<=i<=N) F=10^6,或F=10^6/N,归一化频率将是p= F/10^=1/N

平均比特数为-log2(1/P) = log2(N)。在这种情况下,我们应该找到使n最大化的情况,这发生在di从0开始的连续数,或者di= i-1时

10 ^ 8 =(1 < =我< = N) f . di =(1 < =我< = N) (10 ^ 6 / N)(张)= (10 ^ 6 / N) N (N - 1) / 2

i.e.

N <= 201。在这种情况下,平均比特数是log2(201)=7.6511,这意味着我们将需要大约1字节的每个输入元素来保存排序的数组。注意,这并不意味着D一般不能有超过201个元素。它只是说明,如果D的元素是均匀分布的,那么D的唯一值不可能超过201个。

你最多要数到99,999,999,并在沿途标明1,000,000个站点。因此,可以使用位流进行解释,即1表示递增计数器,0表示输出数字。如果流中的前8位是00110010,到目前为止我们将有0,0,2,2,3。

Log (99,999,999 + 1,000,000) / Log(2) = 26.59。你的内存中有2^28位。你只需要用一半!