Fastest method to check if all elements of 2d array are equal
An answer to this question on Stack Overflow.
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
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.)