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

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

问答来源:

slashdot.org

cleaton.net


当前回答

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

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

其他回答

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

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

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

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

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

如果输入流可以接收几次,这将是很大的 更简单(没有关于这方面的信息,想法和时间-性能问题)。

然后,我们可以数小数。如果是计数值的话 容易使输出流。通过计算值来压缩。它 这取决于输入流中的内容。

如果数字的范围是有限的(只能有2个8位数,或者只有10个不同的8位数),那么你可以编写一个优化的排序算法。但如果你想对所有可能的8位数进行排序,这在内存那么少的情况下是不可能的。

假设这个任务是可能的。在输出之前,内存中会有一个百万个排序数字的表示。有多少种不同的表示法?由于可能有重复的数字,我们不能使用nCr(选择),但有一种叫做multichoose的操作,它适用于多集。

在0..99,999,999范围内有22e2436455种方法来选择一百万个数字。 这需要8,093,730位来表示每个可能的组合,或1,011,717字节。

所以理论上是可能的,如果你能想出一个合理(足够)的数字排序表。例如,一个疯狂的表示可能需要一个10MB的查找表或数千行代码。

但是,如果“1M RAM”意味着100万个字节,那么显然没有足够的空间。事实上,多5%的内存使它在理论上成为可能,这对我来说意味着表示必须非常有效,可能是不理智的。