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

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?

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.

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.

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 .}

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!
    ...

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.

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 .

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 .

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.

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.

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.