Discussion :

[timpoi]

Bonjour à tous,

Je débute en C (mais pas en programmation), et j'ai un problème que je n'arrive pas a résoudre…

Je programme un modèle d'évolution dans les réseaux trophiques, ce qui implique de manipuler des matrices et des vecteurs dans tous les sens. Ca se fait très bien en R, mais c'est long – j'ai donc décidé de le refaire en C.

Une des choses que je dois faire, c'est prendre un sous-ensemble d'une matrice quand une des espèces s'éteint (quand l'espèce i s'éteint, je dois enlever la ligne i et la colonne i d'une matrice – en R, ça prend une ligne…). J'ai essayé plusieurs solutions, mais sans grand succès. Est-ce qu'il existe une méthode générale pour le faire?

Merci d'avance

[matafan]

Ca dépend comment sont représentées tes matrices en mémoires. Ce sont de bêtes tableaux à deux dimensions ou quelque chose de plus sophistiqué ?

Si tu n'as pas encore prix le problème sous cet angle, tu peux peut-être chercher une représentation qui permet d'effectuer rapidement les opérations dont tu as le plus besoin.

[timpoi]

Ca dépend comment sont représentées tes matrices en mémoires. Ce sont de bêtes tableaux à deux dimensions ou quelque chose de plus sophistiqué ?

Si tu n'as pas encore prix le problème sous cet angle, tu peux peut-être chercher une représentation qui permet d'effectuer rapidement les opérations dont tu as le plus besoin.

Ce sont effectivement de bêtes tableaux a deux dimensions, et ça m'a semblé le plus naturel pour ce type de données (mais la encore, ça vient du fait que je viens de R/Matlab, et que ces deux langages utilisent des matrices).

Si je garde ces tableaux à deux dimensions, comment je devrai faire?

[quetzacoatl]

Comment sont codées tes matrices ?
Tu utilises un tableau de pointeur ou un tableau à une dimension?

[timpoi]

Comment sont codées tes matrices ?
Tu utilises un tableau de pointeur ou un tableau à une dimension?

Ce sont des matrices carrées, donc ça ressemble à

Code :

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

1
2
3
 
int div = 100;
double A[div][div];

Je dirais donc que c'est des tableaux à deux dimensions, et sans pointeurs. Etant vraiment débutant, je ne sais pas trop dans quelle mesure c'est important…

[quetzacoatl]

Il est en général déconseillé de déclarer un tableau avec une taille qui est une variable, voici par exemple l'avertissement que met gcc après la compilation de ton code:
Untitled1.c:4: warning: ISO C90 forbids variable-size array `A'

[timpoi]

Il est en général déconseillé de déclarer un tableau avec une taille qui est une variable, voici par exemple l'avertissement que met gcc après la compilation de ton code:
Untitled1.c:4: warning: ISO C90 forbids variable-size array `A'

Ok, merci pour l'info. Par contre, par définition, la taille de ma matrice va changer au cours du temps (nb d'espèces ^2), et à part en lui donnant une taille qui est une variable, je ne sais pas trop comment faire…

[quetzacoatl]

Ce que tu dois faire c'est une allocation dynamique pour pouvoir créer une matrice dont tu ne connais pas la taille avant la compilation(voir malloc() )

[timpoi]

Ce que tu dois faire c'est une allocation dynamique pour pouvoir créer une matrice dont tu ne connais pas la taille avant la compilation(voir malloc() )

OK, je vas donc faire comme ça. Par contre, ça ne résoud pas le problème de départ… Est-ce qu'il y a un moins simple de virer les lignes / colonnes d'une matrice construite de cette manière?

[matafan]

La encore ça va dépendre de ce que tu fais avec tes données. Quand tu dis supprimer la ligne et le colonne i, est-ce que ça veut dire que la dimension de ton tableau (div) diminue de 1 ? Est-ce que tu dois absolument conserver l'ordre des lignes et des colonnes, ou pas nécessairement ?

Est-ce qu'un algo de ce genre peut convenir :

- décrémenter div
- copier la ligne div par dessus la ligne i
- copier la colonne div par dessus la colonne i

Ce qui en clair veut dire mettre la dernière ligne à la place de la ligne à supprimer, et la dernière colonne à la place de la colonne à supprimer.

[diogene]

@ quetzacoatl :

Simple pas à ma connaissance, mais ça doit être parfaitement faisable en utilisant memcpy() ou des boucles

On ne peut pas utiliser memcpy() et il faut utiliser memmov()

Si on a une matrice carrée N*N, il faut supprimer 2*N-1 éléments de la matrice. On peut supprimer une ligne d'un coup et il reste N-1 éléments à supprimer. Cela fait N appels à memmov(), chaque appel devant déplacer une partie du tableau.
Je crois préférable de faire une boucle et déplacer directement les données.


Pour la suite, on traite le tableau 2D comme un tableau 1D donc l'élément [i][j] est en position k = i*N+j , k = 0..N*N

Si on veut supprimer la ligne et la colonne d'indice s (0..N-1), les éléments à éliminer sont en position k avec

Code :

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

1
2
3
4
- pour la ligne s : k = s*N + i   , i= 0..N-1    
  soit k/N == s
- pour la colonne s : k = i*N + s , i= 0..N-1  
  soit k%N == s

Il faut déplacer les autres éléments de position k de d positions vers le début du tableau.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
- si k < s , l'élément n'est pas à déplacer

- si s < k < s*N, 
   le nombre de déplacements est égal au nombre d'éléments de la colonne
   s qui précède k  soit tel que  i*N+s < k   ou   i < (k-s)/N. 
   Alors, d = (k-s)/N +1

- si (s+1)N <= k < N*N,
   le nombre de déplacements dû à la suppression de la colonne est (k-s)/N +1 
   celui dû à la suppression de la ligne est N-1 (un élément est commun à la colonne) 
   Alors d = N+(k-s)/N

Ceci correspond au code :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
void suppression(int * t, int s, int dim)
{
  int k;
  for(k=0; k<dim*dim;k++)
  {
    if(k>s && k<s*dim && k%dim !=s) t[k-(k-s)/dim-1] = t[k];
    if(k>s*dim+dim-1 && k%dim !=s)  t[k-dim-(k-s)/dim] = t[k];
  }
}
 
 int tab[N][N];
 ....
 suppression(tab[0],i,N);

** Attention au choix fait par le posteur d'utiliser les VLA du C99 : si le tableau devient trop grand, ce ne sera plus possible à cause de la taille limitée de la pile.

[souviron34]

Si on a une matrice carrée N*N, il faut supprimer 2*N-1 éléments de la matrice. On peut supprimer une ligne d'un coup et il reste N-1 éléments à supprimer. Cela fait N appels à memmov(), chaque appel devant déplacer une partie du tableau.
Je crois préférable de faire une boucle et déplacer directement les données.

Je suis d'accord, mais je le ferais un tout petit peu autrement (et un peu plus clairement ) :

Code C :

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
dec = 0
 
for ( j = 0 ; j < N ; j++ )
{
    if ( j == i )
       {
          dec = dec + N ;
       }
     else
      {
          for ( k = 0 : k < N ; k++ )
            {
                if (  k == i )
                  {
                      dec = dec + 1 ;
                  }
                else
                    tab[j*N + k - dec] = tab[j*N+k] ;
             }
     }
  }

[quetzacoatl]

Simple pas à ma connaissance, mais ça doit être parfaitement faisable en utilisant memcpy() ou des boucles