Allocation dynamique 1 dimension vs 2 dimensions

Bonjour,

j'aimerai savoir si dans le cas d'un tableau à 2 dimensions alloué dynamiquement, un programme c accède à tab[i][j] directement ou bien s'il doit implicitement faire un calcul i*width+j.

Ma question concerne surtout, la différence de performance entre un tableau à une ou deux dimensions. Car si dans les 2 cas le programme doit faire un calcul d'indice (qu'il y ai une méthode implicite et l'autre explicite ne changeant rien pour moi) et que dans le cas des tableaux à 2 dimensions il faille faire toute une série de malloc, j'en déduirai donc qu'ils sont moins performants.

Que pouvez vous me dire à ce sujet?

merci.

Citation:

---

Envoyé par jokoss

j'aimerai savoir si dans le cas d'un tableau à 2 dimensions alloué dynamiquement, un programme c accède à tab[i][j]

---

Oui sans problème, même si un tableau alloué dynamiquement n'est pas réellement un tableau, ca ne reste qu'un pointeur qui pointe vers une adresse mémoire valide.

Citation:

---

Envoyé par jokoss

Ma question concerne surtout, la différence de performance entre un tableau à une ou deux dimensions. Car si dans les 2 cas le programme doit faire un calcul d'indice (qu'il y ai une méthode implicite et l'autre explicite ne changeant rien pour moi) et que dans le cas des tableaux à 2 dimensions il faille faire toute une série de malloc, j'en déduirai donc qu'ils sont moins performants.

---

Bin ce que je peut te dire, c'est qu'il faut faire dans le cas d'un tableau à 2 dimension, une allocation par indice.

Il est plus optimisé de faire une allocation "à une dimension" (enfin, c'est ce que j'ai lu sur le net et entre autre dans "programmez!" de mars dernier). Certainement car les blocs sont tous positionnés séquenciellement. D'un autre coté il est plus agréable d'accéder a un tableau avec des [][]... une fois de plus tout est question de choix.

A noter toutefois que l'astuce de l'allocation a une dimension ne marche qu'avec des lignes de même taille !

Bonjour,

Quand on parle d'un tableau alloué dynamiquement, on parle bien de :

Code:

---

1 2 3 4 5 6 7 8 9

size_t i; size_t width; size_t height; int ** tableau; /* D'abord la hauteur, j'aime bien les éléments d'une même ligne contigus */ tabeau = malloc(height * sizeof * tableau); for(i = 0; i < width; ++i) { tabeau[i] = malloc(height * sizeof * tableau[i]); }

---

Dans ce cas, lorsqu'on accède à tableau[j][i], il n'y a pas de calcul d'indice. En revanche, les données ne sont pas contigues en mémoire, en effet, on a fait une allocation par ligne dans le tableau.

Si on doit travailler sur le tableau d'un bloc, on risque de perdre du temps.


Il est aussi possible de manipuler un tableau un dimension comme s'il en avait deux en ayant à calculer une seule fois le décalage :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

size_t i; size_t width; size_t height; int ** tableau; tableau = malloc(height * sizeof( * tableau));   tableau[0] = malloc(width * height * sizeof( * tableau[0]));   /* attention, on commence à 1 */ for(i = 1; i < height ; ++i){ tableau[i] = tableau[i-1] + width ; }   /* et pour la desallocation */ free(tableau[0]); free(tableau);

---

Dans cet exemple, on commence par allouer un tableau qui correspond au début de chaque ligne.
Après, on alloue le tableau lui même, puis dans le premier tableau, on repère le début de chaque ligne du second.

On peut ainsi accéder à chaque élément individuellement tableau[j][i], ou au tableau en entier tableau[0].


On aurai pu aussi passer par deux variables, mais le résultat est beaucoup moins élégant :

Code:

---

1 2 3 4 5 6 7 8

int ** tableau; int * données tableau = malloc(height * sizeof( * tableau)); données = malloc(width * height * sizeof( * données ));   for(i = 0; i < height ; ++i){ tableau[i] = &données[i * width]; }

---

Merci pour vos réponses.

Donc pour éffectuer des parcourts de tableau il est préférable d'utiliser un tableau à une dimension. Mais si on doit accéder à des éléments de manière plus ou moins aléatoire alors il vaut mieux passer par un double indiçage qui permet d'éviter un calcul d'indice.

Merci également pour l'astuce de mabu. Je pense que je vais l'utiliser car dans mon cas je dois accéder un grand nombre de fois à des éléments sans ordre défini à l'avance.

Citation:

---

Envoyé par jokoss

Mais si on doit accéder à des éléments de manière plus ou moins aléatoire alors il vaut mieux passer par un double indiçage qui permet d'éviter un calcul d'indice.
.

---

ça n'est pas ce qui a été dit..

Ce qui a été dit est que c'était plus facile à lire..

Maintenant, que ce soit toi ou le compilo qui fasse le calcul, c'est kif-kif..

a[3][5] écrit en C comme ceci se traduit en assembleur par

adresse de a + 3*largeur + 5

ce qui est équivalent...

Parfait merci c'est juste ce que je voulais savoir depuis le début. J'avais mal compris une partie des réponses.

Donc dans tous les cas sans exeptions un tableau à 2 dimensions créé dynamiquement est moins performant qu'un tableau à une seule dimension où on fait soi-même le cacul i*largeur+j du fait des multiple allocations mémoire.