Discussion :

[benhilal]

Bonjour,


J'ai un programme ou je doit utiliser des boucles imbriquer. Je veux faire K boucles avec K et un paramètre , la taille de chaque boucle dans un tableau N[K] , un tableau des indices i[k] :

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
for ( i[0]=0 ; i[0]<N[0] ;  i[0]++){
      for ( i[1]=0 ; i[1]<N[1] ; i[1]++){
            for ( i[2]=0 ; i[2]<N[2] ;  i[2]++){
                   for ( i[3]=0 ; i[3]<N[3] ; i[3]++){
                                         .
                                         .                  
                                         .
                                         for ( i[K-1]=0 ; i[K-1]<N[K-1] ; i[K-1]++){
                                                      ..........................
                                         }
                                         .
                                         .                  
                                         .
                  }
            }
      }
}

à chaque fois le K augmente le programme devenir lourde et je n'arrive pas à l'exécuter.
comment je peux réduire les boucles d'une manière optimal pour accélérer mon programme.


Merci pour votre aide

[Matt_Houston]

Quel est le problème originel auquel cet algorithme est destiné à apporter une solution ?

[ternel]

c'est probablement normal.
Si N[i] vaut 20 (pour tout i) et K vaut 10, tu fais 20 puissance 10 soit 10 240 milliards itérations.
Même si chacune prend un micro-seconde, ca fait encore plus de 10 millions de secondes, soit dans les 100 jours. (un jour fait 86400 secondes, un peu moins d'un dixième de millions)

On n'a rarement besoin de plus de 4 boucles.
essaye de limiter le nombre d'itérations.

Il y a des chances pour que tu fasses trop de calculs. As-tu réellement besoin d'explorer intégralement toutes les valeurs possibles d'un espace à K dimensions?

[benhilal]

supposons que j'ai une matrice M de dimension K et je veux calculer la dérivation partiel pour chaque dimension de cette matrice.
Alors pour la dimension K je dois utiliser K boucles pour chaque dériver partiel


si K=3 :

Code :

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

1
2
3
4
5
6
7
for(i2=0 ; i2<N[2] ; i2++){
    for(i1=0 ; i1<N[1] ; i1++){
        for(i0=1 ; i0<N[0] ; i0++){
            Dx0[i0-1][i1][i2] = M[i0][i1][i2] -M[i0-1][i1][i2]  ;
        }
    }
}

Code :

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

1
2
3
4
5
6
7
for(i0=0 ; i0<N[0] ; i0++){
    for(i2=0 ; i2<N[2] ; i2++){
        for(i1=1 ; i1<N[1] ; i1++){
            Dx1[i0][i1-1][i2] = M[i0][i1][i2] -M[i0][i1-1][i2]  ;
        }
    }
}

Code :

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

1
2
3
4
5
6
7
for(i1=0 ; i1<N[1] ; i1++){
    for(i0=0 ; i0<N[0] ; i0++){
        for(i2=1 ; i2<N[2] ; i2++){
            Dx2[i0][i1][i2-1] = M[i0][i1][i2] -M[i0][i1][i2-1]  ;
        }
    }
}

je cherche une méthode générale pour diminuer la quantité de code



Merci pour votre aide.

[ternel]

C'est presque la forme la plus courte.
Tu peux utiliser une expression conditionnelle: (condition ? valeur_si_vrai : valeur_si_faux ). Cela te permettrait de regrouper tous les cas ensembles.

Par ailleurs, pour des raisons de performances, il vaut mieux parcourir "par la droite" en premier:

Code :

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

1
2
3
4
5
6
7
for( i ...) {
  for( j ...) {
    for( k ...) {
      utiliser M[i][j][k];
    }
  }
}

Mieux encore, je t'invite à grouper dans un seul tableau toutes les dimensions.

Tu peux faire commencer par faire une fonction dédiée pour la dérivée partielle selon une dimension précise:

Code :

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

1
2
3
4
5
6
7
8
9
10
 
void derive_partielle(data_type const *** matrice, data_type *** derivee, size_t dimension_derivee, size_t* bounds)
  for (size_t i0 = 0; i0 < bounds[0] -  (dimension_derivee==0 ? 1 : 0); i0++) {
    for (size_t i1 = 0; i1 < bounds[1] - (dimension_derivee==1 ? 1 : 0); i1++) {
      for (size_t i2 = 0; i2 < bounds[2] -  (dimension_derivee==2 ? 1 : 0); i2++) {
        derivee[i0][i1][i2] = matrice[i0][i1][i2] - matrice[i0][i1][i2]  ;
      }
    }
  }
}

Ce qui te permettrait d'écrire tes trois séries de boucles sous la forme:

Code :

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

1
2
3
derive_partielle(M, Dx0, 0, N);
derive_partielle(M, Dx1, 1, N);
derive_partielle(M, Dx2, 2, N);

Et tu t'apercois qu'un tableau serait pratique:

Code :

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

1
2
3
4
data_type derivees_partielles[ N[0] ][ N[1] ][ N[2] ] [ 3 ];
for (size_t d = 0; d < 3; d++) {
    derive_partielle(M, Dx[d], d, N);
}

[pvincent]

En fait, c'est le genre de problème dont la solution la plus simple consiste à utiliser une fonction récursive, c'est à dire une fonction qui contient un appel à elle-même.
Il faut alors prévoir un compteur pour arrêter les itérations quand toutes les dimensions ont été traitées.

[ternel]

Ma réponse est faite pour le cas précis de K = 3, pour une solution plus générale, en effet, la récursion risque d'être utile.