représente un tableau 2D comme tableau 1D

Question

Doublons possibles:
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

Je regardais un code dynamique moléculaire de mon copain bases l'autre jour et il avait représenté quelques-uns Données 2D en tant que tableau 1D. Ainsi, plutôt que d'avoir à utiliser deux index, il doit seulement en garder une trace, mais un peu de calcul est fait pour déterminer dans quelle position il se trouverait s'il était en 2D. Ainsi, dans le cas de ce tableau 2D:

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

Il serait représenté comme:

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

S'il avait besoin de savoir ce qui était en position (1,1) du tableau 2D qu'il ferait une certaine algèbre simple et obtenez 4.

Y at-il une amélioration des performances acquise en utilisant un tableau 1D plutôt qu'un tableau 2D. Les données dans les tableaux peuvent être appelées des millions de fois au cours du calcul.

J'espère que l'explication de la structure des données est claire ... si ce n'est pas faites le moi savoir et je vais essayer de mieux l'expliquer.

Merci :)

EDIT La langue est C

Answer 1

Jetez un oeil à Performance of 2-dimensional array vs 1-dimensional array

Answer 2

tableaux 2D sont souvent mises en œuvre sous forme de tableaux 1D. Parfois, les tableaux 2D sont implémentés par un tableau 1D de pointeurs sur des tableaux 1D. Le premier cas n'a évidemment aucune pénalité de performance par rapport à un tableau 1D, car il est identique à un tableau 1D. Le deuxième cas peut avoir une légère pénalité de performance en raison de l'indirection supplémentaire (et des effets subtils supplémentaires comme une diminution de la localisation du cache).

Il est différent pour chaque système quel type est utilisé, donc sans informations sur ce que vous utilisez, il n'y a vraiment aucun moyen d'être sûr. Je vous conseille de tester la performance si c'est vraiment important pour vous. Et si la performance n'est pas si importante, alors ne vous inquiétez pas. Pour les réseaux C, 2D sont des réseaux 1D avec du sucre syntaxique, donc la performance est identique.

Answer 3

Vous n'avez pas mentionné quelle langue cela ou comment le au sujet de tableau 2D sera mis en œuvre. En C 2D, les tableaux sont implémentés en tant que tableaux 1D où C effectue automatiquement l'arithmétique sur les index pour accéder à l'élément correct. Donc, il ferait ce que votre ami fait de toute façon dans les coulisses. Dans d'autres langages, un tableau 2d pourrait être un tableau de pointeurs vers les tableaux internes, auquel cas l'accès à un élément serait recherche de tableau + déréférencement de pointeur + recherche de tableau, qui est probablement plus lent que l'arithmétique d'index, bien qu'il ne vaut pas la peine d'être optimisé à moins de savoir que c'est un goulot d'étranglement.

Answer 4

oneD_index = 3 * y + x; 

Où x est la position dans la ligne et y la position dans la colonne. Au lieu de 3, vous utilisez votre largeur de colonne. De cette façon, vous pouvez convertir vos coordonnées 2D en coordonnées 1D.

Answer 5

pour une matrice de M largeur W et de hauteur 2-d on peut représenter comme une matrice 1-D de longueur W * H où chaque indice

(x,y) 

où x est la colonne et y est la ligne, du tableau 2-d est mappé à l'index

i=y*W + x 

dans le tableau 1D. De même, vous pouvez utiliser le mappage inverse:

y = i/W 
x = i % W 

. Si vous faites W une puissance de 2 (W = 2^m), vous pouvez utiliser le hack

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

où cette optimisation est limitée uniquement au cas où W est une puissance de 2. Un compilateur le plus probable manquez cette micro-optimisation donc vous devrez l'implémenter vous-même. Le module est un opérateur lent en C/C++, donc il est avantageux de le faire disparaître. De plus, avec les grandes baies 2-D, gardez à l'esprit que l'ordinateur les stocke en mémoire sous la forme d'une matrice 1-D et détermine les index en utilisant les mappages listés ci-dessus.

La façon d'accéder à la baie est plus importante que la façon dont vous déterminez ces mappages. Il y a deux façons de le faire, la colonne major et la ligne majeure. La façon dont vous traversez est plus important que que tout autre facteur car il détermine si vous utilisez la mise en cache à votre avantage. S'il vous plaît lire http://en.wikipedia.org/wiki/Row-major_order.