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

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

问答来源:

slashdot.org

cleaton.net


当前回答

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

其他回答

(我原来的答案是错误的,对不起,数学不好,见下面的休息。)

这个怎么样?

前27位存储您所看到的最小数字,然后是与下一个数字的差值,编码如下:5位存储用于存储差值的位数,然后是差值。使用00000表示您再次看到了该数字。

这是因为插入的数字越多,数字之间的平均差值就越小,所以当你添加更多的数字时,你用更少的比特来存储差值。我想这叫做增量表。

我能想到的最糟糕的情况是所有数字都等距(以100为间隔),例如假设0是第一个数字:

000000000000000000000000000 00111 1100100
                            ^^^^^^^^^^^^^
                            a million times

27 + 1,000,000 * (5+7) bits = ~ 427k

Reddit来拯救你!

如果你要做的只是把它们排序,这个问题就简单了。它需要122k(100万比特)来存储你看到的数字(如果看到0,则第0位,如果看到2300,则第2300位,等等。

读取数字,将它们存储在位域中,然后在保持计数的同时将位移出。

但是,你必须记住你看过多少。我受到上面的子列表答案的启发,想出了这个方案:

用2位或27位代替1位:

00表示你没有看到这个数字。 01表示你看过一次 1表示你看过,接下来的26位是看了多少次。

我认为这是可行的:如果没有重复,你就有一个244k的列表。 在最坏的情况下,你看到每个数字两次(如果你看到一个数字三次,它会缩短列表的其余部分),这意味着你不止一次看到了50,000个,你0次或1次看到了950,000个项目。

50,000 * 27 + 950,000 * 2 = 396.7k.

如果你使用以下编码,你可以做进一步的改进:

0表示你没有看到这个数字 10表示你看过一次 11是你计数的方式

这将导致平均280.7k的存储空间。

编辑:我周日早上的数学算错了。

最坏的情况是,我们两次看到50万个数字,所以数学就变成了:

500,000 *27 + 500,000 *2 = 1.77M

交替编码导致平均存储为

500,000 * 27 + 500,000 = 1.70M

: (

你试过转换成十六进制吗?

我可以看到前后文件大小都有了很大的减小;然后,用自由空间分步计算。也许,再次转换为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

在所有可能的输入中,这个问题只有一个解决方案。作弊。

通过TCP读取m个值,其中m接近内存中可排序的最大值,可能是n/4。 对250,000(大约)个数字进行排序并输出。 重复做另外3个四分之三。 让接收方在处理时合并接收到的4个数字列表。(这并不比使用单个列表慢多少。)

If the numbers are evenly distributed we can use Counting sort. We should keep the number of times that each number is repeated in an array. Available space is: 1 MB - 3 KB = 1045504 B or 8364032 bits Number of bits per number= 8364032/1000000 = 8 Therefore, we can store the number of times each number is repeated to the maximum of 2^8-1=255. Using this approach we have an extra 364032 bits unused that can be used to handle cases where a number is repeated more than 255 times. For example we can say a number 255 indicates a repetition greater than or equal to 255. In this case we should store a sequence of numbers+repetitions. We can handle 7745 special cases as shown bellow:

364032/(表示每个数字所需的位数+表示100万所需的位数)= 364032 / (27+20)=7745

我们有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”分隔,然后我认为我们可以保持足够短的差距表示,但它需要更多的分析。