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

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

问答来源:

slashdot.org

cleaton.net


当前回答

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

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

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

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

其他回答

基数树表示可以接近于处理这个问题,因为基数树利用了“前缀压缩”的优势。但是很难想象一个基树表表法可以在一个字节中表示单个节点——两个可能是极限。

但是,不管数据是如何表示的,一旦它被排序,它就可以以前缀压缩的形式存储,其中数字10、11和12将由001b、001b、001b表示,表示从前一个数字增加1。那么,也许10101b表示增量5,1101001b表示增量9,以此类推。

您只需要按顺序存储数字之间的差异,并使用编码来压缩这些序列号。我们有2^23位。我们将它分成6位块,让最后一位表示这个数字是否扩展到另外6位(5位加上扩展块)。

因此,000010是1,000100是2。000001100000表示128。现在,我们考虑用最坏的类型来表示不超过10,000,000的数字序列的差异。可能有10000000 /2^5的差异大于2^5,10000000 /2^10的差异大于2^10,10000000 /2^15的差异大于2^15,等等。

所以,我们把表示这个序列所需要的比特数相加。我们有1,000,000*6 +汇总(10,000,000/2^5)*6+汇总(10,000,000/2^10)*6+汇总(10,000,000/2^15)*6+汇总(10,000,000/2^20)*4=7935479。

2^24 = 8388608。由于8388608 > 7935479,我们应该很容易有足够的内存。我们可能还需要一点内存来存储插入新数字时的和。然后我们遍历这个序列,找到插入新数字的位置,如果必要的话减少下一个差值,并将它之后的所有内容都右移。

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

我可以看到前后文件大小都有了很大的减小;然后,用自由空间分步计算。也许,再次转换为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个数字列表。(这并不比使用单个列表慢多少。)

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