Optimisation d'une boucle for

Version imprimable

Bonjour,
Je sollicite votre aide, je suis debutant et je voudrais savoir comment on peut optimiser ce bout de code

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
for (k = 0; k < 20; k++)
    {
    for (i = 1; i <= size; i++)
      {
      for (j = 1; j <= size; j++)
        {
        x[fonction(i, j, size)] = 
        (a * ( x[fonction(i-1, j, size)] + x[fonction(i+1, j, size)]
         +
         x[fonction(i, j-1, size)] + x[fonction(i, j+1, size)])
         +  
         x0[fonction(i, j, size)]) / c;
        }
      }
    fonction(b, x, size);
    }

02/11/2016, 00h53
foetus
:mrgreen: :mrgreen:
- Supprimer ta première boucle parce que k n'intervient pas dans les calculs (tu fais k fois la même chose :aie: :aie:)
- Tu sors tes cours de mathématiques :mrgreen: pour simplifier ton addition pondérée des proches en croix (... je pense à des sommes partielles)
02/11/2016, 01h11
louyxv

Justement a chaque tour de la boucle K j'execute une instruction, sinon je n'ai pas comrpis ce que vous vouliez dire pour le second point.
02/11/2016, 06h54
BufferBob

salut,

les maths c'est pas mon fort par contre je me dis que les appels de fonction() doivent couter cher, alors que quand on a fonction(i+1, j+1), au tour de boucle j suivant on relance le même calcul avec fonction(i+1, j), et idem pour i
du coup avoir un tableau temp[i*j] permettrait d'effectuer des accès mémoire au lieu de calculs potentiellement lourds, ça vaut peut-être la peine de creuser...

Voila donc j'ai reussi a virer les appels de fonctions et la boucle k, y a t-il un moyen d'optimiser encore plus?

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
for (i = 1; i <= grid_size*20 ; i++)
      {
      for (j = 1; j <= grid_size; j++)
        {
        x[ i % grid_size + 1 + (grid_size + 2) * j] 
        = 
        (a * ( x[ i % grid_size + (grid_size + 2) * j] + x[ i%grid_size + 2 + (grid_size + 2) * j]
         +
         x[ i % grid_size + 1  + (grid_size + 2) * (j-1)] + x[ i % grid_size + 1 + (grid_size + 2) * (j+1)])
         +  
         x0[ i % grid_size + 1 + (grid_size + 2) * j]) / c;
        }
		if( (i % 20 == 0))
		function(b, x, grid_size);
    }

02/11/2016, 18h18
droggo

Bonjour,

Tu calcules souvent i % grid_size et grid_size + 2. :)
02/11/2016, 18h48
louyxv

Le i%size est du a la suppression de la boucle k->20 ,et je ne vois pas comment l'optimiser, sinon pour grid_size + 2 il suffira de la stocker dans une variable.
02/11/2016, 23h15
droggo

Bonjour,

Citation:

Envoyé par louyxv

Le i%size est du a la suppression de la boucle k->20 ,et je ne vois pas comment l'optimiser, sinon pour grid_size + 2 il suffira de la stocker dans une variable.

idem pour l'autre, puisque tu la recalcules plusieurs fois dans le même bloc.
03/11/2016, 08h24
BufferBob

Citation:

Envoyé par louyxv

Voila donc j'ai reussi a virer les appels de fonctions et la boucle k, y a t-il un moyen d'optimiser encore plus?

difficile à dire, ça parait évident pour toi qui connais le code, mais vu d'ici je comprends pas un brin ce qu'est censé faire ce bout de code incomplet et qui pourrait bien être faux qui plus est (devrait pas y avoir un tableau glissant quelque part ?), tu dis que tu fais sauter la boucle k avec un modulo, pourquoi pas...

et avant de vouloir optimiser plus, est-ce que tu as testé ? quel est le gain concrètement ?
03/11/2016, 08h39
Ehonn

Donne aussi le compilateur utilisé, sa version ainsi que les options donnés.
03/11/2016, 11h53
picodev

Bonjour,
en attendant ta réponse sur les questions de mes vdd, j'imagine quand même que tu essayes de faire une convolution avec
$Formule mathématique$
J'imagine également que tu utilises un tableau 1D pour stocker ton image, que Fonction permet de passer des coordonnées 2D en 1D.

Donc la première chose que je dirai est : pourquoi faire une double boucle avec des appels à Fonction alors qu'une seule boucle suffirait ? OK, il n'y aurait pas moins de tours de boucle mais tu t'affranchirais carrément de l'appel à Fonction (la case du dessus est obtenue en retranchant size, au détails d'implémentation près, celle du dessous en ajoutant size, celle de gauche en retranchant 1, …).
Ça c'est le plus choquant. Ensuite garde ta boucle externe, pas la peine de rajouter un calcul de modulo.

Maintenant pourquoi vouloir précisément optimiser cette partie ? On optimise pas par hasard, on optimise les morceaux de code qui sont intéressant à optimiser = ceux qu'un outil (comme gperf) nous a permis d'isoler par exemple.
03/11/2016, 12h10
foetus

Citation:

Envoyé par picodev

tu essayes de faire une convolution avec
$Formule mathématique$

:mouarf: :mouarf: Même si ce ne sont que des suppositions, cela me fait doucement rire lorsqu'il n'a pas compris mon "sors tes cours de mathématiques" :mouarf: :mouarf:

Effectivement, on voit bien qu'il fait des sommes pondérées des voisins en croix (haut, bas, gauche et droite)

Mais comme l'a dit BufferBob :mrgreen:, difficile de répondre plus parce que c'est à l'intérieur de fonction qui se passe un changement qui oblige k calculs.
03/11/2016, 12h23
picodev

Oui, et c'est pour cela que je lui conseille de garder sa boucle externe et de ne pas essayer de l'intégrer dans les autres boucles à coup de modulo …