如何有效地改变一个矩阵的连续部分

Question

给定一个M行和N列的矩阵，并将其分配为M*N元素的字节数组(这些元素最初被设置为零)，我将根据以下规则修改该矩阵:在某个元素的邻域内找到的元素必须被设置为给定值。换句话说，给定一个矩阵，我应该设置矩阵的一个区域:为此，我应该访问数组中不相邻的部分。

为了执行上述操作，我可以访问以下信息:

• 指向位于邻域中心的元素的指针(该指针在上述操作中不能改变);还提供了该元素的位置(行和列);
• 邻域的大小L*L (L总是奇数)。

实现这个操作的代码应该在c++中尽可能快地执行:出于这个原因，我想到使用上面的指针来访问数组的不同部分。相反，邻域中心元素的位置(行和列)可以让我检查指定的区域是否超出了矩阵的维度(例如，区域的中心可能位于矩阵的边缘):在这种情况下，我应该只设置位于矩阵中的区域的那一部分。

int M = ... // number of matrix rows
int N = ... // number of matrix columns
char* centerPtr = ... // pointer to the center of the region
int i = ... // position of the central element
int j = ... // of the region to be modified
char* tempPtr = centerPtr - (N+1)*L/2;
for(int k=0; k < L; k++)
{
    memset(tempPtr,value,N);
    tempPtr += N;
}

我如何改进代码?如何处理一个区域可能超过一个矩阵的维数?如何使代码在执行时间方面更有效?

Answer 1

您的代码可能是最优的一般情况下，该区域不重叠的外部矩阵。使用这种代码可能导致的主要效率问题是对列而不是行进行外部循环。这将破坏缓存和分页性能。你没有那样做。

使用指针在大多数现代编译器中几乎没有速度优势。优化器会从普通的数组索引中得到非常好的指针代码。在某些情况下，我看到数组索引代码比手动调整指针代码运行得快得多。因此，如果索引运算更清晰，就不要使用指针运算。

有8种边界情况:北、西北、西、…,东北。这些都需要一个自定义版本的循环来接触正确的元素。我先展示西北的箱子，剩下的让你自己解决。

处理这种情况最快的方法是一个3层的"if"树:

if (j < L/2) {  // northwest, west, or southwest
  if (i < L/2) {  
    // northwest
    char* tempPtr = centerPtr - (L/2 - i) * N - (L/2 - j);
    for(int k = 0; k < L; k++) {
      memset(tempPtr, value, L - j);
      tempPtr += N;
    }
  } else if (i >= M - L/2) { 
    // southwest
  } else { 
    // west
  }
} else if (j >= N - L/2) { // symmetrical cases for east.
  if (i < L/2) {  
    // northeast
  } else if (i >= M - L/2) { 
    // southeast
  } else { 
    // east
  }
} else { 
  if (i < L/2) {  
    // north
  } else if (i >= M - L/2) { 
    // south
  } else { 
    // no overlap
  }
}

这样做很繁琐，但是每个区域的比较不超过3个。