Algoritmo de comparación de matrices

Question

Si tiene 2 matrices de dimensiones N * M. ¿cuál es la mejor manera de obtener la diferencia Rect?

Ejemplo:

2 3 2 3 2 3 2 3      2 3 2 3 2 3 2 3 
2 3 2 3 2 3 2 3      2 3 2 3 2 3 2 3 
2 3 4 5 4 3 2 3  <--->   2 3 2 3 2 3 2 3 
2 3 4 5 2 3 2 3      2 3 2 3 2 3 2 3 
2 3 2 3 2 3 2 3      2 3 2 3 2 3 2 3 

         | 
         | 
        \/
      Rect([2,2] , [3,4]) 
        4 5 4 
        4 5 2-> A (2 x 3 Matrix) 

Lo mejor que podía pensar es escanear desde Superior izquierda golpeó el punto en el que no hay diferencia. Luego escanea desde la parte inferior derecha y toca el punto donde hay una diferencia.

Pero en el peor de los casos, esto es O (N * M). ¿hay un mejor algoritmo eficiente? ¿O hay algo que podría hacer con la forma en que los represento, para que pueda aplicar un algoritmo más eficiente? Y cuidado, esta Matriz puede ser muy grande.

Answer 1

No, no hay un algoritmo más eficiente. Para matrices idénticas, debe escanear todos los elementos, por lo que el algoritmo es necesariamente O(n*m).

Answer 2

"Pero en el peor de los casos, esto es O (N M). ¿Hay algún algoritmo eficiente mejor?" Probablemente no debido a la dimensión de los datos que es O (N M). Muchas operaciones matriciales como esta son de orden M N porque en el peor de los casos hay M N elementos que todos tendrán que comprobarse en el caso de que las matrices sean iguales.

Ver el caso promedio es más interesante, si el cuadro de diferencia es necesariamente un único rectángulo dentro de la matriz completa, entonces sospecho que podría escaparse escaneando menos que todos los elementos en promedio.

He aquí una rápida pesar de que tenía: no perder de vista el elemento actual, llamar a este XY

1. de inicio en la esquina superior izquierda de modo XY es la esquina superior ahora

2. Comprobar que los elementos XY en ambos son iguales, si no son iguales, vaya a 3 else vaya a 4

3. Si los elementos no son, entonces tiene un elemento de la matriz de diferencias. Registre este elemento y luego busque esa fila y columna para los demás elementos (tal vez algo así como la búsqueda binaria sea más rápida). Una vez que se busca la fila/columna, tiene las coordenadas de los bordes. Si los elementos no son iguales traslado a 4.

4. El siguiente paso en diagonal movimiento XY un elemento hacia abajo y un elemento derecho, y luego ir a 2 de nuevo

5. vez una diagonal está cubierto, entonces tendrá que poner a prueba a lo largo del diagonal siguiente (sospecho que elegir la nueva diagonal que esté más alejada de la diagonal actual será la mejor, aunque no tengo pruebas de que esta sea la mejor opción) hasta que se cubran todos los elementos. En el peor de los casos, esto sigue siendo O (N * M) pero podría ser más rápido en el caso promedio.

esencia lo que están tratando de un elemento diferente lo más rápido posible, por lo que el objetivo es elegir el primer elemento de tal manera de minimizar el valor esperado del número de búsquedas para encontrar el primer elemento diferente.

Answer 3

Como otros han señalado, O (N * M) es óptimo.

Me gustaría agregar que, al escanear a través de su matriz, debe tener en cuenta el diseño de la memoria. Si la matriz se presenta en filas, lo mejor es escanear horizontalmente. Si está distribuido en columnas, mejor escanee verticalmente. Esto conducirá a un comportamiento de almacenamiento en caché bastante óptimo.

Por supuesto, esto supone que la diferencia en cuestión es de hecho en forma de un rectángulo. Si tiene alguna otra forma y desea el rectángulo delimitador, tendrá que escanear ambas filas y columnas, pase lo que pase.

Answer 4

Creo que el algoritmo propuesto es óptimo. Sin embargo, le sugiero que pruebe la biblioteca BLAS que es muy eficiente y compare el rendimiento. También hay una biblioteca Boost uBlas que proporciona una interfaz C++ y methods for Matrix expressions.