Représenter un tableau 2D sous la forme d’un tableau 1D

Doublons possibles:
Mettre en œuvre une masortingce, ce qui est plus efficace – en utilisant un tableau de tableaux (2D) ou un tableau 1D?
Performance d’un tableau à 2 dimensions par rapport à un tableau à 1 dimension

L’autre jour, je regardais l’un des codes de la dynamic moléculaire de mon ami. Il avait présenté des données 2D sous forme de masortingce 1D. Ainsi, plutôt que d’avoir à utiliser deux index, il ne doit en garder qu’un, mais un peu de maths est fait pour déterminer quelle position il serait s’il était 2D. Donc 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, il ferait une algèbre simple et obtiendrait 4.

Existe-t-il une amélioration des performances obtenue 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 pendant le calcul.

J’espère que l’explication de la structure des données est claire … sinon, laissez-moi savoir et je vais essayer de mieux l’expliquer.

Je vous remercie 🙂

EDIT La langue est C

Examinez les performances d’un tableau à 2 dimensions par rapport à un tableau à 1 dimension

Pour un tableau 2-d de largeur W et de hauteur H, vous pouvez le représenter sous la forme d’un tableau 1-d de longueur W * H où chaque index

  (x,y) 

où x est la colonne et y est la ligne, du tableau 2D est mappé à l’index

 i=y*W + x 

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

 y = i / W x = i % W 

. Si vous donnez à 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 manquerait probablement cette micro-optimisation, vous devrez donc la mettre en œuvre vous-même.

Modulus est un opérateur lent en C / C ++, il est donc avantageux de le faire disparaître.

De plus, avec les grands tableaux 2D, gardez à l’esprit que l’ordinateur les stocke en mémoire sous la forme d’un tableau 1D et calcule les index à l’aide des mappages que j’ai énumérés ci-dessus.

Le mode d’access au tableau est bien plus important que la façon dont vous déterminez ces mappages. Il y a deux façons de le faire, la colonne majeure et la rangée principale. La façon dont vous traversez est plus importante que tout autre facteur, car elle détermine si vous utilisez la mise en cache à votre avantage. Veuillez lire http://en.wikipedia.org/wiki/Row-major_order .

Les tableaux 2D sont souvent implémentés en tant que tableaux 1D. Parfois, les tableaux 2D sont mis en œuvre par un tableau 1D de pointeurs vers des tableaux 1D. Le premier cas n’a évidemment aucune incidence sur les performances par rapport à un tableau 1D, car il est identique à un tableau 1D. Le second cas peut avoir une légère pénalité de performances due à l’indirection supplémentaire (et à des effets subtils supplémentaires tels qu’une localisation réduite du cache).

Le type utilisé varie d’un système à l’autre. Par conséquent, sans informations sur ce que vous utilisez, vous ne pouvez vraiment pas en être sûr. Je conseillerais simplement de tester la performance si c’est vraiment important pour vous. Et si la performance n’est pas si importante que cela, ne vous inquiétez pas.

Pour C, les tableaux 2D sont des tableaux 1D avec du sucre syntaxique, de sorte que les performances sont identiques.

Vous n’avez pas mentionné la langue utilisée ni la manière dont le tableau 2D serait implémenté. En C, les tableaux 2D sont réellement implémentés en tant que tableaux 1D, où C exécute automatiquement l’arithmétique sur les indices pour accéder au bon élément. Cela ferait donc ce que votre ami fait de toute façon dans les coulisses.

Dans d’autres langues, un tableau 2d peut être un tableau de pointeurs vers les tableaux internes. Dans ce cas, accéder à un élément serait tableau lookup + pointeur dereference + tableau lookup, ce qui est probablement plus lent que l’arithmétique d’index, bien que cela ne vaille pas la peine d’être optimisé sauf si vous savez qu’il s’agit d’un goulot d’étranglement.

 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.