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

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

问答来源:

slashdot.org

cleaton.net


当前回答

我将利用TCP的重传行为。

让TCP组件创建一个大的接收窗口。 收到一定数量的包,但没有发送ACK。 处理这些传递,创建一些(前缀)压缩数据结构 对最后一个不再需要的数据包发送重复的ack /等待重传超时 转到2 所有数据包被接受

这假设了桶或多次传递的某种好处。

可能是通过对批次/桶进行排序并合并它们。->根树

使用这种技术接受并排序前80%,然后读取后20%,验证后20%不包含将落在最低数字的前20%的数字。然后发送最低的20%的数字,从内存中删除,接受剩下的20%的新数字并合并。**

其他回答

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

If it is possible to read the input file more than once (your problem statement doesn't say it can't), the following should work. It is described in Benchley's book "Programming Perls." If we store each number in 8 bytes we can store 250,000 numbers in one megabyte. Use a program that makes 40 passes over the input file. On the first pass it reads into memory any integer between 0 and 249,999, sorts the (at most) 250,000 integers and writes them to the output file. The second pass sorts the integers from 250,000 to 499,999 and so on to the 40th pass, which sorts 9,750,000 to 9,999,999.

我有一台有1M内存的电脑,没有其他本地存储

另一种作弊方法:你可以使用非本地(网络)存储代替(你的问题不排除这一点),调用一个网络服务,它可以使用直接的基于磁盘的归并排序(或者只需要足够的RAM来在内存中排序,因为你只需要接受1M的数字),而不需要(公认非常巧妙的)已经给出的解决方案。

这可能是作弊,但不清楚你是在寻找一个现实问题的解决方案,还是一个让人扭曲规则的谜题……如果是后者,那么简单的欺骗可能比复杂但“真实”的解决方案(正如其他人指出的那样,后者只能用于可压缩输入)得到更好的结果。

下面是这类问题的一般解决方案:

一般程序

所采取的方法如下。该算法在一个32位字的缓冲区上操作。它在循环中执行以下过程:

We start with a buffer filled with compressed data from the last iteration. The buffer looks like this |compressed sorted|empty| Calculate the maximum amount of numbers that can be stored in this buffer, both compressed and uncompressed. Split the buffer into these two sections, beginning with the space for compressed data, ending with the uncompressed data. The buffer looks like |compressed sorted|empty|empty| Fill the uncompressed section with numbers to be sorted. The buffer looks like |compressed sorted|empty|uncompressed unsorted| Sort the new numbers with an in-place sort. The buffer looks like |compressed sorted|empty|uncompressed sorted| Right-align any already compressed data from the previous iteration in the compressed section. At this point the buffer is partitioned |empty|compressed sorted|uncompressed sorted| Perform a streaming decompression-recompression on the compressed section, merging in the sorted data in the uncompressed section. The old compressed section is consumed as the new compressed section grows. The buffer looks like |compressed sorted|empty|

执行此过程,直到所有数字都已排序。

压缩

当然,这种算法只有在知道实际要压缩什么之前,才有可能计算出新排序缓冲区的最终压缩大小。其次,压缩算法需要足够好来解决实际问题。

所使用的方法使用三个步骤。首先,算法将始终存储排序序列,因此我们可以只存储连续条目之间的差异。每个差值都在[0,99999999]的范围内。

这些差异随后被编码为一元比特流。这个流中的1表示“向累加器添加1,0表示“将累加器作为一个条目发出,并重置”。所以差N由N个1和1个0表示。

所有差异的和将接近算法支持的最大值,所有差异的计数将接近算法中插入的值的数量。这意味着我们期望流在最后包含最大值1和计数0。这允许我们计算流中0和1的期望概率。即,0的概率为count/(count+maxval), 1的概率为maxval/(count+maxval)。

我们使用这些概率来定义这个比特流上的算术编码模型。这个算术代码将在最佳空间中精确地编码1和0的数量。我们可以计算该模型对于任何中间位流所使用的空间:bits = encoded * log2(1 + amount / maxval) + maxval * log2(1 + maxval / amount)。若要计算算法所需的总空间,请将encoded设置为amount。

为了不需要大量的迭代,可以向缓冲区添加少量开销。这将确保算法将至少对适合这个开销的数量进行操作,因为到目前为止,算法最大的时间成本是每个周期的算术编码压缩和解压缩。

除此之外,在算术编码算法的定点近似中,存储簿记数据和处理轻微的不准确性是需要一些开销的,但总的来说,即使使用可以包含8000个数字的额外缓冲区,该算法也能够容纳1MiB的空间,总共1043916字节的空间。

最优

除了减少算法的开销外,理论上不可能得到更小的结果。为了仅仅包含最终结果的熵,1011717个字节是必要的。如果我们减去为提高效率而增加的额外缓冲区,该算法使用1011916字节来存储最终结果+开销。

你用的是哪种电脑?它可能没有任何其他“正常”的本地存储,但它是否有视频RAM,例如?100万像素x每像素32位(比如说)非常接近你所需的数据输入大小。

(我主要是问旧的Acorn RISC PC的内存,如果你选择低分辨率或低颜色深度的屏幕模式,它可以“借用”VRAM来扩展可用的系统RAM !)这在只有几MB普通RAM的机器上非常有用。