Est-ce une bonne pratique de remplacer la division par la multiplication lorsque cela est possible?

73

Chaque fois que j'ai besoin d'une division, par exemple d'une vérification de condition, je voudrais reformuler l'expression de la division en multiplication, par exemple:

Version originale:

if(newValue / oldValue >= SOME_CONSTANT)

Nouvelle version:

if(newValue >= oldValue * SOME_CONSTANT)

Parce que je pense que cela peut éviter:

  1. Division par zéro

  2. Débordement quand oldValueest très petit

Est-ce correct? Y at-il un problème pour cette habitude?

ocomfd
la source
41
Attention, avec les nombres négatifs, les deux versions vérifient des choses totalement différentes. Êtes - vous certain oldValue >= 0?
user2313067
37
Selon le langage utilisé (mais plus particulièrement avec C), quelle que soit l'optimisation à laquelle vous puissiez penser, le compilateur peut généralement le faire mieux, -OU- , a suffisamment de sens pour ne pas le faire du tout.
Mark Benningfield
63
Il n'est jamais "une bonne pratique" de toujours remplacer le code X par le code Y lorsque X et Y ne sont pas sémantiquement équivalents. Mais il est toujours bon de regarder X et Y, d’allumer le cerveau, de réfléchir aux exigences , puis de décider laquelle des deux solutions est la plus correcte. Et après cela, vous devriez également vous demander quels tests sont nécessaires pour vérifier que vous avez bien compris les différences sémantiques.
Doc Brown le
12
@MarkBenningfield: Quoi qu'il en soit, le compilateur ne peut pas optimiser la division par zéro. L '"optimisation" à laquelle vous songez est "l'optimisation de la vitesse". Le PO envisage un autre type d'optimisation: l'évitement des bogues.
Slebetman
25
Le point 2 est faux. La version d'origine peut déborder pour les petites valeurs, mais la nouvelle version peut déborder pour les grandes valeurs. Par conséquent, aucune n'est plus sûre dans le cas général.
JacquesB

Réponses:

74

Deux cas courants à considérer:

Arithmétique entière

Évidemment, si vous utilisez une arithmétique entière (qui tronque), vous obtiendrez un résultat différent. Voici un petit exemple en C #:

public static void TestIntegerArithmetic()
{
    int newValue = 101;
    int oldValue = 10;
    int SOME_CONSTANT = 10;

    if(newValue / oldValue > SOME_CONSTANT)
    {
        Console.WriteLine("First comparison says it's bigger.");
    }
    else
    {
        Console.WriteLine("First comparison says it's not bigger.");
    }

    if(newValue > oldValue * SOME_CONSTANT)
    {
        Console.WriteLine("Second comparison says it's bigger.");
    }
    else
    {
        Console.WriteLine("Second comparison says it's not bigger.");
    }
}

Sortie:

First comparison says it's not bigger.
Second comparison says it's bigger.

Arithmétique en virgule flottante

Outre le fait que la division peut produire un résultat différent lorsqu'elle se divise par zéro (elle génère une exception, contrairement à la multiplication), elle peut également entraîner des erreurs d'arrondi légèrement différentes et un résultat différent. Exemple simple en C #:

public static void TestFloatingPoint()
{
    double newValue = 1;
    double oldValue = 3;
    double SOME_CONSTANT = 0.33333333333333335;

    if(newValue / oldValue >= SOME_CONSTANT)
    {
        Console.WriteLine("First comparison says it's bigger.");
    }
    else
    {
        Console.WriteLine("First comparison says it's not bigger.");
    }

    if(newValue >= oldValue * SOME_CONSTANT)
    {
        Console.WriteLine("Second comparison says it's bigger.");
    }
    else
    {
        Console.WriteLine("Second comparison says it's not bigger.");
    }
}

Sortie:

First comparison says it's not bigger.
Second comparison says it's bigger.

Au cas où vous ne me croyez pas, voici un violon que vous pouvez exécuter et voir par vous-même.

D'autres langues peuvent être différentes. Gardez toutefois à l'esprit que C #, comme de nombreux langages, implémente une bibliothèque à virgule flottante au standard IEEE (IEEE 754) . Vous devriez donc obtenir les mêmes résultats dans d'autres temps d'exécution normalisés.

Conclusion

Si vous travaillez en greenfield , vous allez probablement bien.

Si vous travaillez sur du code hérité et que l'application est une application financière ou une autre application sensible qui effectue des calculs et est tenue de fournir des résultats cohérents, faites très attention lorsque vous modifiez des opérations. Si vous devez le faire, assurez-vous de disposer de tests unitaires capables de détecter d'éventuels changements subtils dans l'arithmétique.

Si vous ne faites que compter les éléments dans un tableau ou d’autres fonctions de calcul générales, tout ira bien. Je ne suis pas sûr que la méthode de multiplication rend votre code plus clair, cependant.

Si vous implémentez un algorithme dans une spécification, je ne changerais rien du tout, pas uniquement à cause du problème d'erreurs d'arrondi, mais pour que les développeurs puissent revoir le code et faire correspondre chaque expression à la spécification pour s'assurer qu'il n'y a pas d'implémentation. défauts.

John Wu
la source
41
Deuxième le bit financier. Ce type de commutateur demande aux comptables de vous poursuivre avec des fourches. Je me souviens de 5 000 lignes dans lesquelles je devais faire plus d'efforts pour garder les fourches plus loin que pour trouver la "bonne" réponse - ce qui était en fait un peu faux. Être hors-jeu par 0,01% n'avait pas d'importance, des réponses absolument cohérentes étaient obligatoires. Ainsi, j'ai été obligé de faire le calcul de manière à provoquer une erreur d'arrondi systématique.
Loren Pechtel
8
Pensez à acheter des bonbons à 5 centimes (il n'en existe plus.) Achetez 20 pièces. La réponse "correcte" n'était pas une taxe car il n'y avait aucune taxe sur 20 achats d'une pièce.
Loren Pechtel
24
@ LorenPechtel, c'est parce que la plupart des systèmes fiscaux prévoient (pour des raisons évidentes) que la taxe est perçue par transaction, et que la taxe est due par tranches d'au moins la plus petite pièce du royaume, et que les montants fractionnaires sont arrondis en faveur du contribuable. Ces règles sont "correctes" car elles sont légales et cohérentes. Les comptables avec fourches savent probablement quelles sont les règles en réalité d’une manière que les programmeurs ne connaîtront pas (à moins qu’ils soient également des comptables expérimentés). Une erreur de 0,01% entraînera probablement une erreur d’équilibrage et il est illégal d’avoir une erreur d’équilibrage.
Steve
9
Parce que je n'avais jamais entendu le terme « greenfield» auparavant, je l'ai cherché. Wikipedia dit que c'est "un projet qui ne souffre d'aucune contrainte imposée par des travaux antérieurs".
Henrik Ripa
9
@Steve: Mon patron a récemment comparé "greenfield" à "brownfield". J'ai remarqué que certains projets ressemblent davantage à "Blackfield" ... :-D
DevSolar
25

J'aime votre question car elle couvre potentiellement de nombreuses idées. Dans l’ensemble, je soupçonne que la réponse est cela dépend probablement des types impliqués et de la plage de valeurs possible dans votre cas particulier.

Mon instinct initial est de réfléchir à la style , c.-à-d. votre nouvelle version est moins claire pour le lecteur de votre code. J'imagine que je devrais réfléchir pendant une seconde ou deux (ou peut-être plus longtemps) pour déterminer l'intention de votre nouvelle version, alors que votre ancienne version est immédiatement claire. La lisibilité est un attribut important du code, votre nouvelle version a donc un coût.

Vous avez raison, la nouvelle version évite une division par zéro. Bien sûr, vous n’avez pas besoin d’ajouter une garde (dans le sens de if (oldValue != 0)). Mais est-ce que cela a du sens? Votre ancienne version reflète un rapport entre deux nombres. Si le diviseur est égal à zéro, votre ratio n'est pas défini. Cela peut être plus significatif dans votre situation, à savoir. vous ne devriez pas produire de résultat dans ce cas.

La protection contre les débordements est discutable. Si vous savez qu'il newValueest toujours supérieur à oldValue, alors vous pourriez peut-être présenter cet argument. Cependant, il peut y avoir des cas où (oldValue * SOME_CONSTANT)débordera également. Donc, je ne vois pas beaucoup de gain ici.

Il se peut que vous obteniez de meilleures performances car la multiplication peut être plus rapide que la division (sur certains processeurs). Cependant, de nombreux calculs tels que ceux-ci seraient nécessaires pour obtenir un gain significatif, à savoir. méfiez-vous de l'optimisation prématurée.

Si l’on réfléchit à tout ce qui précède, je pense qu’en général, il n’ya pas grand chose à gagner avec votre nouvelle version par rapport à l’ancienne version, en particulier compte tenu de la réduction de la clarté. Cependant, il peut y avoir des cas spécifiques où il y a un avantage.

dave
la source
16
Ehm, la multiplication arbitraire étant plus efficace que la division arbitraire ne dépend pas vraiment du processeur, pour les machines du monde réel.
Déduplicateur
1
Il y a aussi le problème de l'arithmétique entier vs virgule flottante. Si le rapport est fractionnaire, la division doit être effectuée en virgule flottante, ce qui nécessite un transtypage. Manquer le casting entraînera une erreur involontaire. S'il se trouve que la fraction est un rapport entre deux petits entiers, leur réorganisation permet de procéder à la comparaison en arithmétique entière. (A quel moment vos arguments s'appliqueront.)
lundi
@ rwong Pas toujours. Plusieurs langues font des divisions entières en supprimant la partie décimale, aucune conversion n'est donc nécessaire.
T. Sar - Rétablir Monica le
@ T.Sar La technique que vous décrivez et la sémantique décrite dans la réponse sont différentes. La sémantique indique si le programmeur souhaite que la réponse soit une valeur décimale ou fractionnaire; la technique que vous décrivez est la division par multiplication réciproque, qui est parfois une approximation parfaite (substitution) d'une division entière. Cette dernière technique est généralement appliquée lorsque le diviseur est connu à l'avance, car la dérivation de l'inverse d'un nombre entier (décalé de 2 ** 32) peut être effectuée au moment de la compilation. Faire cela au moment de l'exécution ne serait pas bénéfique, car cela coûterait plus cher en ressources processeur.
Rwong
22

Non.

J'appellerais probablement cette optimisation prématurée , au sens large, que l'on optimise les performances , comme le dit l'expression, ou tout autre élément pouvant être optimisé, tel que le nombre de bord , les lignes de code ou encore plus largement, des choses comme "design".

L'implémentation de ce type d'optimisation en tant que procédure d'exploitation standard met en péril la sémantique de votre code et cache potentiellement les limites. Les cas marginaux que vous jugez utile d'éliminer en silence devront peut-être quand même être explicitement traités . Et, il est infiniment plus facile de résoudre les problèmes autour des contours bruyants (ceux qui jettent des exceptions) sur ceux qui échouent en silence.

Et, dans certains cas, il est même avantageux de "dé-optimiser" pour des raisons de lisibilité, de clarté ou d'explicite. Dans la plupart des cas, vos utilisateurs ne remarqueront pas que vous avez enregistré quelques lignes de code ou de cycles de processeur pour éviter la gestion des incidents et des exceptions. Code Maladroit ou à défaut en silence, d'autre part, va affecter les gens - vos collègues à tout le moins. (Et aussi, par conséquent, le coût de la construction et de la maintenance du logiciel.)

Par défaut, tout ce qui est plus "naturel" et lisible par rapport au domaine de l'application et au problème spécifique. Restez simple, explicite et idiomatique. Optimiser selon les besoins pour obtenir des gains importants ou pour atteindre un seuil d'utilisation légitime.

Notez également que les compilateurs optimisent souvent la division pour vous, quand vous pouvez le faire en toute sécurité .

svidgen
la source
11
-1 Cette réponse ne correspond pas vraiment à la question, qui concerne les pièges potentiels de la division - rien à voir avec l'optimisation
Ben Cottrell
13
@ BenCottrell Il va parfaitement bien. Le piège est de valoriser des optimisations de performances inutiles au détriment de la maintenabilité. De la question "y at-il un problème pour cette habitude?" - Oui. Cela mènera rapidement à l'écriture de charabia absolu.
Michael
9
@Michael, la question ne concerne pas non plus l'une de ces choses , mais plutôt la correction de deux expressions différentes, chacune ayant une sémantique et un comportement différents, mais destinées à répondre aux mêmes exigences.
Ben Cottrell
5
@ BenCottrell Peut-être pourriez-vous me dire où, dans la question, il est fait mention de l'exactitude?
Michael
5
@BenCottrell Vous auriez dû juste dire «je ne peux pas» :)
Michael
13

Utilisez celui qui est le moins buggé et qui a un sens plus logique.

En règle générale , la division par une variable est de toute façon une mauvaise idée, car le diviseur peut être égal à zéro.
La division par une constante dépend généralement de la signification logique.

Voici quelques exemples pour montrer que cela dépend de la situation:

Division bonne:

if ((ptr2 - ptr1) >= n / 3)  // good: check if length of subarray is at least n/3
    ...

Multiplication mauvaise:

if ((ptr2 - ptr1) * 3 >= n)  // bad: confusing!! what is the intention of this code?
    ...

Multiplication bonne:

if (j - i >= 2 * min_length)  // good: obviously checking for a minimum length
    ...

Division mauvaise:

if ((j - i) / 2 >= min_length)  // bad: confusing!! what is the intention of this code?
    ...

Multiplication bonne:

if (new_length >= old_length * 1.5)  // good: is the new size at least 50% bigger?
    ...

Division mauvaise:

if (new_length / old_length >= 2)  // bad: BUGGY!! will fail if old_length = 0!
    ...
Mehrdad
la source
2
Je conviens que cela dépend du contexte, mais vos deux premières paires d'exemples sont extrêmement médiocres. Je ne préférerais pas l'un sur l'autre dans les deux cas.
Michael
6
@ Michael: Uhm ... vous trouvez (ptr2 - ptr1) * 3 >= naussi facile à comprendre que l'expression ptr2 - ptr1 >= n / 3? Cela ne fait pas trébucher votre cerveau et vous relever en essayant de déchiffrer le sens de tripler la différence entre deux pointeurs? Si c'est vraiment évident pour vous et votre équipe, alors plus de pouvoir pour vous, je suppose; Je dois juste être dans la minorité lente.
Mehrdad
2
Une variable appelée net un nombre arbitraire 3 sont déroutants dans les deux cas, mais remplacés par des noms raisonnables, non, je ne trouve pas que l'un soit plus déroutant que l'autre.
Michael
1
Ces exemples ne sont pas vraiment médiocres… certainement pas «extrêmement pauvres» - même si vous inscrivez des «noms raisonnables», ils ont encore moins de sens lorsque vous les échangez pour les cas graves. Si j'étais nouveau dans un projet, je préférerais de loin voir les «bons» cas énumérés dans cette réponse lorsque je suis allé corriger un code de production.
John-M
3

Faire quelque chose «autant que possible» est très rarement une bonne idée.

Votre priorité numéro un devrait être l'exactitude, suivie de la lisibilité et de la maintenabilité. Remplacer aveuglément une division par une multiplication lorsque cela est possible échouera souvent dans le service de la correction, parfois seulement dans des cas rares et donc difficiles à trouver.

Faites ce qui est correct et le plus lisible. Si vous avez des preuves solides que l'écriture de code de la manière la plus lisible pose un problème de performances, vous pouvez alors le modifier. Les commentaires sur les soins, les maths et le code sont vos amis.

gnasher729
la source
1

En ce qui concerne la lisibilité du code, je pense que la multiplication est en réalité plus lisible dans certains cas. Par exemple, s'il y a quelque chose que vous devez vérifier si newValuea augmenté de 5% ou plus oldValue, alors il 1.05 * oldValuey a un seuil à tester newValue, et il est naturel d'écrire

    if (newValue >= 1.05 * oldValue)

Mais méfiez-vous des nombres négatifs lorsque vous refactorisez les choses de cette façon (en remplaçant la division par la multiplication ou en remplaçant la multiplication par la division). Les deux conditions que vous avez considérées sont équivalentes si la oldValuegarantie n'est pas négative; mais suppose newValueest en réalité -13,5 et oldValueest -10,1. ensuite

newValue/oldValue >= 1.05

évalue à vrai , mais

newValue >= 1.05 * oldValue

évalue à faux .

David K
la source
1

Notez le fameux papier Division par Invariant Integers en utilisant la multiplication .

Le compilateur est en train de multiplier, si l'entier est invariant! Pas une division. Cela se produit même pour les valeurs non puissantes de 2. La puissance de 2 divisions utilise évidemment des bits de décalage et est donc encore plus rapide.

Cependant, pour les entiers non invariants, il vous incombe d'optimiser le code. Avant d’optimiser, assurez-vous d’optimiser réellement un véritable goulet d’étranglement et de ne pas sacrifier la correction. Attention au débordement d'entier.

La micro-optimisation me tient à cœur, donc je jetterais probablement un coup d'œil aux possibilités d'optimisation.

Pensez également aux architectures sur lesquelles votre code est exécuté. Surtout ARM a une division extrêmement lente; vous devez appeler une fonction pour diviser, il n’ya pas d’instruction de division dans ARM.

De plus, sur les architectures 32 bits, la division 64 bits n'est pas optimisée, comme je l'ai découvert .

juhist
la source
1

En reprenant votre point 2, cela empêchera effectivement le débordement pour un très petit oldValue. Toutefois, siSOME_CONSTANT est également très petite, votre méthode alternative se retrouvera avec un dépassement inférieur, où la valeur ne peut pas être représentée avec précision.

Et inversement, que se passe-t-il si oldValue est très grand? Vous avez les mêmes problèmes, à l’inverse.

Si vous souhaitez éviter (ou minimiser) le risque de débordement / dépassement, le meilleur moyen consiste à vérifier si l' newValueampleur est la plus proche de oldValueou la plus proche SOME_CONSTANT. Vous pouvez ensuite choisir l’opération de division appropriée, soit

    if(newValue / oldValue >= SOME_CONSTANT)

ou

    if(newValue / SOME_CONSTANT >= oldValue)

et le résultat sera le plus précis.

Pour ce qui est de la division par zéro, selon mon expérience, il n’est presque jamais approprié d’être "résolu" en maths. Si vos contrôles continus se divisent par zéro, vous avez certainement une situation qui nécessite une analyse et tout calcul fondé sur ces données n'a pas de sens. Une vérification explicite de la division par zéro est presque toujours le mouvement approprié. (Notez que je dis «presque» ici, parce que je ne prétends pas être infaillible. Je noterai simplement que je ne me souviens pas avoir vu une bonne raison à cela en 20 ans d'écriture de logiciels embarqués, et je passe à autre chose. .)

Toutefois, si votre application présente un risque réel de débordement / de débordement, ce n'est probablement pas la bonne solution. Plus probablement, vous devriez généralement vérifier la stabilité numérique de votre algorithme, ou peut-être simplement passer à une représentation plus précise.

Et si vous ne possédez pas de risque avéré de débordement / de sous-remplissage, vous ne craignez plus rien. Cela signifie que vous devez littéralement prouver que vous en avez besoin, avec des chiffres, des commentaires à côté du code qui expliquent à un responsable pourquoi c'est nécessaire. En tant qu'ingénieur principal en train de réviser le code d'autres personnes, si je rencontrais quelqu'un qui prenait des efforts supplémentaires, je n'accepterais personnellement rien de moins. C’est un peu l’opposé de l’optimisation prématurée, mais elle aurait généralement la même cause fondamentale: l’obsession des détails qui ne fait aucune différence fonctionnelle.

Graham
la source
0

Encapsulez l'arithmétique conditionnelle dans des méthodes et des propriétés significatives. Non seulement une bonne dénomination vous dira ce que "A / B" signifie , la vérification des paramètres et la gestion des erreurs peuvent également s'y cacher.

Il est important de noter que ces méthodes étant composées d'une logique plus complexe, la complexité extrinsèque reste très gérable.

Je dirais que la substitution par multiplication semble une solution raisonnable car le problème est mal défini.

radarbob
la source
0

Je pense que ce ne serait pas une bonne idée de remplacer les multiplications par des divisions, car l’ALU (unité arithmétique-logique) du processeur exécute des algorithmes, même s’ils sont implémentés dans le matériel. Des techniques plus sophistiquées sont disponibles dans les nouveaux processeurs. Généralement, les processeurs s'efforcent de paralléliser les opérations de paires de bits afin de minimiser les cycles d'horloge requis. Les algorithmes de multiplication peuvent être parallélisés assez efficacement (bien que davantage de transistors soient nécessaires). Les algorithmes de division ne peuvent pas être parallélisés aussi efficacement. Les algorithmes de division les plus efficaces sont assez complexes. Généralement, ils nécessitent plus de cycles d'horloge par bit.

Ishan Shah
la source