我有一台有1mb内存的电脑,没有其他本地存储。我必须使用它通过TCP连接接受100万个8位十进制数字,对它们进行排序,然后通过另一个TCP连接发送排序的列表。
数字列表可能包含重复的,我不能丢弃。代码将放在ROM中,所以我不需要从1 MB中减去我的代码的大小。我已经有了驱动以太网端口和处理TCP/IP连接的代码,它需要2 KB的状态数据,包括1 KB的缓冲区,代码将通过它读取和写入数据。这个问题有解决办法吗?
问答来源:
slashdot.org
cleaton.net
我有一台有1mb内存的电脑,没有其他本地存储。我必须使用它通过TCP连接接受100万个8位十进制数字,对它们进行排序,然后通过另一个TCP连接发送排序的列表。
数字列表可能包含重复的,我不能丢弃。代码将放在ROM中,所以我不需要从1 MB中减去我的代码的大小。我已经有了驱动以太网端口和处理TCP/IP连接的代码,它需要2 KB的状态数据,包括1 KB的缓冲区,代码将通过它读取和写入数据。这个问题有解决办法吗?
问答来源:
slashdot.org
cleaton.net
当前回答
现在的目标是一个实际的解决方案,覆盖所有可能的情况下,输入在8位数范围内,只有1MB的RAM。注:工作正在进行中,明天继续。使用对已排序整型的增量进行算术编码,对于1M个已排序整型,最坏的情况是每个条目花费大约7位(因为99999999/1000000是99,而log2(99)几乎是7位)。
但是你需要将1m个整数排序到7位或8位!级数越短,delta就越大,因此每个元素的比特数就越多。
我正在努力尽可能多地压缩(几乎)在原地。第一批接近250K的整数最多每个需要大约9位。因此结果大约需要275KB。重复使用剩余的空闲内存几次。然后解压缩-就地合并-压缩这些压缩块。这很难,但也是可能的。我认为。
合并后的列表将越来越接近每整数7位的目标。但是我不知道合并循环需要多少次迭代。也许3。
但是算术编码实现的不精确性可能使它不可能实现。如果这个问题是可能的,它将是非常紧张的。
有志愿者吗?
其他回答
在10^8的范围内有10^6个值,所以平均每100个码点有一个值。存储第N个点到第(N+1)个点的距离。重复值的跳过值为0。这意味着跳跃平均需要7比特来存储,所以100万个跳跃将很适合我们的800万比特存储空间。
这些跳跃需要被编码成一个比特流,比如通过霍夫曼编码。插入是通过遍历比特流并在新值之后重写。通过遍历并写出隐含值来输出。出于实用性考虑,它可能被做成10^4个列表,每个列表包含10^4个代码点(平均100个值)。
随机数据的霍夫曼树可以通过假设跳跃长度上的泊松分布(均值=方差=100)先验地构建,但可以在输入上保留真实的统计数据,并用于生成处理病理病例的最佳树。
由于ROM大小不计算,因此除了TCP缓冲区外,不需要任何额外的RAM。只需要实现一个大的有限状态机。每个状态表示读入的多组数字。在读取了一百万个数字之后,只需打印出与所达到的状态相对应的数字。
如果输入流可以接收几次,这将是很大的 更简单(没有关于这方面的信息,想法和时间-性能问题)。
然后,我们可以数小数。如果是计数值的话 容易使输出流。通过计算值来压缩。它 这取决于输入流中的内容。
基数树表示可以接近于处理这个问题,因为基数树利用了“前缀压缩”的优势。但是很难想象一个基树表表法可以在一个字节中表示单个节点——两个可能是极限。
但是,不管数据是如何表示的,一旦它被排序,它就可以以前缀压缩的形式存储,其中数字10、11和12将由001b、001b、001b表示,表示从前一个数字增加1。那么,也许10101b表示增量5,1101001b表示增量9,以此类推。
排序在这里是次要问题。正如其他人所说,仅仅存储整数是困难的,并且不能在所有输入上工作,因为每个数字需要27位。
我对此的看法是:只存储连续(排序)整数之间的差异,因为它们很可能很小。然后使用压缩方案,例如,每个输入数字增加2位,来编码数字存储在多少位上。 喜欢的东西:
00 -> 5 bits
01 -> 11 bits
10 -> 19 bits
11 -> 27 bits
在给定的内存限制内,应该能够存储相当数量的可能输入列表。如何选择压缩方案以使其在最大输入数量上工作的数学超出了我的范围。
我希望您能够利用输入的领域特定知识,在此基础上找到足够好的整数压缩方案。
哦,然后,当你收到数据时,你对那个排序的列表进行插入排序。