我有一台有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
当前回答
我们有1 MB - 3 KB RAM = 2^23 - 3*2^13位= 8388608 - 24576 = 8364032位可用。
我们给出10^8范围内的10^6个数。这给出了~100 < 2^7 = 128的平均差距
让我们首先考虑一个比较简单的问题,即当所有间距都< 128时,数字间距相当均匀。这很简单。只存储第一个数字和7位空白:
(27位)+ 10^6个7位间隔数=需要7000027位
注意重复的数字间隔为0。
但如果间隔大于127呢?
好吧,让我们直接表示小于127的间隙大小,但是127的间隙大小后面跟着一个连续的8位编码来表示实际的间隙长度:
10xxxxxx xxxxxxxx = 127 .. 16,383
110xxxxx xxxxxxxx xxxxxxxx = 16384 .. 2,097,151
etc.
注意这个数字表示描述了它自己的长度,所以我们知道下一个间隙数何时开始。
对于小于127的小间隙,仍然需要7000027位。
可能有高达(10^8)/(2^7)= 781250个23位的间隙数,需要额外的16* 781250 = 12500,000位,这是太多了。我们需要一个更紧凑和缓慢增加的差距表示。
平均差距大小是100,所以如果我们把它们重新排序 [100, 99, 101, 98, 102,…], 2, 198, 1, 199, 0, 200, 201, 202,…] 然后用密集的二进制斐波那契基编码索引它,没有对零(例如,11011=8+5+2+1=16),数字用“00”分隔,然后我认为我们可以保持足够短的差距表示,但它需要更多的分析。
其他回答
在10^8的范围内有10^6个值,所以平均每100个码点有一个值。存储第N个点到第(N+1)个点的距离。重复值的跳过值为0。这意味着跳跃平均需要7比特来存储,所以100万个跳跃将很适合我们的800万比特存储空间。
这些跳跃需要被编码成一个比特流,比如通过霍夫曼编码。插入是通过遍历比特流并在新值之后重写。通过遍历并写出隐含值来输出。出于实用性考虑,它可能被做成10^4个列表,每个列表包含10^4个代码点(平均100个值)。
随机数据的霍夫曼树可以通过假设跳跃长度上的泊松分布(均值=方差=100)先验地构建,但可以在输入上保留真实的统计数据,并用于生成处理病理病例的最佳树。
如果数字的范围是有限的(只能有2个8位数,或者只有10个不同的8位数),那么你可以编写一个优化的排序算法。但如果你想对所有可能的8位数进行排序,这在内存那么少的情况下是不可能的。
如果我们对这些数字一无所知,我们就会受到以下约束:
我们需要在排序之前加载所有的数字, 这组数字是不可压缩的。
如果这些假设成立,则无法执行您的任务,因为您将需要至少26,575,425位的存储空间(3,321,929字节)。
你能跟我们说说你的数据吗?
你试过转换成十六进制吗?
我可以看到前后文件大小都有了很大的减小;然后,用自由空间分步计算。也许,再次转换为dec, order,十六进制,另一个块,转换为dec, order…
对不起. .我不知道是否可行
# for i in {1..10000};do echo $(od -N1 -An -i /dev/urandom) ; done > 10000numbers
# for i in $(cat 10000numbers ); do printf '%x\n' $i; done > 10000numbers_hex
# ls -lah total 100K
drwxr-xr-x 2 diego diego 4,0K oct 22 22:32 .
drwx------ 39 diego diego 12K oct 22 22:31 ..
-rw-r--r-- 1 diego diego 29K oct 22 22:33 10000numbers_hex
-rw-r--r-- 1 diego diego 35K oct 22 22:31 10000numbers
我们有1 MB - 3 KB RAM = 2^23 - 3*2^13位= 8388608 - 24576 = 8364032位可用。
我们给出10^8范围内的10^6个数。这给出了~100 < 2^7 = 128的平均差距
让我们首先考虑一个比较简单的问题,即当所有间距都< 128时,数字间距相当均匀。这很简单。只存储第一个数字和7位空白:
(27位)+ 10^6个7位间隔数=需要7000027位
注意重复的数字间隔为0。
但如果间隔大于127呢?
好吧,让我们直接表示小于127的间隙大小,但是127的间隙大小后面跟着一个连续的8位编码来表示实际的间隙长度:
10xxxxxx xxxxxxxx = 127 .. 16,383
110xxxxx xxxxxxxx xxxxxxxx = 16384 .. 2,097,151
etc.
注意这个数字表示描述了它自己的长度,所以我们知道下一个间隙数何时开始。
对于小于127的小间隙,仍然需要7000027位。
可能有高达(10^8)/(2^7)= 781250个23位的间隙数,需要额外的16* 781250 = 12500,000位,这是太多了。我们需要一个更紧凑和缓慢增加的差距表示。
平均差距大小是100,所以如果我们把它们重新排序 [100, 99, 101, 98, 102,…], 2, 198, 1, 199, 0, 200, 201, 202,…] 然后用密集的二进制斐波那契基编码索引它,没有对零(例如,11011=8+5+2+1=16),数字用“00”分隔,然后我认为我们可以保持足够短的差距表示,但它需要更多的分析。