C ++: el método más rápido para verificar si todos los elementos de la matriz son iguales

¿Cuál es el método más rápido para comprobar si todos los elementos de una matriz (conjunto de enteros preferido) son iguales? Hasta ahora he estado usando el siguiente código:

bool check(int array[], int n) { bool flag = 0; for(int i = 0; i < n - 1; i++) { if(array[i] != array[i + 1]) flag = 1; } return flag; } 

 int check(const int a[], int n) { while(--n>0 && a[n]==a[0]); return n!=0; } 

Una vez que haya encontrado un elemento que no coincide, puede salir del círculo:

 bool check(const int array[], int n) { for (int i = 0; i < n - 1; i++) { if (array[i] != array[i + 1]) return true; } return false; } 

Si esto es crítico para el rendimiento, entonces se puede optimizar aún más como:

 bool check(const int array[], int n) { const int a0 = array[0]; for (int i = 1; i < n; i++) { if (array[i] != a0) return true; } return false; } 

Aquí hay una solución sólida que es válida C ++ 11. Las ventajas es que no necesita jugar manualmente con los índices o iteradores. Es una mejor práctica

prefiera las llamadas de algoritmo a los bucles escritos a mano [Herb Sutter – C ++ Coding Standards]

Creo que esto será igualmente eficiente como la solución de Paul R.

 bool check(const int a[], int n) { return !std::all_of(a, a+n, [a](int x){ return x==a[0]; }); } 

Redefine la matriz a un tipo de datos más grande. Por ejemplo, opere con entradas de 64 bits o use intrínsecos SSE o AVX para operaciones de 128 o 256 bits. Por ejemplo, el SSE2 intrínseco es _mm_cmpeq_epi32, cuyo resultado usará con _mm_or_si128. Verifique el resultado con la aplicación repetida de _mm_srli_si128 y _mm_cvtsi128_si32. Compruebe el resultado cada pocas cientos de iteraciones para la salida anticipada.

Asegúrese de operar en la memoria alineada, verifique el inicio y el fin desalineados como enunciados, y verifique el primer elemento empaquetado consigo mismo.

Busque una biblioteca que esté disponible en su plataforma que admita subprocesos o bucles paralelos, y divida el cálculo de forma tal que diferentes núcleos prueben diferentes rangos de la matriz.

Algunas bibliotecas disponibles se enumeran aquí:

http://parallel-for.sourceforge.net/parallelfor.html

O posiblemente, puede hacer uso del paralismo que ofrecen muchas GPU.

 bool check(int array[],int n) { // here 1st element is checked with others. This decreases the number of iteration by 1. // also it returns immediately. // The requirement is to check if all the elements are equal. // So if 1st element is equal to others then all elements are equal. // Otherwise the elements are not equal. for(int i=1;i 

Básicamente se trata de una operación de O (n), por lo que no se puede hacer mucho mejor de lo que se tiene, aparte de prescindir de la bandera y simplemente return false; mensaje return false; en la primera falla y return true; después de la iteración.

En teoría, yo propondría esto:

 bool check_single(const int a[], int n) { for (int i = 1; i < n; ++i) { if (a[0] != a[n]) { return false; } } return true; } 

Comparado con otras versiones (ya propuestas):

  • a[0] será levantado fuera del bucle por el comstackdor, lo que significa un solo acceso de matriz dentro del bucle
  • hacemos un bucle de 0 a n, que es mejor (acceso-sabio) que cargando a[0] y luego bucle de a[n]

Obviamente, todavía comprueba N elementos y por lo tanto es O (N).

Para la eficiencia del progtwigdor puede intentar lo siguiente, todo en una sola línea.

 vector v{1, 1, 1, 1}; all_of(v.cbegin(), v.cend(), [&r=v[0]](int value){ return value == r; }->bool); 

No probé ejecutar este código, avíseme si hay un error de syntax.

 bool check_identity (int a[], int b[], const int size) { int i; i = 0; while ((i < size-1) && (a[i] == b[i])) i++; return (a[i] == b[i]); }