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

Question

I have a 2d array houses[5][2] = {{1,1},{1,1},{1,1},{1,1},{1,1}} What is the fastest way to check if all the elements inside that array are equal? Here is what I have tried so far: ```

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;
     }
}
}

This won't compare all the elements tho, I know how to compare all of them, but it seems to be a very long loop .. is there a faster way to do that?

Answer 1

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.

Code Snippet :

---

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;
}

Answer 2

Multiple things:

First, as others have pointed out, the line:

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

Is wrong, the left hand side declares an array with 5 rows and 6 columns, but the right hand side constitutes an array of 6 rows and 2 columns.

On the general case comparing all elements of a 2d array (or even a 1d array) is in O(n) since for every element you must check all other elements. You can optimize it a little bit but it will still be an O(n) algorithm. On the most general case:

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;

This may seem a little bit confusing so let me explain:

a 2d array has n*m elements, so an easy way to see all of them in a single loop is doing [i/n] (if i < n, then it's the first row, if n < i < 2n then it's the second row...) and doing [i%n] gives you the remainder. This way we can iterate the entire array in a single loop.

Since we want all elements to be the same, if the first element is equal to all others then they are ll the same, if at least on is different then they are not all the same.

Answer 3

The fastest way:

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;
}

I wrote it for fun, don't use that in production. Instead, iterate through them all:

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

First, do you understand what your array looks like? You have 6 times of two ones, but you used houses[5][6]. That's it 5 rows and 6 columns. You should have gotten an error for that:

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}};
                                                      ^~~~~

What you really wanted was 6 rows and 2 columns.

---

As for the way of checking whether all elements of a 2D array are equal, I would follow a simple approach; store the first element of your array to a variable, e.g. named v, and check that value versus all the other elements. If it is not equal to just one element, then it is enough to take a decision and say that not all elements are equal, like in the following example:

#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?

I doubt it. They idea is that the memory locations will be contiguous, but this is what happens pretty most in the 2D case, given that the rows are more than the columns.

Here is my experiment:

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.

and my code, based on my 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;
}

where the 2d.cpp is the straightforward way.

Using the equal method provided in this answer for a 2D array, the timings reported are similar.

Moreover, there is std::equal, which is comparable in terms of performance to my code above, reporting a time of:

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

It's complexity is: "Up to linear in the distance between first1 and last1: Compares elements until a mismatch is found."

---

Summary:

std::equal does OK, and requires the less effort from the programmer, thus use it.

Answer 5

Your current code will fail because break will only take you out of one loop. You must exit both, which requires a second check, like so:

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
}

(Storing the first element in a variable and then looping over all of the elements to check to see if they are equal to that variable obviates the mess you invoke by checking adjacent elements.)

Breaking out of both loops simultaneously requires the Dark Arts (goto), but may be more readable/maintainable if you are disciplined and may be slightly faster, depending on your compiler:

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

You may find a flat array to be faster:

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;
  }

The 2D array is stored as a 1D contiguous array in memory. Using flat array addressing accesses the same memory locations, but explicitly avoids forcing the internal arithmetic. For highly performant code you may wish to consider using flat arrays by default.

Since you might use a function such as this a number of times or have it embedded in otherwise complex code, perhaps you'd like to abstract it:

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);

Since you're coding in C++, you probably don't want to be using raw arrays anyway. Let's rewrite your code using the STL, assuming flat arrays:

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

(Also: as another answerer mentioned, the way you are adding data to your array seems to imply that it should be 2x6/6x2 array instead of 5x6/6x5.)