intérêt de faire un stockage 1D plutôt que 2D?

[invite5420aad7]

Bonjour,

j'ai comparé les deux types de stockage pour une matrice pleine à savoir :
-> on stocke la matrice dans un tableau
-> on stocke la matrice dans un tableau de tableau
La première forme de stockage semble être la meilleure au niveau temps d'exécution si j'effectue par exemple un produit matrice/vecteur.
Néanmoins je n'ai pas très bien compris pourquoi. Si quelqu'un a une réponse qu'il n'hésite pas à me la faire partage merci.

Cordialement.
-----

[Paraboloide_Hyperbolique]

Simplement cela est dû au fait que si l'on stocke la mémoire dans un tableau simple, toutes les données se trouveront dans une zone de mémoire contigüe, ce qui n'est pas le cas du stockage dans un tableau de tableau*.

Lorsque le processus fait appel à une donnée de cette mémoire, le système d'exploitation charge également dans le cache toute la mémoire qui lui contigüe.
Dans le cas du stockage dans un tableau simple, il y a de fortes chances que pour le prochain appel de donnée par le processus, cette donnée se trouve déjà dans le cache; qui est plus rapide d'accès que la mémoire vive. Il ne faudra donc pas re-remplir le cache.

Dans le cas du stockage dans tableau de tableau, ce n'est pas forcément le cas. Il faudra alors à nouveau charger des données de la mémoire vive dans le cache, ce qui prend du temps.

*Quoique cela dépende du langage de programmation employé, du compilateur, des options de celui-ci, du système d'exploitation et du hardware.

[invited1c1a33e]

Bonsoir, un tableau 2D c'est un tableau 1D auquel on applique un modulo. L'intérêt du tableau 2D, à part la clarté, c'est de vérifier que les indices ne dépassent pas les dimensions. Ces contrôles expliquent aussi un certain ralentissement.

Ce que dit Paraboloide Hyperbolique est également exact, les explications peuvent varier selon le langage utilisé

[invited1c1a33e]

Par exemple si l'on a:

int tab2D[10][10] ;

int tab1D[100] ;

tab2D[5][9] correspondra à tab1D[5*10+9] , ce qui explique aussi pourquoi une opération de copie est plus rapide en 1D, le programme ayant moins de calculs d'indices à faire.

au passage tab1D[53] correspond à tab2[53 /10][53 % 10] = tab2D[5][3] d'où le modulo dont je parlais.

[A voir en vidéo sur Futura]

[Jack]

le programme ayant moins de calculs d'indices à faire.

Je ne comprends pas trop la logique. Si on veut utiliser une matrice stockée dans un tableau 1D, il faudra bien faire le calcul à un moment ou à un autre pour trouver le rand de la donnée à partir de la ligne et de la colonne.
Je trouve qu'il doit être surement plus efficace de laisser le compilateur faire le travail avec un tableau 2D.

A+

[invited1c1a33e]

Je ne comprends pas trop la logique. Si on veut utiliser une matrice stockée dans un tableau 1D, il faudra bien faire le calcul à un moment ou à un autre pour trouver le rand de la donnée à partir de la ligne et de la colonne.
Je trouve qu'il doit être surement plus efficace de laisser le compilateur faire le travail avec un tableau 2D.

A+

Bonjour, je parlais d'une opération de copie de tableaux.

une opération de copie est plus rapide en 1D, le programme ayant moins de calculs d'indices à faire.

Si vous programmez par exemple le déplacement de deux cavaliers et d'un roi voulant capturer le roi adverse dans un jeu d'échecs, un échiquier 8x8 donc, vous pouvez déterminer le mouvement de la pièce en fonction de la case de départ sans utiliser d'indices à deux dimensions. Par exemple un cavalier s'avancera de +6,+10, +15, +17 ou reculera de -6,-10, -15 ou -17 dans un tableau de 0 à 63.

La ligne et la colonne vous serviront uniquement à afficher le déplacement et éventuellement entrer la position de départ. Tout ce que vous devrez contrôler c'est que l'indice ne descend pas en dessous de 0 et ne dépasse pas 63.

Comme un tel programme utilisera un grand nombre de copie de tableaux pour ses minimax ce sera certainement plus efficace de le coder en 1D qu'en 2D.

Par conséquent cela dépend également du programme que vous devez faire.

Sinon je suis d'accord qu'un compilateur bien conçu fera probablement de meilleurs choix d'optimisation qu'un programmeur (par exemple en utilisant des décalages de bits pour calculer les indices), mais passer de 2D à 1D permet justement de privilégier les opérations de copie au détriment des accès aux indices, qui ne sont pas forcément nécessaires comme on vient de le voir. Le compilateur s'occupe de la tactique et le programmeur de la stratégie

[invited1c1a33e]

J'oubliai qu'il faut quand même vérifier la position du cavalier car certains mouvements sont impossibles, mais cela ne change pas le reste du raisonnement. D'ailleurs les mouvements sont en principe pré-calculés.

[Jack]

concernant la copie de tableau, le C par exemple assure que toutes les données d'un tableau sont contiguës. Que ce soit un tableau à 1, 3 ou n dimensions, il suffit de connaitre le nombre total de données pour effectuer la copie en une seule opération.

A+

[invited1c1a33e]

En effet, ça dépend du langage utilisé.

[Paraboloide_Hyperbolique]

En fait, si mes souvenirs sont bons, le C garanti la contiguité d'un tableau de dimension n si celui-ci est statique:

Par exemple:

int tab[10][20];

Par contre, s'il est alloué dynamiquement cela n'est plus forcément le cas (quoique cela dépende d'autres facteurs comme le compilateur, le système d'exploitation...)

int **tab;
*tab = malloc(10*sizeof(int*));

for(int i = 0; i < 10; i++)
   {
   tab[i] = malloc(10*sizeof(int));
   }

[Jack]

En fait, si mes souvenirs sont bons, le C garanti la contiguité d'un tableau de dimension n si celui-ci est statique:

Oui.

Par contre, s'il est alloué dynamiquement cela n'est plus forcément le cas (quoique cela dépende d'autres facteurs comme le compilateur, le système d'exploitation...)

Dans ce cas rien ne garantit la contiguïté des données du tableau. Mais là, ça devient compliqué car il existe plusieurs possibilités pour le stockage dynamique d'un tableau multidimensionnel.

A+

[invite5420aad7]

merci beaucoup pour les explications.