Algoritmo di confronto matrice

Question

Se si dispone di 2 matrici di dimensioni N * M. qual è il modo migliore per ottenere la differenza Rect?

Esempio:

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) 

Il meglio che ho potuto pensare è quello di eseguire la scansione da Top-sinistra ha colpito il punto in cui non v'è differenza. Quindi scansiona da In basso a destra e colpisci il punto in cui c'è una differenza.

Ma nel peggiore dei casi, questo è O (N * M). c'è un algoritmo migliore efficiente? O c'è qualcosa che posso fare con il modo in cui li rappresento, in modo da poter applicare un algoritmo più efficiente? E attenzione, questa Matrix può essere molto grande.

Answer 1

No, non esiste un algoritmo più efficiente. Per matrici identiche, è necessario eseguire la scansione di tutti gli elementi, quindi l'algoritmo è necessariamente O(n*m).

Answer 2

"Ma nel peggiore dei casi, questo è O (N M). C'è un algoritmo migliore efficiente?" Probabilmente non a causa della dimensione dei dati O (N M). Molte operazioni di matrice come questa sono di ordine M N perché nel caso peggiore ci sono M N elementi che dovranno essere controllati nel caso in cui le matrici siano uguali.

Guardare al caso medio è più interessante, se la casella di differenza è necessariamente un singolo rettangolo all'interno dell'intera matrice, quindi sospetto che si possa ottenere una scansione con meno di tutti gli elementi in media.

Ecco un rapido se ho avuto: tenere traccia dell'elemento corrente, chiamare questo XY

1. Inizia in alto a sinistra in modo XY è alto ora

2. Verificare che gli elementi XY in entrambi sono uguali, se non uguale vai a 3 altrimenti vai a 4

3. Se gli elementi non sono allora hai un elemento della differenza di matrice. Registra questo elemento quindi cerca quella riga e colonna per gli altri elementi (forse qualcosa come la ricerca binaria è la più veloce). Dopo aver cercato la riga/colonna, hai le coordinate dei bordi. Se gli elementi non sono uguali per passare a 4.

4. passo successivo movimento XY diagonalmente un elemento basso e un elemento di destra, quindi andare nuovamente 2

5. volta una diagonale è coperto poi dovrai testare lungo la diagonale successiva (sospetto che la scelta di una nuova diagonale che è la più lontana dalla diagonale attuale sarà la migliore, anche se non ho prove che questa sia la scelta migliore) finché tutti gli elementi non saranno coperti. Nel peggiore dei casi questo è ancora O (N * M) ma potrebbe essere più veloce nel caso medio.

In sostanza si sta tentando di un elemento diverso il più velocemente possibile, in modo da l'obiettivo è scegliere il primo elemento in modo tale da ridurre al minimo il valore atteso del numero di ricerche per trovare il primo elemento diverso.

Answer 3

Come altri hanno sottolineato, O (N * M) è ottimale.

Vorrei solo aggiungere che, durante la scansione attraverso la matrice, è necessario tenere a mente il layout della memoria. Se la matrice è disposta in righe, è meglio eseguire la scansione in orizzontale. Se è disposto in colonne, è meglio eseguire una scansione verticale. Ciò condurrà a un comportamento di caching ottimale.

Naturalmente, questo presuppone che la differenza in questione sia effettivamente nella forma di un rettangolo. Se si tratta di un'altra forma e si desidera il rettangolo di delimitazione, è necessario eseguire la scansione di righe e colonne, indipendentemente da cosa.

Answer 4

Penso che l'algoritmo proposto sia ottimale. Tuttavia ti suggerisco di provare la libreria BLAS che è molto efficiente e confrontare le prestazioni. C'è anche la libreria Boost uBlas che fornisce l'interfaccia C++ e methods for Matrix expressions.