Discussion :

[ppaul128]

Bonjour,

Je cherche à coder une fonction qui qui prend en parametre deux doubles et renvoie true si la distance entre ces deux doubles est plus petite qu'une valeur determinée à l'avance.(settée via un #define seuil par ex)

Ma contrainte est que cette fonction soit la plus performante possible( pour du calcul numérique, cette opération sera effectuée plusieurs milliards de fois)...

J'allais partir sur une implementation classique en utilisant std::abs ou fabs pour mesurer la distance entre mes deux nombres, puis faire une comparaison avec le seuil, mais je me demandais s'il n'y avait pas des astuces pour faire plus rapide ? (du style équivalent des bitwise operations qu'on peut faire sur des types entiers ?)

Si qqu'un à un lien ou un article à conseiller là dessus, ou des astuces je suis preneur

merci!

[salseropom]

Je ne sais pas si ça va te faire gagner du temps mais une macro du genre

Code :

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

1
2
3
 
#define SEUIL 1e-10
#define COMPARE(a,b) ((fabs((a)-(b)) < SEUIL) ? true : false)

et de l'utiliser ainsi

Code :

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

1
2
 
bool test=COMPARE(a,b);

je n'ai pas testé si tu allais gagner du temps...

[ppaul128]

Je vais tester ça.
Merci

[JolyLoic]

Cette macro ne fait rien d'autre que la comparaison que tu as dit vouloir éviter... Et en plus, c'est une macro

De plus, a<b retourne un booleen. Je ne vois donc pas le besoin de faire (a<b ? true : false) là où (a<b) est équivalent. Ou alors, autant faire ((a<b?true : false) ? true : false)

Honnêtement, sur ce genre de choses, je ne crois pas qu'il y ait plus rapide que le fabs. Mais je crois surtout qu'il est assez improbable que le temps passé à cette opération ait un impact significatif sur le temps global de calcul.

[koala01]

Salut,

Je rejoint pleinement l'avis de JolyLoic (une fois n'est pas coutume )

Selon moi, bien plus que d'essayer de gagner une ou deux fréquence d'horloge avec un sucre syntaxique quelconque, tu devrais déjà essayer d'améliorer ton algorithme pour, quitte à y passer un tout petit peu de temps, te permettre d'éviter toutes les itérations inutiles...

Ainsi, s'il t'es possible de créer un algorithme basé - par exemple - sur la dichotomie, tu pourrait en arriver à ne faire le test qu'à peine plus de 32 fois...(s'il s'agit de rechercher une valeur parmis 4 milliards de valeurs possibles)

Pour rappel, la principale condition pour pouvoir utiliser la dichotomie est le fait que les valeurs soient triées...

Les deux "structures" les plus aptes à la permettre étant l'arbre binaire (idéal s'il est complet) et le tableau (éventuellement le std::vector) car ce dernier autorise un accès aléatoire aux données

Sinon, il est fort vraisemblable que les milliards de fois où ce test sera effectués viennent de plusieurs boucles imbriquées.

Encore une fois, si tu arrive à supprimer toutes les itérations, en fonction de la boucle dans laquelle tu te trouves, pour les valeurs dont tu sais "pertinemment" qu'elle donneront un résultat donné (soit vrai, soit faux), tu en arrivera à gagner énormément de temps d'exécution, et ce... malgré le fait que tu ajoute sans doute un test.

La raison est simple, pour arriver à un milliard d'exécutions, on peut envisager entre autre un algorithme proche de

Code :

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

1
2
3
4
5
6
7
8
pour i= 0 à 1000
    pour j = 0 à 1000
        pour k = 0 à 1000
            if( fabs(a<b)
                faire quelque chose
        fin pour
    fin pour
fin pour

Si tu ajoutes un test proche de

Code :

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

si i%2 = 0

(simple exemple) dans la boucle "pour i" et décidant d'entrer dans la boucle "pour j", tu réduira déjà de moitié les tests effectués

[nicroman]

De plus fabs est une fonction intrinsic... donc est traduite directement en assembleur....

Au pire si tu as besoin de le faire absoluement (profiling avant), tu veux juste tester l'exposant du double (dont la representation est: S * 1.F x 2^E)... donc... (1 bit de signe, 11 bits d'exposant, et 52 bits de mantisse)

Code c++ :

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

1
2
3
4
5
6
7
 
#define  SEUIL        0x0030000000000000
#define  EXP_MASK  0x7FF0000000000000
inline boolean _fast_double_test(const double& d)
{
     return ((*((const int64*)&d)) & EXP_MASK) < SEUIL;
}

Mais encore une fois, je ne suis même pas sur que ca te permette de grapiller quelques ns... Le &EXP_MASK revenant grosso merdo au fabs ....