需要制作一个非常大的数组[2 ^ 16 + 1] [2 ^ 16 + 1] - 数组的大小太大:(

Question

问候

我需要计算一个包含16位字的信号的一阶熵(Markov源,就像维基上的http://en.wikipedia.org/wiki/Entropy_(information_theory)一样.这意味着,我必须计算频率a-> b的每个组合(符号b出现在a之后)发生在数据流中.当我只做4个不太重要或4个更重要的位时,我使用了一个二维数组,其中第一维是第一个符号和第二维是第二个符号.

我的算法看起来像这样

1. 读取当前符号
2. 阵列[prev_symbol] [curr_symbol] ++
3. prev_symbol = curr_symbol
4. 向前移动1个符号

然后,Array [a] [b]将表示符号b在流中出现符号a之后的次数.

现在,我明白C中的数组是一个递增得到精确值的指针,比如从数组[10] [10]获取元素[3] [4]我必须将指针递增到数组[0] [0] by(3*10 + 4)(存储在数组中的变量大小).我理解问题必须是2 ^ 32个unsigned long类型的元素必须占用太多.

但是,还有办法解决它吗？

或者也许有另一种方法来实现这一目标？

Answer 1

具有32'000乘32'000元素的二维整数数组(4字节)占用大约16GB的RAM.你的机器有那么多内存吗？

无论如何,在超过10亿个数组元素中,只有极少数数组元素的数量不同于0.因此,使用某种稀疏存储可能会更好.

一种解决方案是使用字典,其中元组(a,b)是关键字,并且出现次数是值.