Dlaczego niektóre porównania typu float <liczby całkowite są cztery razy wolniejsze niż inne?

Porównując liczby zmiennoprzecinkowe z liczbami całkowitymi, ocena niektórych par zajmuje znacznie więcej czasu niż innych wartości o podobnej wielkości.

Na przykład:

>>> import timeit
>>> timeit.timeit("562949953420000.7 < 562949953421000") # run 1 million times
0.5387085462592742

Ale jeśli liczba zmiennoprzecinkowa lub liczba całkowita zostanie zmniejszona lub powiększona o określoną wartość, porównanie przebiega znacznie szybciej:

>>> timeit.timeit("562949953420000.7 < 562949953422000") # integer increased by 1000
0.1481498428446173
>>> timeit.timeit("562949953423001.8 < 562949953421000") # float increased by 3001.1
0.1459577925548956

Zmiana operatora porównania (np. Użycie ==lub >zamiast tego) nie wpływa na czasy w zauważalny sposób.

Nie jest to związane wyłącznie z wielkością, ponieważ wybieranie większych lub mniejszych wartości może skutkować szybszymi porównaniami, więc podejrzewam, że jest to spowodowane niefortunnym układem bitów.

Oczywiście porównanie tych wartości jest wystarczająco szybkie dla większości przypadków użycia. Jestem po prostu ciekawy, dlaczego Python wydaje się walczyć bardziej z niektórymi parami wartości niż z innymi.

Komentarz w kodzie źródłowym Pythona dla obiektów pływających potwierdza, że:

Porównanie to prawie koszmar

Jest to szczególnie prawdziwe, gdy porównujemy liczbę zmiennoprzecinkową z liczbą całkowitą, ponieważ w przeciwieństwie do liczb zmiennoprzecinkowych liczby całkowite w Pythonie mogą być dowolnie duże i zawsze są dokładne. Próba wyrzucenia liczby całkowitej na liczbę zmiennoprzecinkową może stracić precyzję i sprawić, że porównanie będzie niedokładne. Próba rzutowania liczby zmiennoprzecinkowej na liczbę całkowitą również nie zadziała, ponieważ jakakolwiek część ułamkowa zostanie utracona.

Aby obejść ten problem, Python wykonuje serię kontroli, zwracając wynik, jeśli jedna z nich zakończy się powodzeniem. Porównuje znaki dwóch wartości, a następnie czy liczba całkowita jest „zbyt duża”, aby być liczbą zmiennoprzecinkową, a następnie porównuje wykładnik liczby zmiennoprzecinkowej z długością liczby całkowitej. Jeśli wszystkie te testy zakończą się niepowodzeniem, konieczne jest zbudowanie dwóch nowych obiektów Python w celu porównania w celu uzyskania wyniku.

Porównując vliczbę zmiennoprzecinkową do liczby całkowitej / długiej w, najgorszym przypadkiem jest:

• vi wmają ten sam znak (oba dodatnie lub oba ujemne),
• liczba całkowita wma wystarczającą liczbę bitów, aby można ją było zapisać w size_ttypie (zazwyczaj 32 lub 64 bity),
• liczba całkowita wma co najmniej 49 bitów,
• wykładnik pływaka vjest taki sam jak liczba bitów w w.

I właśnie to mamy dla wartości w pytaniu:

>>> import math
>>> math.frexp(562949953420000.7) # gives the float's (significand, exponent) pair
(0.9999999999976706, 49)
>>> (562949953421000).bit_length()
49

Widzimy, że 49 jest zarówno wykładnikiem liczb zmiennoprzecinkowych, jak i liczbą bitów w liczbie całkowitej. Obie liczby są dodatnie, więc cztery powyższe kryteria są spełnione.

Wybranie jednej lub większej wartości (lub mniejszej) może zmienić liczbę bitów liczby całkowitej lub wartość wykładnika, dzięki czemu Python może określić wynik porównania bez przeprowadzania kosztownej kontroli końcowej.

Jest to specyficzne dla implementacji języka CPython.

Porównanie bardziej szczegółowo

float_richcompareFunkcja obsługuje porównania pomiędzy dwoma wartościami vi w.

Poniżej znajduje się opis krok po kroku kontroli, które wykonuje funkcja. Komentarze w źródle Pythona są w rzeczywistości bardzo pomocne, gdy próbujemy zrozumieć, co robi funkcja, więc zostawiłem je tam, gdzie to stosowne. Podsumowałem również te kontrole na liście pod odpowiedzią.

Główną ideą jest mapowanie obiektów Python vi wdwóch odpowiednich podwójnych C, ii jktóre można następnie łatwo porównać, aby uzyskać poprawny wynik. Zarówno Python 2, jak i Python 3 używają do tego tych samych pomysłów (poprzedni obsługuje tylko inti longtypy osobno).

Pierwszą rzeczą, którą należy zrobić, to sprawdzić, że vjest na pewno pływak Python i mapować go do C podwójnie i. Następny wygląd Funkcja przy czy wteż pływaka i mapuje je do C podwójnym j. Jest to najlepszy scenariusz dla tej funkcji, ponieważ wszystkie inne kontrole można pominąć. Funkcja sprawdza również, czy vjest influb nan:

static PyObject*
float_richcompare(PyObject *v, PyObject *w, int op)
{
    double i, j;
    int r = 0;
    assert(PyFloat_Check(v));       
    i = PyFloat_AS_DOUBLE(v);       

    if (PyFloat_Check(w))           
        j = PyFloat_AS_DOUBLE(w);   

    else if (!Py_IS_FINITE(i)) {
        if (PyLong_Check(w))
            j = 0.0;
        else
            goto Unimplemented;
    }

Teraz wiemy, że jeśli wte testy nie powiodą się, nie jest to pływak w języku Python. Teraz funkcja sprawdza, czy jest liczbą całkowitą w języku Python. W takim przypadku najłatwiejszym sposobem jest wyodrębnienie znakuv i znaku w(zwróć, 0jeśli zero, -1jeśli ujemne, 1jeśli dodatnie). Jeśli znaki są różne, to wszystkie informacje potrzebne do zwrócenia wyniku porównania:

    else if (PyLong_Check(w)) {
        int vsign = i == 0.0 ? 0 : i < 0.0 ? -1 : 1;
        int wsign = _PyLong_Sign(w);
        size_t nbits;
        int exponent;

        if (vsign != wsign) {
            /* Magnitudes are irrelevant -- the signs alone
             * determine the outcome.
             */
            i = (double)vsign;
            j = (double)wsign;
            goto Compare;
        }
    }   

Jeśli to sprawdzenie się nie powiedzie, to vi wmieć ten sam znak.

Następne sprawdzenie liczy liczbę bitów w liczbie całkowitej w . Jeśli ma zbyt wiele bitów, nie może być utrzymywane jako liczba zmiennoprzecinkowa, a zatem musi mieć większą wielkość niż liczba zmiennoprzecinkowa v:

    nbits = _PyLong_NumBits(w);
    if (nbits == (size_t)-1 && PyErr_Occurred()) {
        /* This long is so large that size_t isn't big enough
         * to hold the # of bits.  Replace with little doubles
         * that give the same outcome -- w is so large that
         * its magnitude must exceed the magnitude of any
         * finite float.
         */
        PyErr_Clear();
        i = (double)vsign;
        assert(wsign != 0);
        j = wsign * 2.0;
        goto Compare;
    }

Z drugiej strony, jeśli liczba całkowita w ma 48 lub mniej bitów, można ją bezpiecznie przekształcić w podwójne C ji porównać:

    if (nbits <= 48) {
        j = PyLong_AsDouble(w);
        /* It's impossible that <= 48 bits overflowed. */
        assert(j != -1.0 || ! PyErr_Occurred());
        goto Compare;
    }

Od tego momentu wiemy o tym w ma 49 lub więcej bitów. Wygodnie będzie traktować wjako dodatnią liczbę całkowitą, więc w razie potrzeby zmień znak i operator porównania:

    if (nbits <= 48) {
        /* "Multiply both sides" by -1; this also swaps the
         * comparator.
         */
        i = -i;
        op = _Py_SwappedOp[op];
    }

Teraz funkcja patrzy na wykładnik pływaka. Przypomnij sobie, że liczba zmiennoprzecinkowa może być zapisana (znak ignorujący) jako znaczenie * 2 ^wykładnik oraz że znaczenie reprezentuje liczbę między 0,5 a 1:

    (void) frexp(i, &exponent);
    if (exponent < 0 || (size_t)exponent < nbits) {
        i = 1.0;
        j = 2.0;
        goto Compare;
    }

To sprawdza dwie rzeczy. Jeśli wykładnik jest mniejszy niż 0, liczba zmiennoprzecinkowa jest mniejsza niż 1 (a więc mniejsza pod względem wielkości niż jakakolwiek liczba całkowita). Lub, jeśli wykładnik jest mniejszy niż liczba bitów w, mamy to v < |w|od znaczenia i * 2 ^wykładnik jest mniejszy niż 2 ^nbity .

Niepowodzenie tych dwóch kontroli, funkcja sprawdza, czy wykładnik jest większy niż liczba bitów w w. To pokazuje, że ^wykładnik znaczenia i * 2 jest większy niż 2 ^nbity a zatem v > |w|:

    if ((size_t)exponent > nbits) {
        i = 2.0;
        j = 1.0;
        goto Compare;
    }

Jeśli to sprawdzenie się nie powiedzie, wiemy, że wykładnik liczby zmiennoprzecinkowej vjest taki sam, jak liczba bitów w liczbie całkowitej w.

Jedynym sposobem, w jaki można teraz porównać te dwie wartości, jest zbudowanie dwóch nowych liczb całkowitych Pythona z vi w. Chodzi o to, aby odrzucić część ułamkową v, podwoić liczbę całkowitą, a następnie dodać jedną. wjest również podwojony i te dwa nowe obiekty w języku Python można porównać, aby uzyskać poprawną wartość zwracaną. Korzystając z przykładu z małymi wartościami, 4.65 < 4określa się porównanie(2*4)+1 == 9 < 8 == (2*4) (zwracanie wartości false).

    {
        double fracpart;
        double intpart;
        PyObject *result = NULL;
        PyObject *one = NULL;
        PyObject *vv = NULL;
        PyObject *ww = w;

        // snip

        fracpart = modf(i, &intpart); // split i (the double that v mapped to)
        vv = PyLong_FromDouble(intpart);

        // snip

        if (fracpart != 0.0) {
            /* Shift left, and or a 1 bit into vv
             * to represent the lost fraction.
             */
            PyObject *temp;

            one = PyLong_FromLong(1);

            temp = PyNumber_Lshift(ww, one); // left-shift doubles an integer
            ww = temp;

            temp = PyNumber_Lshift(vv, one);
            vv = temp;

            temp = PyNumber_Or(vv, one); // a doubled integer is even, so this adds 1
            vv = temp;
        }
        // snip
    }
}

Dla zwięzłości pominąłem dodatkowe sprawdzanie błędów i wyrzucanie śmieci, które Python musi zrobić, gdy tworzy te nowe obiekty. Nie trzeba dodawać, że powoduje to dodatkowe obciążenie i wyjaśnia, dlaczego wartości wyróżnione w pytaniu są znacznie wolniejsze w porównaniu z innymi.

Oto podsumowanie kontroli przeprowadzanych przez funkcję porównania.

Niech vbędzie float i rzuć go jako podwójne C. Teraz, jeśli wjest również zmiennoprzecinkowe:

• Sprawdź, czy wjest nanlub inf. Jeśli tak, należy potraktować ten specjalny przypadek osobno, w zależności od rodzaju w.

• Jeśli nie, porównaj vi wbezpośrednio przez ich przedstawień jak podwaja C.

Jeśli wjest liczbą całkowitą:

• Wyodrębnij znaki vi w. Jeśli są różne, to wiemy vi wsą różne, a to jest większa wartość.

• ( Znaki są takie same. ) Sprawdź, czy wma zbyt wiele bitów, aby być liczbą zmiennoprzecinkową (więcej niż size_t). Jeśli tak, wma większą wielkość niż v.

• Sprawdź, czy wma 48 lub mniej bitów. Jeśli tak, można go bezpiecznie rzucić do podwójnego C bez utraty precyzji i porównać z nim v.

• ( wma więcej niż 48 bitów. Będziemy teraz traktować wjako dodatnią liczbę całkowitą, zmieniając odpowiednio operację porównania. )

• Rozważ wykładnik pływaka v. Jeśli wykładnik jest ujemny, to vjest mniejszy, 1a zatem mniejszy niż jakakolwiek dodatnia liczba całkowita. W przeciwnym razie, jeśli wykładnik jest mniejszy niż liczba bitów, wto musi być mniejszy niżw .

• Jeśli wykładnik vjest większy niż liczba bitów, wto vjest większy niżw .

• ( Wykładnik jest taki sam jak liczba bitów w w. )

• Ostatnia kontrola. Podziel vna części całkowite i ułamkowe. Podwój liczbę całkowitą i dodaj 1, aby skompensować część ułamkową. Teraz podwoj liczbę całkowitą w. Porównaj te dwie nowe liczby całkowite, aby uzyskać wynik.

Używając gmpy2dowolnych liczb zmiennoprzecinkowych i liczb całkowitych, można uzyskać bardziej jednolite wyniki porównania:

~ $ ptipython
Python 3.5.1 |Anaconda 4.0.0 (64-bit)| (default, Dec  7 2015, 11:16:01) 
Type "copyright", "credits" or "license" for more information.

IPython 4.1.2 -- An enhanced Interactive Python.
?         -> Introduction and overview of IPython's features.
%quickref -> Quick reference.
help      -> Python's own help system.
object?   -> Details about 'object', use 'object??' for extra details.

In [1]: import gmpy2

In [2]: from gmpy2 import mpfr

In [3]: from gmpy2 import mpz

In [4]: gmpy2.get_context().precision=200

In [5]: i1=562949953421000

In [6]: i2=562949953422000

In [7]: f=562949953420000.7

In [8]: i11=mpz('562949953421000')

In [9]: i12=mpz('562949953422000')

In [10]: f1=mpfr('562949953420000.7')

In [11]: f<i1
Out[11]: True

In [12]: f<i2
Out[12]: True

In [13]: f1<i11
Out[13]: True

In [14]: f1<i12
Out[14]: True

In [15]: %timeit f<i1
The slowest run took 10.15 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 441 ns per loop

In [16]: %timeit f<i2
The slowest run took 12.55 times longer than the fastest. This could mean that an intermediate result is being cached.
10000000 loops, best of 3: 152 ns per loop

In [17]: %timeit f1<i11
The slowest run took 32.04 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 269 ns per loop

In [18]: %timeit f1<i12
The slowest run took 36.81 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 231 ns per loop

In [19]: %timeit f<i11
The slowest run took 78.26 times longer than the fastest. This could mean that an intermediate result is being cached.
10000000 loops, best of 3: 156 ns per loop

In [20]: %timeit f<i12
The slowest run took 21.24 times longer than the fastest. This could mean that an intermediate result is being cached.
10000000 loops, best of 3: 194 ns per loop

In [21]: %timeit f1<i1
The slowest run took 37.61 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 275 ns per loop

In [22]: %timeit f1<i2
The slowest run took 39.03 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 259 ns per loop