c++ - 如何有效地改变矩阵的连续部分？

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 次。