Discussion :

[jokoss]

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.

[Franck.H]

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.

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.

[TheDrev]

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 !

[Invité(e)]

Bonjour,

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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];
}

[jokoss]

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.

[souviron34]

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...