Discussion :

[bosonfuté]

Bonjour,

je suis en train de travailler sur un code où il faut ordonner des éléments d'une matrice (j'ordonne les éléments de toute la matrice.

En codant ça, je me demande si en général il est plus efficace, du point de vue du coût en ressources (et pas du point de vue de l'écriture du code), de travailler directement avec des tableaux à plusieurs dimensions, ou bien de travailler avec des tableaux unidimensionnels en mettant tout bout à bout. Evidemment, mettre tout bout à bout suppose de recalculer les indices et ça peut être laborieux à coder. Mais d'un autre côté, pour des opérations de style tri, il se pourrait que ça soit plus efficace ? (un gain en nombre de boucles imbriquées par exemple).

Quelqu'un sait-il me répondre ? Y a-t-il des scénarios où l'un est mieux et d'autre où c'est le contraire ? Est-ce pareil ? Est-ce qu'il y a une taille critique de tableau au delà de laquelle il vaut mieux effectivement choisir l'une ou l'autre des deux possibilités ?

[mith06]

Bonjour,

J'ai créer une petite API pour faire du calcul Matriciel en C. Le but étant de traduire le plus simplement du code Scilab/Matlab en C, pour le porter sur des systèmes embarqués (malloc nécessaire...).
Il s'est avéré que pour être strictement conforme aux fonctions les plus utilisées avec Scliab/Matlab (dans mon cas : diff sum cumsun linspace dft min max mean fftshift ce genre de truc...) le plus simple était d'utiliser un unique tableau organiser par colonne. Cad premier éléments du tableau <=> éléments de la première colonne, élément suivant <=> élément de la deuxième colonne etc.

Est-ce plus efficace que de déclarer un tableau à deux dimensions : JE NE PENSE PAS.
Est-ce moins efficace que de déclarer un tableau à deux dimensions : NON
Est-ce plus efficace que de déclarer un tableau de tableau : OUI

Est-ce l’implémentation la plus lisible : de mon point de vue OUI

[matafan]

Un tableau à deux dimension de N par M prend exactement la même place en mémoire qu'un tableau à une dimension de N*M. Et aucune différence de perf non plus pour accéder aux éléments. Une fois compilé, le code est le même.

[kwariz]

Bonjour,

si on parle de tableaux int Tab2D[M][N]; vs des tableaux int Tab1D[M*N]; il n'y aura aucune différence.
si on parle de tableaux dynamiquement alloués int **Tab2D vs int *Tab1D; alors il pourra y avoir une différence car dans le premier cas les éléments ne seront plus contigüs en mémoire.
En effet pour initialiser le premier il est typique de passer par :

Code :

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

1
2
3
4
int **Tab2D;
Tab2D=malloc(M*sizeof *Tab2D);
for(size_t i=0; i<M; ++i)
  Tab2D[i]=malloc(N*sizeof **Tab2D);

les Tab2D[i] sont des pointeurs qui peuvent pointer n'importe où en mémoire et parfois très éloignés les uns des autres.
Si la localité des données est importante il faut préférer l'autre solution :

Code :

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

int *Tab1D=malloc(M*N*sizeof *Tab1D);

Autant tu pourras faire un simple qsort(Tab1D, N*M, sizeof *Tab1D, compare_int) autant ce sera plus compliqué avec un Tab2D.

EDIT: à partir de C99 tu peux passer aussi par des pointeurs sur des tableaux VM ou VLA. Cela donnerait quelque chose du genre :

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
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define M 5
#define N 7
 
void fill_tab(size_t m, size_t n, int tab[m][n])
{
  for(size_t i=0; i<m; ++i)
    for(size_t j=0; j<n; ++j)
      tab[i][j]=i*n+j;
}
 
void print_tab(size_t m, size_t n, int tab[m][n])
{
  for(size_t i=0; i<m; ++i) {
    for(size_t j=0; j<n; ++j)
      printf("%2d ", tab[i][j]);
    printf("\n");
  }
}
 
int main(void)
{
  int (*tabMN)[M][N];
  tabMN=malloc(M*N*sizeof(int));
 
  fill_tab(M,N, *tabMN);
  print_tab(M,N, *tabMN);
 
  int (*tabNM)[N][M];
  tabNM=malloc(M*N*sizeof(int));
 
  fill_tab(N, M, *tabNM);
  print_tab(N, M, *tabNM);
 
  if (memcmp(tabMN, tabNM, N*M) == 0)
    printf("Identiques\n");
  else
    printf("Différents\n");
 
  free(tabMN);
  free(tabNM);
 
  return 0;
}

désolé pour le nom de mes variables ... mais c'est pour donner une idée.

[mido1951]

a mon avis il faut faire attention à la taille des tableaux, si on prend une grande taille j pense que le programme n'accepte pas une si grande valeur.

[bosonfuté]

Merci pour vos réponses éclairantes...

J'avais imaginé que le problème éventuel serait le nombre de boucles, croissant avec la dimension des tableaux.

Je n'avais pas pensé au problème de la contiguïté en mémoire pour les allocations dynamiques. Pourtant, j'aurais dû plus que d'autres, ayant à la base une formation en physique de la matière :-) En tout cas, c'est intéressant. Merci kwariz pour ta réponse qui m'apporte des précisions. Je vais tester un peu avec ton code pour me rendre compte par moi-même.

En tout cas merci.