c++ - 检查二维数组的所有元素是否相等的最快方法

Question

我有一个二维数组 houses[5][2] = {{1,1},{1,1},{1,1},{1,1},{1,1}} 检查该数组中的所有元素是否相等的最快方法是什么？到目前为止，这是我尝试过的:```

for(int j=0;j<5;j++){
 for(int k=0;k<6;k++){
   if(houses[j][k] == houses[j+1][k+1] && j+1 != 5 && k + 1 != 6)
     equal = true;
    else{
     equal = false;
     break;
     }
}
}

虽然这不会比较所有元素，但我知道如何比较所有元素，但这似乎是一个很长的循环.. 有更快的方法吗？

Answer 1

您当前的代码将失败，因为 break 只会让您跳出一个循环。您必须退出两者，这需要进行第二次检查，如下所示:

auto the_value = houses[0][0];
bool equal     = true;

for(int j=0;j<5;j++){
  for(int k=0;k<6;k++){
    if(houses[j][k]!=the_value){
      equal = false;
      goto done;
    }
  }
  if(!equal)
    break
}

(将第一个元素存储在一个变量中，然后遍历所有元素以检查它们是否等于该变量，避免了通过检查相邻元素调用的困惑情况。)

同时跳出两个循环需要黑魔法 (goto)，但如果您有纪律，可能会更具可读性/可维护性，并且可能会稍微快一些，具体取决于您的编译器:

auto the_value = houses[0][0];
bool equal     = true;

for(int j=0;j<5;j++)
for(int k=0;k<6;k++)
  if(houses[j][k]!=the_value){
    equal = false;
    goto done; //Danger, Will Robinson!
  }

done:
//More stuff

您可能会发现平面阵列更快:

auto the_value = houses[0][0];
bool equal     = true;
for(int i=0;i<5*6;i++)
  if(houses[i]!=the_value){
    equal = false;
    break;
  }

二维数组作为一维连续数组存储在内存中。使用平面数组寻址访问相同的内存位置，但明确避免强制执行内部算术。对于高性能代码，您可能希望默认使用平面数组。

由于您可能会多次使用这样的函数，或者将其嵌入到其他复杂的代码中，也许您想将其抽象化:

template<class T>
bool AllEqual(const T& arr, size_t N){
  T the_value = arr[0];
  for(int i=0;i<N;i++)
    if(arr[i]!=the_value)
      return false;
  return true;
}

AllEqual(houses, 5*6);

由于您使用 C++ 进行编码，您可能无论如何都不想使用原始数组。让我们使用 STL 重写您的代码，假设平面数组:

template<class T>
bool AllEqual(const std::vector<T>& arr){
  return std::all_of(arr.begin(), arr.end(), [&](const T& x){ return x==arr[0]; });
}

std::vector<int> houses = {}; //Replace with appropriate initialization
if(AllEqual(houses))
  //Do stuff

(另外:正如另一个回答者提到的，您向数组添加数据的方式似乎暗示它应该是 2x6/6x2 数组而不是 5x6/6x5。)