我有一台有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。
但是算术编码实现的不精确性可能使它不可能实现。如果这个问题是可能的,它将是非常紧张的。
有志愿者吗?
其他回答
现在的目标是一个实际的解决方案,覆盖所有可能的情况下,输入在8位数范围内,只有1MB的RAM。注:工作正在进行中,明天继续。使用对已排序整型的增量进行算术编码,对于1M个已排序整型,最坏的情况是每个条目花费大约7位(因为99999999/1000000是99,而log2(99)几乎是7位)。
但是你需要将1m个整数排序到7位或8位!级数越短,delta就越大,因此每个元素的比特数就越多。
我正在努力尽可能多地压缩(几乎)在原地。第一批接近250K的整数最多每个需要大约9位。因此结果大约需要275KB。重复使用剩余的空闲内存几次。然后解压缩-就地合并-压缩这些压缩块。这很难,但也是可能的。我认为。
合并后的列表将越来越接近每整数7位的目标。但是我不知道合并循环需要多少次迭代。也许3。
但是算术编码实现的不精确性可能使它不可能实现。如果这个问题是可能的,它将是非常紧张的。
有志愿者吗?
(我原来的答案是错误的,对不起,数学不好,见下面的休息。)
这个怎么样?
前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
: (
我们可以利用网络堆栈,在我们得到所有数字之前,按顺序发送数字。如果你发送1M的数据,TCP/IP会把它分解成1500字节的数据包,并按照目标发送。每个包将被赋予一个序列号。
我们可以用手来做。在填满内存之前,我们可以对现有的数据进行排序,并将列表发送给目标,但在每个数字周围的序列中留下空洞。然后用同样的方法处理第二个1/2的数字,使用序列中的这些洞。
远端的网络堆栈将按顺序组装结果数据流,然后将其提交给应用程序。
它使用网络来执行归并排序。这是一个完全的黑客,但我是受到之前列出的其他网络黑客的启发。
To represent the sorted array one can just store the first element and the difference between adjacent elements. In this way we are concerned with encoding 10^6 elements that can sum up to at most 10^8. Let's call this D. To encode the elements of D one can use a Huffman code. The dictionary for the Huffman code can be created on the go and the array updated every time a new item is inserted in the sorted array (insertion sort). Note that when the dictionary changes because of a new item the whole array should be updated to match the new encoding.
如果每个唯一元素的数量相等,则编码D中每个元素的平均比特数将最大化。比如元素d1 d2…, dN在D中各出现F次。在这种情况下(最坏的情况是输入序列中同时有0和10^8)我们有
sum(1<=i<=N) F. di = 10^8
在哪里
sum(1<=i<=N) F=10^6,或F=10^6/N,归一化频率将是p= F/10^=1/N
平均比特数为-log2(1/P) = log2(N)。在这种情况下,我们应该找到使n最大化的情况,这发生在di从0开始的连续数,或者di= i-1时
10 ^ 8 =(1 < =我< = N) f . di =(1 < =我< = N) (10 ^ 6 / N)(张)= (10 ^ 6 / N) N (N - 1) / 2
i.e.
N <= 201。在这种情况下,平均比特数是log2(201)=7.6511,这意味着我们将需要大约1字节的每个输入元素来保存排序的数组。注意,这并不意味着D一般不能有超过201个元素。它只是说明,如果D的元素是均匀分布的,那么D的唯一值不可能超过201个。
谷歌的(坏)方法,从HN线程。存储rle风格的计数。
你的初始数据结构是“99999999:0”(都是零,没有看到任何数字),然后假设你看到了数字3,866,344,那么你的数据结构就变成了“3866343:0,1:1,96133654:0”,你可以看到数字总是在零位数和1位数之间交替,所以你可以假设奇数代表0位,偶数代表1位。这就变成了(3866343,1,96133654)
他们的问题似乎不包括副本,但让我们假设他们使用“0:1”来表示副本。
大问题#1:1M个整数的插入将花费很长时间。
大问题#2:像所有的普通增量编码解决方案一样,一些分布不能用这种方式覆盖。例如,1m整数,距离为0:99(例如,每个整数+99)。现在考虑相同的情况,但随机距离在0:99的范围内。(注:99999999/1000000 = 99.99)
谷歌的方法既不值得(缓慢),也不正确。但要为他们辩护,他们的问题可能略有不同。