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

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

问答来源:

slashdot.org

cleaton.net


当前回答

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

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

其他回答

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个。

我将利用TCP的重传行为。

让TCP组件创建一个大的接收窗口。 收到一定数量的包,但没有发送ACK。 处理这些传递,创建一些(前缀)压缩数据结构 对最后一个不再需要的数据包发送重复的ack /等待重传超时 转到2 所有数据包被接受

这假设了桶或多次传递的某种好处。

可能是通过对批次/桶进行排序并合并它们。->根树

使用这种技术接受并排序前80%,然后读取后20%,验证后20%不包含将落在最低数字的前20%的数字。然后发送最低的20%的数字,从内存中删除,接受剩下的20%的新数字并合并。**

在10^8的范围内有10^6个值,所以平均每100个码点有一个值。存储第N个点到第(N+1)个点的距离。重复值的跳过值为0。这意味着跳跃平均需要7比特来存储,所以100万个跳跃将很适合我们的800万比特存储空间。

这些跳跃需要被编码成一个比特流,比如通过霍夫曼编码。插入是通过遍历比特流并在新值之后重写。通过遍历并写出隐含值来输出。出于实用性考虑,它可能被做成10^4个列表,每个列表包含10^4个代码点(平均100个值)。

随机数据的霍夫曼树可以通过假设跳跃长度上的泊松分布(均值=方差=100)先验地构建,但可以在输入上保留真实的统计数据,并用于生成处理病理病例的最佳树。

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

如果输入流可以接收几次,这将是很大的 更简单(没有关于这方面的信息,想法和时间-性能问题)。

然后,我们可以数小数。如果是计数值的话 容易使输出流。通过计算值来压缩。它 这取决于输入流中的内容。