Rappresentando una matrice 2D come un array 1D

Question

Possibili duplicati:
Implementing a matrix, which is more efficient - using an Array of Arrays (2D) or a 1D array?
Performance of 2-dimensional array vs 1-dimensional array

Stavo guardando uno dei dinamica molecolare del mio amico basi di codice l'altro giorno e aveva rappresentato un po ' Dati 2D come array 1D. Quindi, piuttosto che dover usare due indici, deve solo tenere traccia di uno, ma un po 'di matematica è fatta per capire in che posizione sarebbe se fosse 2D. Quindi, nel caso di questa matrice 2D:

two_D = [[0, 1, 2], 
     [3, 4, 5]] 

Sarebbe essere rappresentata come:

one_D = [0, 1, 2, 3, 4, 5] 

Se aveva bisogno di sapere che cosa era in posizione (1,1) della matrice 2D che avrebbe fatto un po 'di semplice algebra e ottieni 4.

C'è qualche aumento di prestazioni ottenuto usando un array 1D piuttosto che un array 2D. I dati negli array possono essere chiamati milioni di volte durante il calcolo.

Spero che la spiegazione della struttura dati sia chiara ... se non me lo faccia sapere, cercherò di spiegarlo meglio.

Grazie :)

EDIT Il linguaggio è C

Answer 1

Date un'occhiata a Performance of 2-dimensional array vs 1-dimensional array

Answer 2

array Spesso 2D sono implementate come array 1D. A volte gli array 2D sono implementati da un array 1D di puntatori agli array 1D. Il primo caso ovviamente non ha penalizzazioni rispetto a un array 1D, perché è identico a un array 1D. Il secondo caso potrebbe avere una leggera penalizzazione delle prestazioni a causa dell'extetrection aggiuntivo (e ulteriori effetti sottili come la riduzione della localizzazione della cache).

È diverso per ogni sistema che tipo viene utilizzato, quindi senza informazioni su ciò che si sta utilizzando non c'è davvero alcun modo per esserne sicuri. Ti consiglio di testare le prestazioni solo se è davvero importante per te. E se le prestazioni non sono così importanti, non preoccuparti.

Per C, gli array 2D sono array 1D con zucchero sintattico, quindi le prestazioni sono identiche.

Answer 3

Lei non ha menzionato che la lingua è per quanto riguarda questo o come la matrice 2D sarebbe stata attuata. In C gli array 2D sono in realtà implementati come array 1D in cui C esegue automaticamente l'aritmetica sugli indici per accedere all'elemento giusto. Quindi farebbe ciò che il tuo amico fa comunque dietro le quinte.

In altri linguaggi una matrice 2D può essere una matrice di puntatori agli array interni, nel qual caso l'accesso a un elemento sarebbe la ricerca di matrice + la dereferenziazione puntatore + la ricerca matrice, che è probabilmente più lenta dell'aritmetica dell'indice, anche se sarebbe non vale la pena di essere ottimizzato a meno che non si sappia che questo è un collo di bottiglia.

Answer 4

oneD_index = 3 * y + x; 

Dove x è la posizione all'interno della riga y la posizione nella colonna. Invece di 3 usi la larghezza della tua colonna. In questo modo puoi convertire le tue coordinate 2D in una coordinata 1D.

Answer 5

Per un 2-d array di larghezza W e altezza H è possibile rappresentate come 1-d array di lunghezza W * H dove ciascun indice

(x,y) 

dove x è la colonna ed y è il riga, della matrice 2-d viene mappata all'indice

i=y*W + x 

nell'array 1-D. Analogamente è possibile utilizzare la mappatura inversa:

y = i/W 
x = i % W 

. Se si effettua W una potenza di 2 (W = 2^m), è possibile utilizzare il mod

y = i >> m; 
x = (i & (W-1)) 

dove questa ottimizzazione è limitata solo per il caso in cui W è una potenza di 2. Un compilatore molto probabilmente perdi questa micro-ottimizzazione, quindi dovresti implementarla tu stesso.

Il modulo è un operatore lento in C/C++, quindi far scomparire è vantaggioso.

Inoltre, con gli array 2D di grandi dimensioni tenere presente che il computer li archivia in memoria come un array 1-d e fondamentalmente calcola gli indici utilizzando le mappature I elencate sopra.

Molto più importante del modo in cui si determinano questi mapping è l'accesso all'array. Ci sono due modi per farlo, colonna principale e riga maggiore. Il modo in cui si attraversa è più importante di rispetto a qualsiasi altro fattore poiché determina se si sta utilizzando nella cache a proprio vantaggio. Si prega di leggere http://en.wikipedia.org/wiki/Row-major_order.