C++将二维数组的一部分复制到另一个二维数组，性能

Question

在我的程序中，我有一个函数被调用了数千次。该函数有一个参数，一个长度为 30000 的 bool 值数组。基于这个 bool 数组，我从一个全局二维数组变量中复制了一些行来构建一个本地二维数组。然后我找到局部二维数组中每一列的平均值。然后我获取局部二维数组中的每个值并减去它的列均值，以构建第二个局部二维数组。

程序正在按预期执行，但自从我添加了相关函数以来，它花费的时间太长了。有没有更快的方法从二维数组中获取数据子集并制作一个新的二维数组？有没有更快的方法从二维数组中的每个值中减去列平均值？也许我应该研究一下 vector 或在函数外声明一些东西……

谢谢。

double FitValue(bool *X){
    int i,j,k; //loop index
    int counter;
    int numUsedVariables = 0; //
    double sum;
    //find number of selected variables
    for(i=0; i<NUMVARIABLES; i++){ //NUMVARIABLES is a globally defined variable
        if(X[i] == true){
            numUsedVariables += 1;
        }
    }   
    //declare matrix for variable subset    
    alglib::real_2d_array input;
    input.setlength(NUMINDIVS,numUsedVariables); 
    //populate matrix for variable subset
    counter = -1;
    for(i=0; i<NUMVARIABLES; i++){ //NUMVARIABLES is a globally defined variable
        if(X[i] == true){       
            counter++;
            for(j=0; j<NUMINDIVS; j++){ //NUMINDIVS is a globally defined variable      
                input[j][counter] = genotype[i][j]; //genotype is global variable
            }   
        }
    }
    //find the mean of each column
    alglib::real_1d_array colMeans;
    colMeans.setlength(numUsedVariables);
    for(i=0; i<numUsedVariables; i++){
        sum = 0;
        for(j=0; j<NUMINDIVS; j++){
            sum += input[j][i];     
        }   
        colMeans[i] = sum/NUMINDIVS;
    }   
    //declare centered selected markers matrix
    alglib::real_2d_array centeredInput;
    centeredInput.setlength(NUMINDIVS,numUsedVariables);    
    for(i=0; i<numUsedVariables; i++){   
        for(j=0; j<NUMINDIVS; j++){
            centeredInput[j][i] = input[j][i]   - colMeans[i];
        }
    }
    //perform further analysis ...
    //...

}   

Answer 1

您的代码之所以变慢，是因为二维数组是按列优先顺序访问的。每次 CPU 从主内存中获取一个数字时，都会将一大堆数字提取到缓存中。请记住，C/C++ 以行优先的方式存储数组，如果您需要的下一个数字在下一行，则所有缓存的数据都是无用的。 CPU 必须返回主内存以获取下一个数字。与访问缓存中已有的数据相比，进入主内存是一个非常慢的过程。
为了使您的代码运行得更快，您需要考虑如何重新组织数据，以便以对缓存最友好的方式访问它们。这段代码
for(i=0; i<numUsedVariables; i++)
for(j=0; j<NUMINDIVS; j++)
centeredInput[j][i] = input[j][i] - colMeans[i];
会比
运行得慢很多 for(j=0; j<NUMINDIVS; j++)
for(i=0; i<numUsedVariables; i++)
centeredInput[j][i] = input[j][i] - colMeans[i];