Discussion :

[progfou]

Bonjour tout le monde !
J'ai un problème très bête, mais je n'arrive pas à le résoudre de manière simple (et surtout efficace !).

Explication :
Dans une boucle (qui peut être très grande) je calcule une position notée x.
Cette position me sert à choisir un filtre et j'ai besoin de tester des bornes :

Code :

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

1
2
3
4
5
6
7
8
9
10
 
Pour k allant de 0 à 3
  Si x<0
  Alors m=0
  Sinon
    Si x > taille_max-1
    Alors m=taille_max-1
  Sinon
m=x-1+k
FinPour

Comment éviter le if() dans la boucle (incluse elle-même dans une autre) ?
Comment le faire de manière très rapide, sans branchement ?

Merci d'avance !

[souviron34]

je ne sais pas si ça accélérera vraiment..

Par contre tu peux déjà, avant de rentrer dans la boucle (mais tu l'as sans doute déjà fait ) définir le paramètre taillemax1 = taillemax - 1 (2 additions en moins).

Pour le reste je réfléchis

Note : je suppose que ton m tu t'en sert dans ta boucle ?

[souviron34]

Note2 : je ne crois pas que ça accélérera car la seule possibilité serait d'avoir une formule avec une multiplication, qui sera plus longue qu'avec un test...

Et sinon tu peux formuler autrement :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
Pour k = 0 à k = 3
 
    Si x >= 0 et x < taille_max 
            m=x-1+k ;
    Sinon
           Si x < 0
                 m = 0 ;
           Sinon
                 m = taille_max - 1
           Fin si
    Fin si
 
Fin Pour

Mais je ne crois pas que ce soit ce que tu cherches

[millie]

Si c'est pour du traitement des images... ce que je faisais pour éviter ce cas, c'est de ne pas m'occuper des bords.

Si par exemple j'ai un filtre qui a besoin des 6 pixels autour d'un pixel, je tronque le calcul tout autour de l'image.

On obtient quelque chose du genre :

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
22
23
24
25
26
27
28
29
30
31
32
void AreaOperator::compute(Image & out, const Image& in)
{
  if(out.getNumComponents() != in.getNumComponents())
    throw IllegalArgument("AreaOperator::compute");
 
  LocalAreaOperator& localAreaOp = getLocalAreaOperator();
 
  int leftpadding = getLeftPadding();
  int rightpadding = getRightPadding();
  int toppadding = getTopPadding();
  int bottompadding = getBottomPadding();
  int hauteur = in.getHeight();
  int largeur = in.getWidth();
 
  out.resize(largeur - (rightpadding + leftpadding), hauteur - (toppadding+bottompadding));
 
 
  for(int canal=0; canal< in.getNumComponents(); canal++)
    for(int j = toppadding; j< hauteur - bottompadding; j++)
    {
      for(int i = leftpadding; i< largeur - rightpadding; i++)
      {
        /*localAreaOp n'a pas besoin de faire de test des bornes
           car on est assuré par cette méthode que c'est appelé dans les bornes
        */
        out.setPixel(i - leftpadding, j - toppadding,
                     canal, localAreaOp.computeLocalArea(in, i,j, canal));
 
 
      }
    }
}

Donc pas de if.


Et pour obtenir quand même une image de la même taille, j'utilise un étendeur de bord :

Code C++ :

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

1
2
3
4
5
6
7
8
9
10
11
void AreaOperator::compute(Image& out, const Image& in, const BorderExtender& extender)
{
  Image tempo(in.getNumComponents());
  /*on étend le bord de l'image pour lui appliquer ensuite l'opération*/
  extender.extend(tempo, in, getTopPadding(),
                  getLeftPadding(),
                  getRightPadding(),
                  getBottomPadding());
 
  compute(out, tempo);
}

Mais je ne sais pas si c'était pour ça

[progfou]

Alors, merci pour toutes ces réponses !
Je n'ai pas pensé à faire le if des cas probables en amont .
Donc, première solution, je testerai (ça doit améliorer).

Ensuite, je ne peux pas me permettre de ne pas tenir compte des bords, car je dois avoir le même résultat avec les if() et sans (mais à une vitesse plus grande dans le second cas ).
Oui c'est pour du traitement d'image, mais je pense que ce problème est plus général, et qu'il doit y avoir une solution simple.

EDIT: au fait, les compilateurs n'arrivent pas à sortir le taille_max-1 seuls ?

[pseudocode]

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
Pour k allant de 0 à 3
    Si x<0 Alors
        m=0
    Sinon
        Si x > taille_max-1 Alors
            m=taille_max-1
        Sinon 
            m=x-1+k
        FinSi
    FinSi
FinPour

C'est quoi l'interet de faire un "if" sur la variable "x", alors que "x" ne varie pas dans la boucle ?

[progfou]

Il y en a une autre (celle-ci est imbriquée) dans laquelle x varie .

[pseudocode]

Il y en a une autre (celle-ci est imbriquée) dans laquelle x varie .

oui, mais ca ne change pas ma question. Quelle interet de tester "3 fois" la valeurs de "x" alors que "x" ne varie pas ?

autant faire un truc 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
 
Si x<0 Alors Boucle_fixe(0)
Sinon Si x>taille_max-1 Alors Boucle_fixe(taille_max-1)
Sinon Boucle_variable(x)
 
Procedure Boucle_fixe(m)
    Pour k allant de 0 à 3
        ...
    FinPour
FinProcedure
 
Procedure Boucle_variable(x)
    Pour k allant de 0 à 3
        m = x+k-1
        ...
    FinPour
FinProcedure

[progfou]

Je me pose du coup une autre question : hormis dans les cas déjà rencontrés, quand vous arrivez sur un algorithme que vous ne connaissez pas, comment l'analysez-vous ?
Y a-t-il des méthodes pour cela ?
Ou bien tout au feeling ?

EDIT: quand à ta réponse, pseudocode, je ne suis pas certain que cela change grand chose (je n'ai pas encore testé).
La boucle qui est au-dessus va s'exécuter des milliers de fois, donc conserver des if() me semble encore coûteux, et je ne suis pas sûr que de les sortir change fondamentalement le temps de calcul ?

[pseudocode]

Je me pose du coup une autre question : hormis dans les cas déjà rencontrés, quand vous arrivez sur un algorithme que vous ne connaissez pas, comment l'analysez-vous ?
Y a-t-il des méthodes pour cela ?
Ou bien tout au feeling ?

Avant de comprendre l'algo, j'essaye deja de comprendre le probleme.
Ensuite j'envisage une solution "naive" et je confronte a l'algo en question.

EDIT: quand à ta réponse, pseudocode, je ne suis pas certain que cela change grand chose (je n'ai pas encore testé).
La boucle qui est au-dessus va s'exécuter des milliers de fois, donc conserver des if() me semble encore coûteux, et je ne suis pas sûr que de les sortir change fondamentalement le temps de calcul ?

Non, c'est clair que sortir 3 pauvres "if" ca ne changera rien au perf (optimisation du compilateur, pipeline d'instructions, prediction de branches, ...). Pour gagner en perf il faut soit:
- faire moins de tour de boucle (précalculs, approximations, ...)
- faire des operations en parallele (sur un multicore)

[souviron34]

Avant de comprendre l'algo, j'essaye deja de comprendre le probleme.
Ensuite j'envisage une solution "naive" et je confronte a l'algo en question.

+10

Et en général (mais je parle pour moi, pôv physicien à l'origine ) je ne regarde rien de ce qui contient des maths plus compliquées que la dérivée seconde....

Et en général (quoique quelque fois après un certain temps...) je finis par trouver une solution naive, simple, et qui donne des résultats équivalents

Mais je précise en général

Car, même dans la résolution de problèmes complexes, je suis toujours (et jusqu'à maintenant l'expérience me donne raison) basé sur "ce qui se conçoit bien s'énonce clairement", et qu'un prof de maths de Maths Spé nous avait énoncé sous la forme : "plus une théorie est simple, plus elle a de chance d'être vraie", et comme en général quand elle est simple, elle est esthétiquement belle, et que je dois être un peu artiste, ben, je me creuse la cervelle....

(voir la fameuse démonstration du théorème de Fermat...)

[souviron34]

Non, c'est clair que sortir 3 pauvres "if" ca ne changera rien au perf (optimisation du compilateur, pipeline d'instructions, prediction de branches, ...).

bah quand même :

Si tu fais 20 millions de boucles,

Code :

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

1
2
   à chacune une boucle de 3
        à chaque tour 3 test

Au lieu de

Code :

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

1
2
3
 
   à chacune 3 tests
       à chacun une boucle de 3

tu gagnes 6*20 millions de tests....

En fait l'optimisation (ou la perte de temps) peut se nicher dans des petits trucs... Tout dépend de ce que tu as dans ta boucle.... Des choses que tu n'aurais pas besoin de recalculer, des allocations dynamiques (ça ça prend du temps), des calculs d'adresses ou de variables répétés, etc etc...


Tu me payes un peu et je te fais l'optimisation du code

[progfou]

Pas d'allocation dynamique, et je ne paie pas les autres pour faire mon travail .
La boucle est exécutée 350000 fois en moyenne (pour donner un ordre d'idée).
En revanche, il est sans doute possible pour moi de calculer x en amont, en tout cas, de ne pas le recalculer dans la boucle principale.

Là je n'ai pas le temps, mais si je le prend - le temps - je vous donnerai le calcul effectué, car je suis sûr qu'on peut faire quelque chose avec.

[pseudocode]

bah quand même : (...) tu gagnes 6*20 millions de tests....

Oui, c'est pour ca que j'ai dit qu'il fallait mieux inverser le "if" et la "boucle". C'est plus propre.

Mais, à la question "est-ce que ca va ameliorer les perfs", la réponse est "globalement non". Un bon compilateur et un processeur moderne vont optimiser tout cela et le ralentissement dû aux "if" va etre minime.

Pour gagner vraiment en perf, il faut revoir la "solution" algorithmique plutot que son "implementation".

[souviron34]

Je suis d'accord en partie, sauf avec :

Mais, à la question "est-ce que ca va ameliorer les perfs", la réponse est "globalement non". Un bon compilateur et un processeur moderne vont optimiser tout cela et le ralentissement dû aux "if" va etre minime.

Là non.. Tout dépend de ce que tu as dans la boucle, la pile, etc... Si tu as 250 variables, pas mal de trucs dynamiques, des varaibles étant des retours de fonctions etc... le compilo pourra pas améliorer grand chose tel quel...

Sinon bien entendu d'accord sur le fait que c'est l'algo le fond.

Mais l'implémentation est quelque fois vitale (et toi qui fais du traitement d'image, tu le sais : vaut mieux parcourir une image en horizontal qu'en vertical... : CQFD)

[progfou]

Au passage, j'ai deux "formules" qui me paraissent simplifiables, mais je n'arrive pas à le démontrer (juste une conjecture) :

Code :

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

1
2
3
4
5
 
(x<<16 + (y>>1))/y = 32768
et
(x<<15 + (y>>1))/y = 16384
si x=y/2

Peut-on le démontrer ?
Je pose l'hypothèse que c'est le cas...
(x, y)>(0, 0), et x et y divisibles par 16 (pas sûr que ça serve).
Ce n'est pas un exercice, c'est juste que je constate que ça a l'air d'être vrai, et que pour gagner (beaucoup) de temps dans mon code, remplacer ces expressions m'aiderait grandement...

[progfou]

Oubliez la question, j'ai évidement trouvé en quelques secondes après avoir passé un coup de flotte sur ma figure...