[C] Ruotare Matrice!!

[bDaniele]

Salve, qualcuno può suggerirmi un algoritmo in C per fare la rotazione di una matrice 4x4 il più efficiente possibile??

Grazie a tutti.

[Dwenegar]

m1 = matrix(4,4);
m2 = matrix(4,4);
c = 3;

for i = 0 to 3 do
  for j = 0 to 3 do
    m2(j,c) = m1(i,j)
  c = c - 1

Lo pseudo codice esegue la rotazione in senso orario.

Bye.

[bDaniele]

Graazie, solo che richiede troppi cicli di clock.

Mi serve qualcosa di molto più efficiente.

[lelefante]

In base a cosa dici che usa troppi cicli di clock?
E' un esercizio, o hai proprio bisogno di fare il tutto in maniera molto efficiente?
E poi la rotazione che ti ha suggerito Dwenegar e' quella che cercavi?

[Dwenegar]

La matrice ha 4x4 = 16 elementi. Sia A = { a_0, a_1, ..., a_15} tale matrice.
La rotazione della matrice A in senso orario di un passo genera una nuova matrice A' = (a_i_0, a_i_1, ..., a_i_15} dove x' = (i_0, i_1, ..., i_15} è una permutazione di x = (0, 1, ..., 15) con i_j != j per 0 <= j <= 15. Pertanto l'algoritmo per ruotare la matrice di un passo in senso orario è O(16).

Per me, più veloce di così si muore. Devi spostare 16 elementi e fai 16 operazioni di assegnazione.

Non vedo come si possa velocizzare.
Se qualcuno ha un algoritmo migliore sono tutt'orecchi

[bDaniele]

il mio problema è effettivamente andare veloce, sulle 16 letture non ci sono dubbi che devono essere fatte, ma possono essere fatte in tanti modi diversi, es. accedendo ad ogni singola posizione attraverso l'uso delle parentesi, utilizzando un puntatore e incrementandolo di sizeof(elemento) ad ogni iterazione.
Sempre sulla lettura si hanno differenze abbissali solamente gestendo opportunamente la cache quindi abbolendo i cache miss.

fare in modo da avere i dati nella cache anzichè pescarli in memoria significa risparmiare circa 90 cicli di clock, in quando il tempo che il processore attende per ottenere un dato passa da 10 a 100 cicli di clock a seconda se il dato è in cache o in memoria.

Cmq vi ringrazio per l'aiuto e se avete idee postate.

[Dwenegar]

OK. Ora è chiaro. I miei due centesimi:
- se le matrici che sono sempre e solamente 4 x 4 tienile in un array di 16 elementi ed accedi alla matrice tramite una macro (suppongo l'uso di C/C++) tipo GET(m, i, j) (hmm...forse questa è un po' una cazzata);
- crea a mano le permutazioni degli indici che ti servono per fare le rotazioni (per la rotazione di un passo in senso orario la permutazione è x = (12, 8, 4, 0, 13, 9, 5, 1, 14, 10, 6, 2, 15, 11, 7, 3). In pratica le permutazioni sono /hardwired/ nel codice.
- fai un solo loop e l'elemento in posizione i lo metti in posizione x_i;
- se usi gcc digli di sbrogliare i loop se possibile;

[r0x]

bDaniele, non puoi incrementare un puntatore del genere, perche` non e` un array contiguo, e` un array di array. La complessita` delle operazioni su una matrice e` sempre quadratica, non si scappa. Questo a meno che tu non usi un metodo artificioso per creare una matrice da un array monodimensionale, e quello si puo` fare e permette la linearita`.

Ciao.

[Dwenegar]

Originariamente inviato da r0x
La complessita` delle operazioni su una matrice e` sempre quadratica, non si scappa.

Ma che c'entra? Lui chiede idee e tu rispondi così? Con cosa fai colazione?

[bDaniele]

Originariamente inviato da r0x
bDaniele, non puoi incrementare un puntatore del genere, perche` non e` un array contiguo, e` un array di array.

In C come anche in Pascal gli array sono allocati in modo contiguo e su questo si può essere certi, altrimenti tutte le funzioni che lavorano su array di libreria dovrebbero riscritte.
La sintassi del C indica proprio che il nome di un array non è altro che un puntatore alla prima posizione.

Se hai dubbi ti mando tutti gli esempi che vuoi.