Ist es eine gute Praxis, wenn möglich die Division durch Multiplikation zu ersetzen?

73

Wenn ich eine Division benötige, zum Beispiel eine Bedingungsprüfung, möchte ich den Ausdruck der Division in Multiplikation umgestalten, zum Beispiel:

Originalfassung:

if(newValue / oldValue >= SOME_CONSTANT)

Neue Version:

if(newValue >= oldValue * SOME_CONSTANT)

Weil ich denke, es kann vermeiden:

  1. Durch Null teilen

  2. Überlauf, wenn oldValuesehr klein ist

Ist das richtig? Gibt es ein Problem für diese Angewohnheit?

ocomfd
quelle
41
Achten Sie darauf, dass die beiden Versionen bei negativen Zahlen völlig unterschiedliche Dinge überprüfen. Bist du dir da sicher oldValue >= 0?
user2313067
37
Abhängig von der Sprache (vor allem aber mit C) hat der Compiler bei allen Optimierungen, die Sie sich vorstellen können, normalerweise genügend Sinn, dies überhaupt nicht zu tun.
Mark Benningfield
63
Es ist nie „eine gute Praxis“ , um immer Code X durch Y - Code zu ersetzen , wenn X und Y nicht semantisch äquivalent. Aber es ist immer eine gute Idee, X und Y zu betrachten, das Gehirn einzuschalten, über die Anforderungen nachzudenken und dann zu entscheiden, welche der beiden Alternativen korrekter ist. Danach sollten Sie sich auch überlegen, welche Tests erforderlich sind, um zu überprüfen, ob Sie die semantischen Unterschiede richtig erkannt haben.
Doc Brown
12
@MarkBenningfield: Der Compiler kann die Division durch Null nicht optimieren. Die "Optimierung", an die Sie denken, ist "Geschwindigkeitsoptimierung". Das OP denkt über eine andere Art der Optimierung nach - die Vermeidung von Fehlern.
Slebetman
25
Punkt 2 ist falsch. Die ursprüngliche Version kann für kleine Werte überlaufen, die neue Version kann jedoch für große Werte überlaufen, sodass im Allgemeinen keine der beiden Versionen sicherer ist.
JacquesB

Antworten:

74

Zwei häufig zu berücksichtigende Fälle:

Ganzzahlige Arithmetik

Wenn Sie eine Ganzzahl-Arithmetik verwenden (die abschneidet), erhalten Sie offensichtlich ein anderes Ergebnis. Hier ist ein kleines Beispiel in 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.");
    }
}

Ausgabe:

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

Gleitkomma-Arithmetik

Abgesehen von der Tatsache, dass eine Division ein anderes Ergebnis liefern kann, wenn sie durch Null dividiert (sie erzeugt eine Ausnahme, während eine Multiplikation dies nicht tut), kann sie auch zu leicht unterschiedlichen Rundungsfehlern und einem anderen Ergebnis führen. Einfaches Beispiel in 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.");
    }
}

Ausgabe:

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

Falls du mir nicht glaubst, hier ist eine Geige, die du ausführen und selbst sehen kannst.

Andere Sprachen können abweichen. Bedenken Sie jedoch, dass C # wie viele andere Sprachen eine Gleitkommabibliothek nach IEEE-Standard (IEEE 754) implementiert , sodass Sie bei anderen standardisierten Laufzeiten dieselben Ergebnisse erzielen sollten.

Fazit

Wenn Sie auf der grünen Wiese arbeiten , sind Sie wahrscheinlich in Ordnung.

Wenn Sie an altem Code arbeiten und es sich bei der Anwendung um eine finanzielle oder andere vertrauliche Anwendung handelt, die arithmetisch arbeitet und konsistente Ergebnisse liefern muss, gehen Sie beim Ändern von Vorgängen sehr vorsichtig vor. Wenn Sie müssen, stellen Sie sicher, dass Sie Komponententests haben, die subtile Änderungen in der Arithmetik erkennen.

Wenn Sie nur Dinge wie das Zählen von Elementen in einem Array oder andere allgemeine Berechnungsfunktionen ausführen, sind Sie wahrscheinlich in Ordnung. Ich bin nicht sicher, ob die Multiplikationsmethode Ihren Code klarer macht.

Wenn Sie einen Algorithmus für eine Spezifikation implementieren, würde ich nichts ändern, nicht nur wegen des Problems der Rundungsfehler, sondern damit Entwickler den Code überprüfen und jeden Ausdruck der Spezifikation zuordnen können, um sicherzustellen, dass keine Implementierung vorliegt Mängel.

John Wu
quelle
41
Zweitens das finanzielle Bit. Diese Art von Schalter verlangt, dass Buchhalter Sie mit Mistgabeln verfolgen. Ich erinnere mich an 5.000 Zeilen, in denen ich mehr Mühe hatte, die Heugabeln in Schach zu halten, als die "richtige" Antwort zu finden - was im Allgemeinen leicht falsch war. Eine Abweichung von 0,01% spielte keine Rolle, absolut einheitliche Antworten waren obligatorisch. Daher musste ich die Berechnung so durchführen, dass ein systematischer Rundungsfehler auftrat.
Loren Pechtel
8
Denken Sie daran, 5-Cent-Bonbons zu kaufen (das gibt es nicht mehr). Kaufen Sie 20 Stück. Die "richtige" Antwort war keine Steuer, da auf 20 Einkäufe von einem Stück keine Steuer erhoben wurde.
Loren Pechtel
24
@LorenPechtel, das liegt daran, dass in den meisten Steuersystemen (aus offensichtlichen Gründen) die Steuer pro Transaktion erhoben wird und die Steuer in Schritten fällig wird, die nicht kleiner als die kleinste Münze des Reiches sind, und dass Spitzenbeträge zugunsten des Steuerzahlers abgerundet werden. Diese Regeln sind "korrekt", weil sie rechtmäßig und konsequent sind. Die Buchhalter mit Heugabeln wissen wahrscheinlich, wie die Regeln tatsächlich sind, was Computerprogrammierer nicht tun (es sei denn, sie sind auch erfahrene Buchhalter). Ein Fehler von 0,01% verursacht wahrscheinlich einen Auswuchtfehler, und es ist unzulässig, einen Auswuchtfehler zu haben.
Steve
9
Da ich den Begriff " grüne Wiese" noch nie gehört habe , habe ich ihn nachgeschlagen. Wikipedia sagt, es sei "ein Projekt, bei dem keine Einschränkungen aufgrund vorheriger Arbeiten bestehen".
Henrik Ripa
9
@Steve: Mein Chef hat kürzlich "Greenfield" und "Brownfield" gegenübergestellt. Ich bemerkte, dass bestimmte Projekte eher wie "Blackfield" sind ... :-D
DevSolar
25

Ich mag Ihre Frage, da sie möglicherweise viele Ideen abdeckt. Insgesamt denke ich, dass die Antwort davon abhängt , wahrscheinlich von den beteiligten Typen und dem möglichen Wertebereich in Ihrem speziellen Fall.

Mein anfänglicher Instinkt ist es, über den Stil nachzudenken , d. H. Ihre neue Version ist für den Leser Ihres Codes weniger klar. Ich stelle mir vor, ich müsste ein oder zwei Sekunden (oder länger) nachdenken, um die Absicht Ihrer neuen Version zu bestimmen, während Ihre alte Version sofort klar ist. Die Lesbarkeit ist ein wichtiges Attribut des Codes, sodass Ihre neue Version Kosten verursacht.

Sie haben Recht, dass die neue Version eine Division durch Null vermeidet. Sicherlich müssen Sie keine Schutzvorrichtung hinzufügen (in Anlehnung an if (oldValue != 0)). Aber macht das Sinn? Ihre alte Version spiegelt ein Verhältnis zwischen zwei Zahlen wider. Wenn der Divisor Null ist, ist Ihr Verhältnis undefiniert. Dies kann in Ihrer Situation sinnvoller sein, z. In diesem Fall sollten Sie kein Ergebnis erzielen.

Überlaufschutz ist umstritten. Wenn Sie wissen, dass newValuedas immer größer ist als oldValue, dann könnten Sie vielleicht dieses Argument vorbringen. Es kann jedoch Fälle geben, in denen (oldValue * SOME_CONSTANT)auch ein Überlauf auftritt. Daher sehe ich hier nicht viel Gewinn.

Möglicherweise gibt es ein Argument dafür, dass Sie eine bessere Leistung erzielen, da die Multiplikation schneller als die Division sein kann (auf einigen Prozessoren). Es müssten jedoch viele Berechnungen wie diese durchgeführt werden, um einen signifikanten Gewinn zu erzielen, d. H. Vorsicht vor vorzeitiger Optimierung.

Nach alledem denke ich, dass mit Ihrer neuen Version im Vergleich zur alten Version im Allgemeinen nicht viel gewonnen werden kann, insbesondere angesichts der geringeren Klarheit. In bestimmten Fällen kann es jedoch Vorteile geben.

Dave
quelle
16
Ähm, die willkürliche Multiplikation ist effizienter als die willkürliche Division und für reale Maschinen nicht wirklich prozessorabhängig.
Deduplikator
1
Es gibt auch das Problem der Ganzzahl-Gleitkomma-Arithmetik. Wenn das Verhältnis ein Bruchteil ist, muss die Division im Gleitkomma durchgeführt werden, was eine Umwandlung erfordert. Das Fehlen der Besetzung führt zu unbeabsichtigten Fehlern. Wenn es sich bei dem Bruch um ein Verhältnis zwischen zwei kleinen ganzen Zahlen handelt, können Sie den Vergleich in Ganzzahlarithmetik durchführen, indem Sie sie neu anordnen. (Zu welchem ​​Zeitpunkt werden Ihre Argumente zutreffen.)
rwong
@rwong Nicht immer. Mehrere Sprachen führen eine Ganzzahldivision durch, indem sie den Dezimalteil löschen, sodass keine Umwandlung erforderlich ist.
T. Sar - Reinstate Monica
@ T.Sar Die von Ihnen beschriebene Technik und die in der Antwort beschriebene Semantik sind unterschiedlich. Semantik ist, ob der Programmierer beabsichtigt, dass die Antwort ein Gleitkomma- oder ein Bruchwert ist; Die von Ihnen beschriebene Technik ist die Division durch reziproke Multiplikation, die manchmal eine perfekte Annäherung (Substitution) für eine ganzzahlige Division darstellt. Die letztere Technik wird typischerweise angewendet, wenn der Divisor im Voraus bekannt ist, da die Herleitung des ganzzahligen Reziprokwerts (um 2 ** 32 verschoben) zur Kompilierungszeit erfolgen kann. Dies zur Laufzeit zu tun, wäre nicht vorteilhaft, da es CPU-teurer ist.
Rwong
22

Nein.

Ich würde diese vorzeitige Optimierung wahrscheinlich im weiteren Sinne als " vorzeitige Optimierung" bezeichnen , unabhängig davon, ob Sie für die Leistung optimieren , wie der Ausdruck allgemein sagt, oder für alles andere, was optimiert werden kann, wie z. B. die Kantenanzahl , Codezeilen oder Noch allgemeiner: Dinge wie "Design".

Die Implementierung dieser Art von Optimierung als Standardbetriebsverfahren gefährdet die Semantik Ihres Codes und verbirgt möglicherweise die Ränder. Die Randfälle, die Sie für unbemerkt beseitigen können, müssen möglicherweise ohnehin explizit behandelt werden . Und es ist unendlich einfacher, Probleme an verrauschten Rändern (die Ausnahmen auslösen) gegenüber solchen zu beheben, die stillschweigend fehlschlagen.

In einigen Fällen ist es sogar vorteilhaft, die Optimierung zu deaktivieren, um die Lesbarkeit, Klarheit oder Aussagekraft zu verbessern. In den meisten Fällen werden Ihre Benutzer nicht bemerken, dass Sie einige Codezeilen oder CPU-Zyklen gespeichert haben, um die Behandlung von Edge-Cases oder Ausnahmen zu vermeiden. Peinlich oder Code leise versagt, auf der anderen Seite, werden Auswirkungen auf Menschen - Ihre Mitarbeiter am allerwenigsten. (Und daher auch die Kosten für die Erstellung und Wartung der Software.)

Die Standardeinstellung ist "natürlich" und in Bezug auf die Domäne der Anwendung und das spezifische Problem lesbar. Halten Sie es einfach, explizit und idiomatisch. Optimieren Sie nach Bedarf, um signifikante Gewinne zu erzielen oder eine legitime Usability-Schwelle zu erreichen.

Beachten Sie auch: Compiler optimieren die Aufteilung oft ohnehin für Sie - wenn es sicher ist .

Svidgen
quelle
11
-1 Diese Antwort passt nicht wirklich zu der Frage, die sich mit den potenziellen Fallstricken der Teilung befasst - nichts mit Optimierung zu tun
Ben Cottrell
13
@BenCottrell Es passt perfekt. Die Falle besteht darin, Wert auf sinnlose Leistungsoptimierungen zu Lasten der Wartbarkeit zu legen. Aus der Frage "Gibt es ein Problem für diese Gewohnheit?" - Ja. Es wird schnell zu absolutem Kauderwelsch führen.
Michael
9
@Michael, bei der Frage geht es auch nicht um eines dieser Dinge - es geht speziell um die Richtigkeit zweier verschiedener Ausdrücke, die jeweils unterschiedliche Semantiken und Verhaltensweisen haben, aber beide für die gleiche Anforderung geeignet sind.
Ben Cottrell
5
@BenCottrell Vielleicht könntest du mich darauf hinweisen, wo in der Frage überhaupt etwas über die Richtigkeit steht?
Michael
5
@BenCottrell Sie sollten gerade gesagt haben "Ich kann nicht" :)
Michael
13

Verwenden Sie das, was weniger fehlerhaft und logischer ist.

Normalerweise ist die Division durch eine Variable ohnehin eine schlechte Idee, da der Divisor normalerweise Null sein kann.
Die Division durch eine Konstante hängt normalerweise nur von der logischen Bedeutung ab.

Hier einige Beispiele, um zu zeigen, dass dies von der Situation abhängt:

Abteilung gut:

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

Multiplikation schlecht:

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

Multiplikation gut:

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

Division schlecht:

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

Multiplikation gut:

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

Division schlecht:

if (new_length / old_length >= 2)  // bad: BUGGY!! will fail if old_length = 0!
    ...
Mehrdad
quelle
2
Ich stimme zu, dass es vom Kontext abhängt, aber Ihre ersten beiden Beispiele sind extrem schlecht. Ich würde es in beiden Fällen nicht vorziehen, eins dem anderen vorzuziehen.
Michael
6
@Michael: Ähm ... findest du (ptr2 - ptr1) * 3 >= ndas genauso einfach zu verstehen wie den Ausdruck ptr2 - ptr1 >= n / 3? Es bringt Ihr Gehirn nicht dazu, wieder aufzustehen und zu versuchen, die Bedeutung der Verdreifachung des Unterschieds zwischen zwei Zeigern zu entschlüsseln? Wenn es für Sie und Ihr Team wirklich offensichtlich ist, dann schätze ich, dass Sie mehr Macht haben. Ich muss nur in der langsamen Minderheit sein.
Mehrdad
2
Eine Variable namens nund eine willkürliche Zahl 3 sind in beiden Fällen verwirrend, aber, ersetzt durch sinnvolle Namen, nein, ich finde keinen verwirrender als den anderen.
Michael
1
Diese Beispiele sind nicht wirklich arm ... definitiv nicht "extrem arm" - selbst wenn Sie "vernünftige Namen" eingeben, sind sie weniger sinnvoll, wenn Sie sie gegen die schlechten Fälle tauschen. Wenn ich ein Neuling in einem Projekt wäre, würde ich die "guten" Fälle, die in dieser Antwort aufgelistet sind, viel lieber sehen, wenn ich einen Produktionscode reparieren würde.
John-M
3

Es ist sehr selten eine gute Idee , „wann immer möglich“ irgendetwas zu tun .

Ihre oberste Priorität sollte die Korrektheit sein, gefolgt von Lesbarkeit und Wartbarkeit. Das blinde Ersetzen der Division durch Multiplikation, wann immer dies möglich ist, schlägt in der Korrektheitsabteilung häufig fehl, manchmal nur in seltenen und daher schwer auffindbaren Fällen.

Tun Sie, was richtig und am besten lesbar ist. Wenn Sie solide Beweise dafür haben, dass das Schreiben von Code auf die am besten lesbare Weise ein Leistungsproblem verursacht, können Sie eine Änderung in Betracht ziehen. Pflege, Mathematik und Code-Reviews sind deine Freunde.

gnasher729
quelle
1

In Bezug auf die Lesbarkeit des Codes denke ich, dass die Multiplikation in einigen Fällen tatsächlich besser lesbar ist. Wenn Sie beispielsweise überprüfen müssen, ob newValueein Wert von 5 Prozent oder mehr überschritten wurde oldValue, 1.05 * oldValueist dies ein Schwellenwert, an dem getestet werden muss newValue, und das Schreiben ist natürlich

    if (newValue >= 1.05 * oldValue)

Aber hüten Sie sich vor negativen Zahlen, wenn Sie die Dinge auf diese Weise umgestalten (entweder die Division durch Multiplikation ersetzen oder die Multiplikation durch Division ersetzen). Die beiden Bedingungen, die Sie in Betracht gezogen haben, sind gleichwertig, wenn oldValuegarantiert nicht negativ ist. Nehmen wir aber an, newValuetatsächlich ist -13,5 und -10,1 oldValue. Dann

newValue/oldValue >= 1.05

ergibt true , aber

newValue >= 1.05 * oldValue

wird zu false ausgewertet .

David K
quelle
1

Beachten Sie das berühmte Paper Division by Invariant Integers using Multiplication .

Der Compiler multipliziert tatsächlich, wenn die Ganzzahl unveränderlich ist! Keine Division. Dies geschieht auch bei Nicht-Potenz von 2 Werten. Potenz von 2 Divisionen verwenden offensichtlich Bitverschiebungen und sind daher noch schneller.

Für nichtinvariante Ganzzahlen liegt es jedoch in Ihrer Verantwortung, den Code zu optimieren. Stellen Sie vor dem Optimieren sicher, dass Sie wirklich einen echten Engpass optimieren und dass die Richtigkeit nicht beeinträchtigt wird. Vorsicht vor Überlauf von ganzen Zahlen.

Da mir die Mikrooptimierung am Herzen liegt, würde ich mir wahrscheinlich die Optimierungsmöglichkeiten ansehen.

Denken Sie auch an die Architekturen, auf denen Ihr Code ausgeführt wird. Insbesondere ARM hat eine extrem langsame Teilung; Sie müssen eine Funktion aufrufen, um zu teilen. In ARM gibt es keine Divisionsanweisung.

Auf 32-Bit-Architekturen ist die 64-Bit-Aufteilung nicht optimiert, wie ich herausgefunden habe .

juhist
quelle
1

Wenn Sie Ihren Punkt 2 aufgreifen, wird ein Überlauf für einen sehr kleinen Teil tatsächlich verhindert oldValue. Wenn SOME_CONSTANTes sich jedoch auch um eine sehr kleine Methode handelt, kommt es zu einem Unterlauf, bei dem der Wert nicht genau dargestellt werden kann.

Und umgekehrt, was passiert, wenn oldValuees sehr groß ist? Sie haben die gleichen Probleme, genau umgekehrt.

Wenn Sie vermeiden möchten (oder zu minimieren) , um das Risiko von Über- / Unterlauf ist der beste Weg , um zu überprüfen , ob newValuein der Größe am nächsten ist , oldValueoder SOME_CONSTANT. Sie können dann entweder die entsprechende Divisionsoperation auswählen

    if(newValue / oldValue >= SOME_CONSTANT)

oder

    if(newValue / SOME_CONSTANT >= oldValue)

und das Ergebnis wird am genauesten sein.

Nach meiner Erfahrung ist es für die Division durch Null so gut wie nie angebracht, in der Mathematik "gelöst" zu werden. Wenn Sie bei Ihren kontinuierlichen Überprüfungen eine Division durch Null haben, dann haben Sie mit ziemlicher Sicherheit eine Situation, die eine Analyse erfordert, und Berechnungen, die auf diesen Daten basieren, sind bedeutungslos. Eine explizite Prüfung durch das Teilen durch Null ist fast immer der richtige Schritt. (Beachten Sie, dass ich hier "fast" sage, weil ich nicht behaupte, unfehlbar zu sein. Ich werde nur bemerken, dass ich mich nicht daran erinnere, dass ich in 20 Jahren des Schreibens eingebetteter Software einen guten Grund dafür gesehen habe und gehe weiter .)

Wenn Sie jedoch ein echtes Überlauf- / Unterlaufrisiko in Ihrer Anwendung haben, ist dies wahrscheinlich nicht die richtige Lösung. Wahrscheinlicher ist, dass Sie im Allgemeinen die numerische Stabilität Ihres Algorithmus überprüfen oder einfach zu einer präziseren Darstellung wechseln sollten.

Und wenn Sie kein nachgewiesenes Risiko für Über- oder Unterlauf haben, machen Sie sich um nichts Sorgen. Das bedeutet, dass Sie buchstäblich beweisen müssen, dass Sie es brauchen, mit Zahlen in Kommentaren neben dem Code, die einem Betreuer erklären, warum es notwendig ist. Als leitender Ingenieur, der den Code anderer überprüft, würde ich persönlich nichts weniger akzeptieren, wenn ich jemandem begegnen würde, der diesbezüglich zusätzliche Anstrengungen unternimmt. Dies ist das Gegenteil von vorzeitiger Optimierung, hat jedoch im Allgemeinen die gleiche Ursache: Besessenheit mit Details, die keinen funktionalen Unterschied macht.

Graham
quelle
0

Verkapseln Sie die bedingte Arithmetik in sinnvolle Methoden und Eigenschaften. Gute Benennung sagt nicht nur, was "A / B" bedeutet , sondern auch Parameterprüfung und Fehlerbehandlung.

Da diese Methoden zu einer komplexeren Logik zusammengesetzt sind, bleibt die extrinsische Komplexität sehr überschaubar.

Ich würde sagen, Multiplikationssubstitution scheint eine vernünftige Lösung zu sein, da das Problem schlecht definiert ist.

Radarbob
quelle
0

Ich denke, es könnte keine gute Idee sein, Multiplikationen durch Divisionen zu ersetzen, da die ALU (Arithmetic-Logic Unit) der CPU Algorithmen ausführt, obwohl sie in Hardware implementiert sind. In neueren Prozessoren sind komplexere Techniken verfügbar. Im Allgemeinen bemühen sich Prozessoren, Bitpaaroperationen zu parallelisieren, um die erforderlichen Taktzyklen zu minimieren. Multiplikationsalgorithmen können sehr effektiv parallelisiert werden (obwohl mehr Transistoren erforderlich sind). Divisionsalgorithmen können nicht so effizient parallelisiert werden. Die effizientesten Divisionsalgorithmen sind ziemlich komplex. Im Allgemeinen erfordern sie mehr Taktzyklen pro Bit.

Ishan Shah
quelle