Trasposta di una matrice contenuta in un array 1D

[Cait Sith]

Per motivi di efficienza rappresento una matrice NxM con un array 1D (float[NxM]) anzichè un array 2D (float[N][M]).
Quando faccio la trasposta, adesso come adesso, creo un nuovo array delle stesse dimensioni e lo riempio invertendo le righe e le colonne degli elementi.
Siccome nella maggior parte dei casi mi interessa solo il risultato della trasposizione e non la matrice originale, vorrei fare un metodo che scambia opportunamente gli elementi dell'array stesso per evitare di dover creare un nuovo array (le dimensioni non sono piccolissime).
Ci ho pensato un attimo e non mi sembra una cosa banalissima.
Qualcuno sa se esiste già la soluzione al problema?


in ingresso ho il puntatore all'array, il numero di righe e in numero di colonne

gli elementi dell'array sono ordinati lungo le colonne della matrice, per esempio una matrice 3x2 del tipo

1 2
3 4
5 6

sarebbe rappresentata dall'array

1 3 5 2 4 6

[DanieleC88]

Be', ti tocca ricostruire l'aritmetica dei puntatori, ma quello non è un compito così tanto ostico; ti serve una funzione di swap e anche lì non dovresti avere problemi; devi poi immaginare che questa tua matrice rettangolare sia tagliata diagonalmente da una linea che va dal vertice in alto a sinistra a quello in basso a destra: poi ti dovrebbe bastare uno scambio tra le posizioni simmetriche rispetto alla diagonale... non so se mi sono spiegato bene...

EDIT: però effettivamente questa funzionerebbe solo per matrici quadrate...

[DanieleC88]

Anche se, a dirla tutta, non sono proprio certo di aver interpretato bene il fatto di "invertendo le righe e le colonne degli elementi"... cioè, intendi che una matrice di questo tipo:

1 2
3 4
5 6

debba diventare così:

1 3 5
2 4 6

o ho capito male?

[Cait Sith]

si, però se guardi gli array da

1 3 5 2 4 6

diventa

1 2 3 4 5 6

in quanto le matrici sono sempre scandite per colonne
quindi come vedi non c'è un semplice swap tra due elementi, ma uno swap concatenato, poi sotto particolari simmetrie (righe e colonne dispari, ci sono elementi che rimangono nello stesso punto)
insomma, non mi sembra così semplice
speravo che qualcuno avesse già incontrato questo tipo di problema

se ho visto giusto, individuati i punti fissi, nel mezzo ci sono dei blocchi composti dagli stessi elementi
nell'esempio c'è solo un blocco composto da 3 5 2 4
quindi io partirei dal 3 che metteri in posizione 2, in posizione 2 c'era il 5 che vado a mettere in posizione 4, in posizione 4 c'era il 4 che vado a mettere in posizione 3, in posizione 3 c'era il 2 che vado a mettere in posizione 1, dove c'era il 3 che ho già spostato, e così ho chiuso la trasposizione
il problema è che ho paura che ci siano situazioni più complicate di questa

[DanieleC88]

Ecco, appunto per quello mi era venuto il dubbio...
Simpatico come problema, dovrò pensarci un po' su.

[DanieleC88]

Anche se probabilmente non ti interesserà più, l'altro giorno ho provato a farmi degli esempi di matrici di diverse dimensioni, ma non riesco a vedere un metodo che assicuri una trasformazione esatta solo con degli scambi. Il problema è molto semplice se puoi permetterti un'array di appoggio, ma facendone a meno dovresti essere in grado di ricordare le posizioni originali per poter "ricordare" ciò che hai fatto dopo gli scambi e riordinare come necessario...

[Cait Sith]

mi interessa ancora, però penso di fare come ho detto (domani provo a sperimentare)
lo scambio concatenato mi sembra ok, il problema è che dopo non so se un elemento è stato scambiato o no, probabilmente per non impazzire troppo creerò un array di booleani per vedere se ciascun elemento è al posto giusto
anzi, invece di usare un array di booleani che in java non si sa bene come vengano memorizzati userò un array di byte lungo ceil(NxM/8) e mi metterò lì con i valori esadecimali per sfruttare meno memoria possibile

[DanieleC88]

Ma su una matrice grossa una lunga serie di scambi può essere lenta, perciò pensavo fosse più semplice appoggiarsi ad una seconda matrice...

[banryu79]

L'ambiente/linguaggio è Java?
Beh, non ha importanza, va bene qualsiasi linguaggio.

Perchè non rappresenti la tua matrice con una struttura/classe del tipo:

//pseudo code
{
    int N;
    int M;
    boolean trasposta;
    array matrix;
}

A quel punto per fare la trasposta ti basta cambiare il valore del booleano.

Il metodo che legge la matrice consulta il valore del booleano: se la matrice non è trasposta legge ll'array in modo sequenziale, altrimenti legge l'array sfuttando i valori di M e N per "saltare di posizione" durante la lettura.

@EDIT:
Intendovo usare i valori di M e N dentro due cicli for annidati, in fase di lettura.

[Cait Sith]

il fatto è che se faccio un oggetto rallenta tutto
quindi volevo stare sui tipi primitivi (monodimensionali per avere un accesso più rapido possibile)

comunque alla fine ho fatto il mio metodo e funziona
siccome avevo letto che in java i boolean non si sa come vengono rappresentati (dipende dalla VM) allora ho fatto io un array di byte di dimensione NxM/8 in modo da mettere il flag per sapere se un elemento è stato scambiato
in realtà mi hanno detto che i vettori di booleani vengono rappresentati in modo efficiente così che 1 elemento=1 bit


faccio un ciclo for per ogni elemento dell'array/matrice
e per ogni elemento controllo il flag che mi dice se l'elemento è già stato scambiato
se è true (elemento già toccato) faccio un continue,
altrimenti parto con lo swap concatenato e per ogni posizione che tocco metto il flag a true
vado avanti così finchè non torno alla posizione di partenza (interna al ciclo)
dopodichè proseguo con l'elemento successivo

testato e funziona

[Unrue]

Originariamente inviato da Cait Sith

il fatto è che se faccio un oggetto rallenta tutto
quindi volevo stare sui tipi primitivi (monodimensionali per avere un accesso più rapido possibile)

comunque alla fine ho fatto il mio metodo e funziona
siccome avevo letto che in java i boolean non si sa come vengono rappresentati (dipende dalla VM) allora ho fatto io un array di byte di dimensione NxM/8 in modo da mettere il flag per sapere se un elemento è stato scambiato
in realtà mi hanno detto che i vettori di booleani vengono rappresentati in modo efficiente così che 1 elemento=1 bit


faccio un ciclo for per ogni elemento dell'array/matrice
e per ogni elemento controllo il flag che mi dice se l'elemento è già stato scambiato
se è true (elemento già toccato) faccio un continue,
altrimenti parto con lo swap concatenato e per ogni posizione che tocco metto il flag a true
vado avanti così finchè non torno alla posizione di partenza (interna al ciclo)
dopodichè proseguo con l'elemento successivo

testato e funziona

Mm, java non alloca la matrice per righe?

[Cait Sith]

un array 1 d lo puoi riempire come vuoi, per righe o per colonne, io seguo lo standard matlab che riempie per colonne
però in effetti mi sembra che l'estrazione dei pixel dalle immagini, java li metta nel buffer per righe