需要使非常大的阵列[2^16 + 1] [2^16 + 1] - 阵列的尺寸太大:(

问候需要使非常大的阵列[2^16 + 1] [2^16 + 1] - 阵列的尺寸太大:(

我需要计算一阶熵（马尔可夫源，就像在这里的维基百科http://en.wikipedia.org/wiki/Entropy_(information_theory）一样，这个信号由16位字组成这意味着，我必须计算a-> b（符号b出现在a之后）在数据流中出现的频率。这样做只有4个不太重要或4个更重要的比特，我使用了一个二维数组，其中第一个维度是第一个符号，第二个维度是第二个符号。

我的算法看起来像这样

读取当前符号
数组[prev_symbol] [curr_symbol] ++
prev_symbol = curr_symbol
向前移动1个符号

然后，数组[A] [B]会表示符号b在符号a后出现的次数。

现在，我明白在C中的数组是一个指针递增，以获得确切的价值，就像从数组[10] [10]中获取元素[3] [4]我必须增加指针数组[0] [0 ] [0]乘以（3 * 10 + 4）（存储在数组中的变量的大小）。我明白这个问题一定是2^32的unsigned long类型的元素必须花费太多。

但是，仍然有办法处理它吗？

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

来源

2011-02-02 Istrebitel

数据流中有多少个符号？ – 2011-02-02 11:23:40

C *中的数组不是指针*。 – 2011-02-02 11:31:35

也许你可以对数据进行多次传递。从符号X开始的对的熵贡献基本上与从任何其他符号开始的对（除了它们的总数之外）无关，因此您可以计算所有这些对的熵，然后丢弃分布数据。最后，结合2^16个部分熵值得到总和。您不一定必须对数据执行2^16次传递，您可以根据您的空间对单个传递中的尽可能多的初始字符“感兴趣”。或者，如果您的数据小于2^32个样本，那么您肯定知道您不会看到所有可能的配对，因此您实际上不需要为每个配对分配一个计数。如果样本足够小，或者熵足够低，那么某种稀疏阵列将使用比完整的16GB矩阵更少的内存。

来源

2011-02-02 11:23:38

32'000乘32'000个元素的整数（4字节）的二维数组占用大约16 GB的RAM。你的机器有多少内存？

无论如何，在超过10亿个数组元素中，只有极少数的元素的计数不会为零。因此，使用某种稀疏存储可能会更好。

一种解决方案是使用一个字典，其中元组（a，b）是关键字，出现次数是该值。

来源

2011-02-02 11:24:05 Codo

难道在Ubuntu 10.10 64位快速测试

 
[email protected]:~/test$ uname -a 
Linux thinkpad-T61p 2.6.35-25-generiC#44-Ubuntu SMP Fri Jan 21 17:40:44 UTC 2011 x86_64 GNU/Linux 
[email protected]:~/test$ cat mtest.c 
#include <stdio.h> 
#include <stdlib.h> 

short *big_array; 


int main(void) 
{ 
    if((big_array = (short *)malloc(4UL*1024*1024*1024*sizeof (short))) == NULL) { 
     perror("malloc"); 
     return 1; 
    } 

    big_array[0]++; 
    big_array[100]++; 
    big_array[1UL*1024*1024*1024]++; 
    big_array[2UL*1024*1024*1024]++; 
    big_array[3UL*1024*1024*1024]++; 

    printf("array[100] = %d\narray[3G] = %d\n", big_array[100], big_array[3UL*1024*1024*1024]); 

    return 0; 
} 
[email protected]:~/test$ gcc -Wall mtest.c -o mtest 
[email protected]:~/test$ ./mtest 
array[100] = 1 
array[3G] = 1 
[email protected]:~/test$

它看起来像Linux上的虚拟内存系统是能够胜任工作，只要你有足够的内存和/或交换。

玩得开心！

来源

2011-02-02 12:40:56

需要使非常大的阵列[2^16 + 1] [2^16 + 1] - 阵列的尺寸太大:(

回答

相关问题