c++ - 在 C++ 中优化二维数组

Question

我正在处理具有以下特征的二维数组:

const int cols = 500; 
const int rows = 100; 
int arr[rows][cols];

我通过以下方式访问数组 arr 来做一些工作:

for(int k = 0; k < T; ++k) { // for each trainee
  myscore[k] = 0;
  for(int i = 0; i < cols; ++i) { // for each sample  
    for(int j = 0; j < rows; ++j) { // for each expert
      myscore[k] += delta(i, anotherArray[k][i], arr[j][i]);
    }   
  }
}

所以我担心数组 'arr' 而不是另一个。我需要使它对缓存更友好并提高速度。我在想也许转置阵列，但我不确定该怎么做。结果证明我的实现只适用于方阵。我如何让它适用于非方阵？

此外，将二维数组映射到一维数组会提高性能吗？如果是这样，我该怎么做？最后，关于我如何优化它的任何其他建议......我已经没有想法了，但我知道 arr[j][i] 是我需要进行更改的地方，因为我正在访问列列而不是逐行，因此根本不是缓存友好的。

谢谢，赫里斯托

Answer 1

将军in-place matrix transposition 非常困难，但如果您可以将它转置到另一个数组，那么它就非常简单。

const int cols = 500; 
const int rows = 100; 

int arr[rows][cols];
// fill arr[][]

int arrT[cols][rows];
for (int r = 0; r < rows; r++) {
   for (int c = 0; c < cols; c++) {
      arrT[c][r] = arr[r][c];
   }
}

当然，根据您获取 arr[][] 的方式，您可以直接填写 arrT[][]。

但是，可能有一个简单的交换循环顺序的更简单的解决方案。

for(int k = 0; k < T; ++k) { // for each trainee
  myscore[k] = 0;
  for(int j = 0; j < rows; ++j) { // for each expert
    for(int i = 0; i < cols; ++i) { // for each sample  
      myscore[k] += delta(i, anotherArray[k][i], arr[j][i]);
    }   
  }
}