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

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)，但如果你有纪律，可能会更多 readable/maintainable 并且可能会稍微快一些，具体取决于你的编译器：

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

Answer 2

首先，你明白你的数组是什么样子的吗？你有 6 倍的两个，但你用了 houses[5][6]。就是 5 行 6 列。你应该得到一个错误：

main.cpp:5:55: error: excess elements in array initializer
    int houses[5][6] = {{1,1},{1,1},{1,1},{1,1},{1,1},{1,1}};
                                                      ^~~~~

您真正想要的是 6 行和 2 列。

至于检查二维数组的所有元素是否相等的方法，我会遵循一个简单的方法；将数组的第一个元素存储到变量中，例如名为 v，并检查该值与所有其他元素的对比。如果它不等于只有一个元素，那么就足以做出决定并说并非所有元素都相等，如下例所示：

#include <iostream>

bool allEqual(int arr[][2], int rows)
{
    int v = arr[0][0];
    for(int i = 0; i < rows; ++i)
        for(int j = 0; j < 2; ++j)
            if(v != arr[i][j])
                return false;
    return true;
}

int main(void)
{
    int houses[6][2] = {{1,1},{1,1},{1,1},{1,1},{1,1},{1,1}};
    allEqual(houses, 6) ? std::cout << "All " : std::cout << "Not all ";
    std::cout << "elements are equal\n";
    return 0;
}

If I emulate a 2D array with an 1D, will it be faster?

我怀疑。他们的想法是内存位置将是连续的，但这是在二维情况下最常发生的情况，因为行多于列。

这是我的实验：

Georgioss-MacBook-Pro:~ gsamaras$ g++ -Wall -std=c++0x -O3 -o 2d 2d.cpp
Georgioss-MacBook-Pro:~ gsamaras$ ./2d
2D array took 1.48e-10 seconds.
Georgioss-MacBook-Pro:~ gsamaras$ g++ -Wall -std=c++0x -O3 -o 1d 1d.cpp
Georgioss-MacBook-Pro:~ gsamaras$ ./1d
Emulating 2D array with 1D array took 1.5e-10 seconds.

和我的代码，基于我的 Time measurements (C++):

#include <iostream>

#define ROWS 10000
#define COLS 20
#define REPEAT 1000

#include <iostream>
#include <ctime>
#include <ratio>
#include <chrono>

bool allEqual(int* arr, const int size)
{
    int v = arr[0];
    for(int i = 0; i < size; ++i)
        if(v != arr[i])
            return false;
    return true;
}

void fill(int* arr, const int size)
{
    for(int i = 0; i < size; ++i)
        arr[i] = 1;
}

int main(void)
{
    const int size = ROWS * COLS;
    int houses[size];
    fill(houses, size);

    bool equal;

    using namespace std::chrono;
    high_resolution_clock::time_point t1 = high_resolution_clock::now();
    for(int i = 0; i < REPEAT; ++i)
        equal = allEqual(houses, size);
    high_resolution_clock::time_point t2 = high_resolution_clock::now();
    duration<double> time_span = duration_cast<duration<double>>(t2 - t1);
    std::cout << "Emulating 2D array with 1D array took " << time_span.count()/(double)REPEAT << " seconds.\n";

    return 0;
}

其中 2d.cpp 是最直接的方法。

对二维数组使用此中提供的相等方法，报告的时间是相似的。

另外还有std::equal，在性能上和我上面的代码差不多，报的时间为：

std::equal with 2D array took 1.63e-10 seconds.

它的复杂度是："Up to linear in the distance between first1 and last1: Compares elements until a mismatch is found."

总结:

std::equal 可以，并且需要程序员较少的努力，因此使用它。

Answer 3

最快的方法：

int houses[6][2] = {{1,1},{1,1},{1,1},{1,1},{1,1},{1,2}};

int equals()
{
    int *p = (int *)houses;
    int *end = p + 6*2;
    int v = *p++;
    for(; p < end; p++)
        if (*p != v)
            return 0;
    return 1;
}

我写它是为了好玩，不要在生产中使用它。相反，遍历它们：

int equals() {
   int v = houses[0][0];
   for(int j=0;j<5;j++)
      for(int k=0;k<6;k++)
         if (houses[i][j] != v)
            return false;
   return true;
}

Answer 4

多项：

首先，正如其他人所指出的，行：

int houses[5][6] = {{1,1},{1,1},{1,1},{1,1},{1,1},{1,1}};

错了，左边声明了一个5行6列的数组，右边却构成了一个6行2列的数组

在一般情况下，比较二维数组（甚至一维数组）的所有元素的时间复杂度为 O(n)，因为对于每个元素，您必须检查所有其他元素。你可以稍微优化一下，但它仍然是一个 O(n) 算法。在最一般的情况下：

A[n][m] is an array of n rows and m columns

for(int i=0; i<n*m; i++)
{
   if(A[0][0] != A[i/n][i%n])
     return false;
}
return true;

这似乎有点令人困惑，所以让我解释一下：

一个二维数组有 n*m 个元素，所以在一个循环中查看所有元素的简单方法是 [i/n]（如果 i < n，那么它是第一行，如果 n < i < 2n 然后它是第二行...) 并且做 [i%n] 给你剩下的。这样我们就可以在一个循环中迭代整个数组。

因为我们希望所有元素都相同，所以如果第一个元素等于所有其他元素，则它们将相同，如果至少有一个不同，则它们不完全相同。

Answer 5

We can simply way to check if all the elements inside that array are equal or not. just assign the first row & column element in a variable. Then compare each element. If not equal then return false.

代码段：

bool Equal(int **arr, int row, int col)
{
   int v = arr[0][0];
   for(int i=0; i<row; i++)
   {
      for(int k=0; k<col; k++)
      {
         if(arr[i][k]!=v)  return false;
      }
   }
   return true;
}

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

Fastest method to check if all elements of 2d array are equal

c++

arrays

algorithm

loops

equality