Czy dobrą praktyką jest zastępowanie dzielenia mnożeniem, jeśli to możliwe?

73

Ilekroć potrzebuję podziału, na przykład sprawdzania warunku, chciałbym zmienić wyrażenie dzielenia na mnożenie, na przykład:

Orginalna wersja:

if(newValue / oldValue >= SOME_CONSTANT)

Nowa wersja:

if(newValue >= oldValue * SOME_CONSTANT)

Ponieważ myślę, że można tego uniknąć:

  1. Dzielenie przez zero

  2. Przepełnienie, gdy oldValuejest bardzo małe

Czy to prawda? Czy istnieje problem z tym nawykiem?

ocomfd
źródło
41
Uważaj, aby przy liczbach ujemnych dwie wersje sprawdzały zupełnie różne rzeczy. Jesteś tego pewien oldValue >= 0?
user2313067
37
W zależności od języka (ale przede wszystkim z C), bez względu na to, jaką optymalizację można wymyślić, kompilator zwykle może to zrobić lepiej, -LUB- , ma wystarczający sens, aby w ogóle tego nie robić.
Mark Benningfield
63
Nigdy nie jest „dobrą praktyką” zawsze zastępować kod X kodem Y, gdy X i Y nie są semantycznie równoważne. Ale zawsze dobrze jest spojrzeć na X i Y, włączyć mózg, przemyśleć jakie są wymagania , a następnie podjąć decyzję, która z dwóch alternatyw jest bardziej poprawna. Następnie powinieneś również zastanowić się, które testy są wymagane, aby zweryfikować, czy poprawnie dostałeś różnice semantyczne.
Doc Brown
12
@MarkBenningfield: Nieważne, kompilator nie może zoptymalizować dzielenia przez zero. „Optymalizacja”, o której myślisz, to „optymalizacja prędkości”. OP myśli o innym rodzaju optymalizacji - unikaniu błędów.
slebetman
25
Punkt 2 jest fałszywy. Oryginalna wersja może przepełniać małe wartości, ale nowa wersja może przepełniać duże wartości, więc żadne z nich nie jest bezpieczniejsze w ogólnym przypadku.
JacquesB

Odpowiedzi:

74

Dwa typowe przypadki do rozważenia:

Arytmetyka liczb całkowitych

Oczywiście, jeśli używasz arytmetyki liczb całkowitych (która obcina), otrzymasz inny wynik. Oto mały przykład w języku 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.");
    }
}

Wynik:

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

Arytmetyka zmiennoprzecinkowa

Oprócz faktu, że dzielenie może dawać inny wynik, gdy dzieli się przez zero (generuje wyjątek, podczas gdy mnożenie nie), może również powodować nieco inne błędy zaokrąglania i inny wynik. Prosty przykład w języku 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.");
    }
}

Wynik:

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

Jeśli mi nie wierzysz, oto skrzypce, które możesz wykonać i przekonać się sam.

Inne języki mogą być inne; pamiętaj jednak, że C #, podobnie jak wiele języków, implementuje bibliotekę zmiennoprzecinkową standardu IEEE (IEEE 754) , więc powinieneś uzyskać te same wyniki w innych znormalizowanych czasach wykonywania.

Wniosek

Jeśli pracujesz na zielonym polu , prawdopodobnie nic ci nie jest.

Jeśli pracujesz nad starszym kodem, a aplikacja jest aplikacją finansową lub inną wrażliwą, która wykonuje arytmetykę i jest wymagana do zapewnienia spójnych wyników, zachowaj ostrożność podczas zmiany operacji. Jeśli musisz, upewnij się, że masz testy jednostkowe, które wykryją wszelkie subtelne zmiany arytmetyki.

Jeśli po prostu robisz takie rzeczy, jak zliczanie elementów w tablicy lub inne ogólne funkcje obliczeniowe, prawdopodobnie będziesz w porządku. Nie jestem jednak pewien, czy metoda mnożenia sprawia, że ​​kod jest bardziej przejrzysty.

Jeśli implementujesz algorytm do specyfikacji, nie zmieniłbym niczego, nie tylko z powodu problemu z zaokrąglaniem błędów, ale także, aby programiści mogli przejrzeć kod i odwzorować każde wyrażenie z powrotem do specyfikacji, aby upewnić się, że nie ma implementacji wady.

John Wu
źródło
41
Po drugie bit finansowy. Tego rodzaju zmiana wymaga od księgowych ścigania cię widłami. Pamiętam 5000 wierszy, w których musiałem włożyć więcej wysiłku, aby trzymać widły na dystans, niż w znalezieniu „właściwej” odpowiedzi - co w zasadzie było nieco błędne. Wyłączenie o 0,01% nie miało znaczenia, absolutnie spójne odpowiedzi były obowiązkowe. W związku z tym byłem zmuszony wykonać obliczenia w sposób powodujący systematyczny błąd zaokrągleń.
Loren Pechtel
8
Pomyśl o zakupie 5 centów cukierków (już nie istnieje). Kup 20 sztuk, „poprawną” odpowiedzią był brak podatku, ponieważ nie było podatku od 20 zakupów jednej sztuki.
Loren Pechtel
24
@LorenPechtel, ponieważ większość systemów podatkowych zawiera (z oczywistych powodów) zasadę, że podatek jest nakładany na transakcję, a podatek jest naliczany w przyrostach nie mniejszych niż najmniejsza moneta danego obszaru, a kwoty ułamkowe są zaokrąglane w dół na korzyść podatnika. Zasady te są „prawidłowe”, ponieważ są zgodne z prawem i spójne. Księgowi z widłami prawdopodobnie wiedzą, jakie są reguły w sposób, którego nie zrobią programiści komputerowi (chyba że są również doświadczonymi księgowymi). Błąd 0,01% najprawdopodobniej spowoduje błąd bilansowania, a błąd bilansowania jest niezgodny z prawem.
Steve
9
Ponieważ nigdy wcześniej nie słyszałem pojęcia greenfield , sprawdziłem go. Wikipedia twierdzi, że jest to „projekt, który nie ma żadnych ograniczeń narzuconych przez wcześniejsze prace”.
Henrik Ripa
9
@ Steve: Mój szef ostatnio porównał „greenfield” do „brownfield”. Zauważyłem, że niektóre projekty bardziej przypominają „blackfield” ... :-D
DevSolar
25

Podoba mi się twoje pytanie, ponieważ potencjalnie obejmuje wiele pomysłów. Ogólnie rzecz biorąc, podejrzewam, że odpowiedź jest taka , prawdopodobnie zależy to od typów i możliwego zakresu wartości w konkretnym przypadku.

Moim początkowym instynktem jest refleksja nad stylem , tj. twoja nowa wersja jest mniej czytelna dla czytelnika twojego kodu. Wyobrażam sobie, że musiałbym zastanowić się przez sekundę lub dwie (a może dłużej), aby ustalić intencję nowej wersji, podczas gdy stara wersja jest natychmiast jasna. Czytelność to ważny atrybut kodu, więc nowa wersja wiąże się z pewnymi kosztami.

Masz rację, że nowa wersja unika dzielenia przez zero. Z pewnością nie musisz dodawać osłony (zgodnie z linią if (oldValue != 0)). Ale czy to ma sens? Twoja stara wersja odzwierciedla stosunek dwóch liczb. Jeśli dzielnik wynosi zero, wówczas współczynnik jest niezdefiniowany. Może to mieć większe znaczenie w twojej sytuacji, tj. w tym przypadku nie powinieneś dawać wyniku.

Ochrona przed przepełnieniem jest dyskusyjna. Jeśli wiesz, że newValueto zawsze jest większe niż oldValue, być może mógłbyś podnieść ten argument. Mogą jednak wystąpić przypadki, w których (oldValue * SOME_CONSTANT)nastąpi również przepełnienie. Więc nie widzę tu większego zysku.

Może istnieć argument, że poprawiasz wydajność, ponieważ mnożenie może być szybsze niż dzielenie (na niektórych procesorach). Jednak musiałoby być wiele takich obliczeń, aby uzyskać znaczący zysk, tj. uważaj na przedwczesną optymalizację.

Zastanawiając się nad wszystkimi powyższymi kwestiami, generalnie nie sądzę, aby można było wiele zyskać na nowej wersji w porównaniu ze starą wersją, szczególnie biorąc pod uwagę zmniejszenie przejrzystości. Mogą jednak występować szczególne przypadki, w których występują pewne korzyści.

Dave
źródło
16
Ehm, dowolne mnożenie jest bardziej wydajne niż arbitralne dzielenie, tak naprawdę nie jest zależne od procesora, w rzeczywistych maszynach.
Deduplicator
1
Istnieje również kwestia arytmetyki liczb całkowitych i zmiennoprzecinkowych. Jeśli stosunek jest ułamkowy, podziału należy dokonać w zmiennoprzecinkowym, wymagającym rzutowania. Brak obsady spowoduje niezamierzony błąd. Jeśli ułamek okazuje się być proporcją między dwiema małymi liczbami całkowitymi, to ich przestawienie pozwala na porównanie w arytmetyce liczb całkowitych. (W tym momencie zastosują się twoje argumenty.)
rwong
@rwong Nie zawsze. Kilka języków dzieli liczbę całkowitą, usuwając część dziesiętną, więc rzutowanie nie jest konieczne.
T. Sar
@ T.Sar Technika, którą opisujesz i semantyka opisana w odpowiedzi są różne. Semantyka polega na tym, czy programista chce, aby odpowiedź była wartością zmiennoprzecinkową czy ułamkową; techniką, którą opisujesz, jest dzielenie przez wzajemne mnożenie, co jest czasem doskonałym przybliżeniem (podstawieniem) dla dzielenia liczb całkowitych. Ta ostatnia technika jest zwykle stosowana, gdy dzielnik jest znany z góry, ponieważ wyprowadzenie liczby całkowitej odwrotnej (przesuniętej o 2 ** 32) można wykonać w czasie kompilacji. Robienie tego w czasie wykonywania nie byłoby korzystne, ponieważ jest ono droższe w stosunku do procesora.
rwong
22

Nie.

Prawdopodobnie nazwałbym tę przedwczesną optymalizację w szerokim znaczeniu, niezależnie od tego, czy optymalizujesz wydajność , jak to ogólnie odnosi się do wyrażenia, czy cokolwiek innego, co można zoptymalizować, takie jak liczenie krawędzi , wiersze kodu lub jeszcze szerzej, takie jak „projektowanie”.

Wdrożenie tego rodzaju optymalizacji jako standardowej procedury operacyjnej naraża semantykę kodu i potencjalnie ukrywa krawędzie. Przypadki brzegowe widać pasuje do cichu eliminować konieczne może być wyraźnie skierowana w każdym razie . I nieskończenie łatwiej jest debugować problemy wokół hałaśliwych krawędzi (tych, które rzucają wyjątki) w stosunku do tych, które zawodzą cicho.

W niektórych przypadkach nawet „optymalizacja” jest korzystna ze względu na czytelność, jasność lub jednoznaczność. W większości przypadków użytkownicy nie zauważą, że zapisałeś kilka wierszy kodu lub cykli procesora, aby uniknąć obsługi krawędzi lub wyjątków. Niezgrabny lub cicho braku kodu, z drugiej strony, będzie wpływać na ludzi - współpracowników przynajmniej. (A zatem także koszt budowy i utrzymania oprogramowania).

Domyślnie cokolwiek jest bardziej „naturalne” i czytelne w odniesieniu do domeny aplikacji i konkretnego problemu. Niech to będzie proste, wyraźne i idiomatyczne. Zoptymalizuj w sposób niezbędny do uzyskania znacznych korzyści lub osiągnięcia uzasadnionego progu użyteczności.

Uwaga: kompilatory często i tak optymalizują podział dla Ciebie - gdy jest to bezpieczne .

svidgen
źródło
11
-1 Ta odpowiedź nie pasuje do pytania, które dotyczy potencjalnych pułapek podziału - nie ma nic wspólnego z optymalizacją
Ben Cottrell
13
@BenCottrell Idealnie pasuje. Pułapką jest umieszczanie wartości w bezcelowych optymalizacjach wydajności kosztem utrzymania. Z pytania „czy jest jakiś problem z tym nawykiem?” - tak. Szybko doprowadzi do napisania absolutnego bełkotu.
Michael
9
@Michael również nie pyta o żadną z tych rzeczy - chodzi konkretnie o poprawność dwóch różnych wyrażeń, z których każde ma inną semantykę i zachowanie, ale oba mają spełniać te same wymagania.
Ben Cottrell
5
@BenCottrell Być może mógłbyś wskazać mi, gdzie w pytaniu jest jakaś wzmianka o poprawności?
Michael
5
@BenCottrell Powinieneś powiedzieć „nie mogę” :)
Michael
13

Użyj tej, która jest mniej obciążająca i ma bardziej logiczny sens.

Zazwyczaj podział przez zmienną jest i tak złym pomysłem, ponieważ zwykle dzielnik może wynosić zero.
Dzielenie przez stałą zwykle zależy tylko od logicznego znaczenia.

Oto kilka przykładów, które pokazują, że zależy to od sytuacji:

Podział dobry:

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

Złe mnożenie:

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

Mnożenie dobre:

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

Podział zły:

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

Mnożenie dobre:

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

Podział zły:

if (new_length / old_length >= 2)  // bad: BUGGY!! will fail if old_length = 0!
    ...
Mehrdad
źródło
2
Zgadzam się, że to zależy od kontekstu, ale dwie pierwsze pary przykładów są bardzo słabe. W obu przypadkach nie wolałbym jednego od drugiego.
Michael
6
@Michael: Uhm ... jesteś (ptr2 - ptr1) * 3 >= nrównie łatwy do zrozumienia, co wyrażenie ptr2 - ptr1 >= n / 3? Nie powoduje to, że mózg się potyka i nie próbuje ponownie rozszyfrować znaczenia potrojenia różnicy między dwoma wskaźnikami? Jeśli to naprawdę oczywiste dla ciebie i twojego zespołu, to chyba więcej mocy dla ciebie; Muszę być tylko w powolnej mniejszości.
Mehrdad
2
Wywoływana zmienna ni dowolna liczba 3 są mylące w obu przypadkach, ale zastąpione rozsądnymi nazwami, nie, nie uważam, że jedna jest bardziej myląca niż druga.
Michael
1
Te przykłady nie są naprawdę kiepskie ... zdecydowanie nie „wyjątkowo słabe” - nawet jeśli podasz „rozsądne nazwy”, nadal mają mniej sensu, kiedy zamienisz je na złe przypadki. Gdybym był nowy w projekcie, wolałbym zobaczyć „dobre” przypadki wymienione w tej odpowiedzi, kiedy poszedłem naprawić jakiś kod produkcyjny.
John-M
3

Robienie czegokolwiek „w miarę możliwości” rzadko jest dobrym pomysłem.

Naszym priorytetem powinna być poprawność, a następnie czytelność i łatwość konserwacji. Ślepe zastępowanie dzielenia mnożeniem, gdy tylko jest to możliwe, często zawiedzie w dziale poprawności, czasami tylko w rzadkich, a zatem trudnych do znalezienia przypadkach.

Rób to, co poprawne i najbardziej czytelne. Jeśli masz solidne dowody na to, że pisanie kodu w najbardziej czytelny sposób powoduje problem z wydajnością, możesz rozważyć jego zmianę. Opieka, matematyka i recenzje kodu są twoimi przyjaciółmi.

gnasher729
źródło
1

Jeśli chodzi o czytelność kodu, myślę, że mnożenie jest w niektórych przypadkach bardziej czytelne. Na przykład, jeśli jest coś, co musisz sprawdzić, czy newValuewzrosło o 5 procent lub więcej powyżej oldValue, 1.05 * oldValueoznacza to próg, w stosunku do którego chcesz przetestować newValue, i naturalnie jest pisać

    if (newValue >= 1.05 * oldValue)

Ale uważaj na liczby ujemne, gdy refaktoryzujesz rzeczy w ten sposób (albo zastępując dzielenie mnożeniem, albo zastępując mnożenie dzieleniem). Dwa warunki, które wziąłeś pod uwagę, są równoważne, jeśli oldValuegwarantuje się, że nie będą ujemne; ale załóżmy, że w newValuerzeczywistości wynosi -13,5 i oldValuewynosi -10,1. Następnie

newValue/oldValue >= 1.05

ocenia na prawdę , ale

newValue >= 1.05 * oldValue

ocenia na fałsz .

David K.
źródło
1

Zwróć uwagę na słynny papierowy podział według niezmiennych liczb całkowitych za pomocą mnożenia .

Kompilator faktycznie dokonuje mnożenia, jeśli liczba całkowita jest niezmienna! Nie podział. Dzieje się tak nawet w przypadku braku mocy 2 wartości. Moc 2 dywizji używa oczywiście przesunięć bitowych i dlatego jest jeszcze szybsza.

Jednak w przypadku niezmienniczych liczb całkowitych Twoim obowiązkiem jest optymalizacja kodu. Przed optymalizacją upewnij się, że naprawdę optymalizujesz prawdziwe wąskie gardło i że poprawność nie jest poświęcona. Uważaj na przepełnienie liczb całkowitych.

Dbam o mikrooptymalizację, więc prawdopodobnie przyjrzałbym się możliwościom optymalizacji.

Pomyśl także o architekturach, na których działa Twój kod. Zwłaszcza ARM ma bardzo wolny podział; musisz wywołać funkcję dzielenia, w ARM nie ma instrukcji podziału.

Ponadto, jak się dowiedziałem , w architekturach 32-bitowych podział 64-bitowy nie jest zoptymalizowany .

juhist
źródło
1

Podniesienie punktu 2, rzeczywiście pozwoli uniknąć przepełnienia bardzo małego oldValue. Jeśli jednak SOME_CONSTANTjest również bardzo mały, wówczas alternatywna metoda zakończy się niedopełnieniem, w którym wartości nie można dokładnie przedstawić.

I odwrotnie, co się stanie, jeśli oldValuejest bardzo duży? Masz te same problemy, wręcz przeciwnie.

Jeśli chcesz uniknąć (lub zminimalizować) ryzyko przepełnienia / niedomiaru, najlepszym sposobem jest sprawdzenie, czy newValuejest najbliżej pod względem wielkości, oldValueczy do SOME_CONSTANT. Następnie możesz wybrać odpowiednią operację podziału

    if(newValue / oldValue >= SOME_CONSTANT)

lub

    if(newValue / SOME_CONSTANT >= oldValue)

a wynik będzie najdokładniejszy.

Jeśli chodzi o dzielenie przez zero, z mojego doświadczenia wynika, że ​​prawie nigdy nie należy „rozwiązywać” matematyki. Jeśli masz ciągłe sprawdzanie dzielenia przez zero, to prawie na pewno masz sytuację, która wymaga analizy i wszelkie obliczenia oparte na tych danych są bez znaczenia. Wyraźne sprawdzenie dzielenia przez zero jest prawie zawsze właściwym posunięciem. (Zauważ, że mówię tutaj „prawie”, ponieważ nie twierdzę, że jest nieomylny. Po prostu zauważę, że nie pamiętam, aby widziałem dobry powód tego przez 20 lat pisania oprogramowania wbudowanego i idę dalej .)

Jeśli jednak istnieje realne ryzyko przepełnienia / niedopełnienia aplikacji, prawdopodobnie nie jest to właściwe rozwiązanie. Bardziej prawdopodobne jest, że ogólnie powinieneś sprawdzić stabilność liczbową swojego algorytmu lub po prostu przejść do reprezentacji o wyższej precyzji.

A jeśli nie masz udowodnionego ryzyka przepełnienia / niedopełnienia, nie martwisz się niczym. Oznacza to, że dosłownie musisz udowodnić, że jest to potrzebne, za pomocą liczb, w komentarzach obok kodu, które wyjaśniają opiekunowi, dlaczego jest to konieczne. Jako główny inżynier przeglądający kod innych ludzi, gdybym natknął się na kogoś, kto podejmowałby dodatkowy wysiłek, osobiście nie zaakceptowałbym niczego mniej. Jest to swego rodzaju przeciwieństwo przedwczesnej optymalizacji, ale generalnie miałoby tę samą pierwotną przyczynę - obsesję na punkcie szczegółów, która nie ma żadnej funkcjonalnej różnicy.

Graham
źródło
0

Zawrzyj arytmetykę warunkową w znaczących metodach i właściwościach. Nie tylko dobre nazewnictwo powiedzieć, co „A / B” oznacza , parametr kontroli i obsługi błędów można zgrabnie ukryć tam też.

Co ważne, ponieważ metody te składają się na bardziej złożoną logikę, złożoność zewnętrzna pozostaje bardzo łatwa do zarządzania.

Powiedziałbym, że podstawienie mnożenia wydaje się rozsądnym rozwiązaniem, ponieważ problem jest źle zdefiniowany.

radarbob
źródło
0

Myślę, że nie byłoby dobrym pomysłem zastąpienie mnożenia podziałami, ponieważ ALU procesora (Arithmetic-Logic Unit) wykonuje algorytmy, chociaż są one zaimplementowane sprzętowo. Bardziej zaawansowane techniki są dostępne w nowszych procesorach. Zasadniczo procesory starają się zrównoważyć operacje parami bitów w celu zminimalizowania wymaganych cykli zegara. Algorytmy mnożenia można dość skutecznie zrównoleglać (choć potrzeba więcej tranzystorów). Algorytmy podziału nie mogą być zrównoleglone tak skutecznie. Najbardziej wydajne algorytmy podziału są dość złożone. Zasadniczo wymagają więcej cykli zegara na bit.

Ishan Shah
źródło