Vérification de bornes

Version imprimable

25/07/2007, 17h15
progfou

Vérification de bornes
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:

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 !
25/07/2007, 18h09
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 8O 8-)

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

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:

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 ;)

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:

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:

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 :aie:

25/07/2007, 18h57
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 ?

Code:

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 ?

25/07/2007, 19h11
progfou

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

Citation:

Envoyé par progfou

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:

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

25/07/2007, 21h28
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 ?
25/07/2007, 23h17
pseudocode

Citation:

Envoyé par 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 ? :)

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.

Citation:

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)
26/07/2007, 01h07
souviron34

Citation:

Envoyé par pseudocode

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 :aie: ) 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 :P

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...)
26/07/2007, 01h11
souviron34
Citation:

Envoyé par pseudocode

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:

1 2 à chacune une boucle de 3 à chaque tour 3 test
Au lieu de
Code:

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 ;)
26/07/2007, 08h22
progfou

Pas d'allocation dynamique, et je ne paie pas les autres pour faire mon travail :aie:.
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.
26/07/2007, 09h39
pseudocode

Citation:

Envoyé par souviron34

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".
26/07/2007, 10h35
souviron34

Je suis d'accord en partie, sauf avec :

Citation:

Envoyé par pseudocode

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)
26/07/2007, 14h36
progfou
Au passage, j'ai deux "formules" qui me paraissent simplifiables, mais je n'arrive pas à le démontrer (juste une conjecture) :
Code:

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...
26/07/2007, 16h10
progfou

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