Warum sind einige Float <Integer-Vergleiche viermal langsamer als andere?

Beim Vergleich von Floats mit ganzen Zahlen dauert die Auswertung einiger Wertepaare viel länger als bei anderen Werten ähnlicher Größe.

Beispielsweise:

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

Wenn der Gleitkomma oder die Ganzzahl jedoch um einen bestimmten Betrag kleiner oder größer wird, läuft der Vergleich viel schneller ab:

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

Das Ändern des Vergleichsoperators (z. B. Verwenden von ==oder >stattdessen) wirkt sich nicht merklich auf die Zeiten aus.

Dies hängt nicht nur mit der Größe zusammen, da die Auswahl größerer oder kleinerer Werte zu schnelleren Vergleichen führen kann. Ich vermute, dass dies auf eine unglückliche Art und Weise zurückzuführen ist, in der die Bits ausgerichtet sind.

Der Vergleich dieser Werte ist für die meisten Anwendungsfälle eindeutig mehr als schnell genug. Ich bin einfach neugierig, warum Python mit einigen Wertepaaren mehr zu kämpfen hat als mit anderen.

Ein Kommentar im Python-Quellcode für Float-Objekte bestätigt Folgendes:

Der Vergleich ist so ziemlich ein Albtraum

Dies gilt insbesondere beim Vergleich eines Floats mit einer Ganzzahl, da Ganzzahlen in Python im Gegensatz zu Floats beliebig groß sein können und immer genau sind. Der Versuch, die Ganzzahl in einen Float umzuwandeln, kann an Genauigkeit verlieren und den Vergleich ungenau machen. Der Versuch, den Float in eine Ganzzahl umzuwandeln, funktioniert ebenfalls nicht, da ein Bruchteil verloren geht.

Um dieses Problem zu umgehen, führt Python eine Reihe von Überprüfungen durch und gibt das Ergebnis zurück, wenn eine der Überprüfungen erfolgreich ist. Es vergleicht die Vorzeichen der beiden Werte, ob die Ganzzahl "zu groß" ist, um ein Float zu sein, und vergleicht dann den Exponenten des Floats mit der Länge der Ganzzahl. Wenn alle diese Überprüfungen fehlschlagen, müssen zwei neue Python-Objekte zum Vergleich erstellt werden, um das Ergebnis zu erhalten.

Beim Vergleich eines Floats vmit einer Ganzzahl / Long wist der schlimmste Fall:

• vund whaben das gleiche Vorzeichen (beide positiv oder beide negativ),
• Die Ganzzahl what nur wenige Bits, die im size_tTyp enthalten sein können (normalerweise 32 oder 64 Bit).
• die ganze Zahl what mindestens 49 Bits,
• Der Exponent des Floats entspricht vder Anzahl der Bits in w.

Und genau das haben wir für die Werte in der Frage:

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

Wir sehen, dass 49 sowohl der Exponent des Floats als auch die Anzahl der Bits in der Ganzzahl ist. Beide Zahlen sind positiv und somit sind die vier oben genannten Kriterien erfüllt.

Wenn Sie einen der Werte als größer (oder kleiner) auswählen, kann sich die Anzahl der Bits der Ganzzahl oder der Wert des Exponenten ändern, sodass Python das Ergebnis des Vergleichs ermitteln kann, ohne die teure Endprüfung durchzuführen.

Dies ist spezifisch für die CPython-Implementierung der Sprache.

Der Vergleich im Detail

Die float_richcompareFunktion übernimmt den Vergleich zwischen zwei Werten vund w.

Im Folgenden finden Sie eine schrittweise Beschreibung der von der Funktion durchgeführten Überprüfungen. Die Kommentare in der Python-Quelle sind tatsächlich sehr hilfreich, wenn Sie versuchen zu verstehen, was die Funktion tut. Deshalb habe ich sie dort belassen, wo sie relevant sind. Ich habe diese Überprüfungen auch in einer Liste am Fuße der Antwort zusammengefasst.

Die Hauptidee ist die Python - Objekte abzubilden vund wzu zwei entsprechenden C verdoppelt, iund j, die dann leicht das richtige Ergebnis zu geben , verglichen werden. Sowohl Python 2 als auch Python 3 verwenden dazu dieselben Ideen (erstere behandeln intund longtippen nur separat).

Als erstes müssen Sie überprüfen, ob ves sich definitiv um einen Python-Float handelt, und ihn einem C-Double zuordnen i. Als nächstes prüft die Funktion, ob wes sich auch um ein Float handelt, und ordnet es einem C-Double zu j. Dies ist das beste Szenario für die Funktion, da alle anderen Überprüfungen übersprungen werden können. Die Funktion kann auch überprüft, ob vist infoder 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;
    }

Jetzt wissen wir, dass es sich bei wdiesen Überprüfungen nicht um einen Python-Float handelt. Jetzt prüft die Funktion, ob es sich um eine Python-Ganzzahl handelt. Wenn dies der Fall ist, besteht der einfachste Test darin, das Vorzeichen vund das Vorzeichen von zu extrahieren w(Rückgabe, 0wenn Null, -1wenn negativ, 1wenn positiv). Wenn die Vorzeichen unterschiedlich sind, sind dies alle Informationen, die erforderlich sind, um das Ergebnis des Vergleichs zurückzugeben:

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

Wenn diese Prüfung fehlgeschlagen ist , dann vund wdas gleiche Vorzeichen haben .

Die nächste Prüfung zählt die Anzahl der Bits in der Ganzzahl w. Wenn es zu viele Bits hat, kann es möglicherweise nicht als Float gehalten werden und muss daher größer sein als der Float 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;
    }

Wenn die Ganzzahl dagegen w48 oder weniger Bits hat, kann sie sicher in ein C-Doppel umgewandelt jund verglichen werden:

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

Ab diesem Zeitpunkt wissen wir, dass w49 oder mehr Bits vorhanden sind. Es ist praktisch, weine positive Ganzzahl zu behandeln. Ändern Sie daher das Vorzeichen und den Vergleichsoperator nach Bedarf:

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

Jetzt betrachtet die Funktion den Exponenten des Floats. Denken Sie daran, dass ein Float als ^{Exponent des} Signifikanten * 2 geschrieben werden kann (Vorzeichen ignorieren) und dass der Signifikand eine Zahl zwischen 0,5 und 1 darstellt:

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

Dies überprüft zwei Dinge. Wenn der Exponent kleiner als 0 ist, ist der Float kleiner als 1 (und daher kleiner als jede ganze Zahl). Oder, wenn der Exponent kleiner ist als die Anzahl der Bits in wdann haben wir , dass v < |w|seit Signifikanden * 2 ^Exponenten weniger als 2 ^nBits .

Wenn diese beiden Prüfungen fehlschlagen, prüft die Funktion, ob der Exponent größer als die Anzahl der Bit-In ist w. Dies zeigt, dass der ^{Exponent des} Signifikanten * 2 größer als 2 ^{nbit ist} und so v > |w|:

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

Wenn diese Prüfung nicht erfolgreich war, wissen wir, dass der Exponent des Gleitkommas vder Anzahl der Bits in der Ganzzahl entspricht w.

Die einzige Möglichkeit, die beiden Werte jetzt zu vergleichen, besteht darin, zwei neue Python-Ganzzahlen aus vund zu erstellen w. Die Idee ist, den Bruchteil von zu verwerfen v, den ganzzahligen Teil zu verdoppeln und dann einen hinzuzufügen. wwird ebenfalls verdoppelt und diese beiden neuen Python-Objekte können verglichen werden, um den korrekten Rückgabewert zu erhalten. Die Verwendung eines Beispiels mit kleinen Werten 4.65 < 4würde durch den Vergleich bestimmt (2*4)+1 == 9 < 8 == (2*4)(Rückgabe von 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
    }
}

Der Kürze halber habe ich die zusätzliche Fehlerprüfung und Müllverfolgung, die Python beim Erstellen dieser neuen Objekte durchführen muss, weggelassen. Dies erhöht natürlich den zusätzlichen Aufwand und erklärt, warum die in der Frage hervorgehobenen Werte wesentlich langsamer zu vergleichen sind als andere.

Hier ist eine Zusammenfassung der Überprüfungen, die von der Vergleichsfunktion durchgeführt werden.

Sei vein Schwimmer und wirf ihn als C-Doppel. Nun, wenn wist auch ein Schwimmer:

• Überprüfen Sie, ob wist nanoder inf. Wenn ja, behandeln Sie diesen Sonderfall je nach Art separat w.

• Wenn nicht, vergleichen Sie vund wdirekt durch ihre Darstellungen als C verdoppelt sich.

Wenn wist eine ganze Zahl:

• Extrahieren Sie die Zeichen von vund w. Wenn sie unterschiedlich sind, dann wissen wir vund wsind unterschiedlich und welches ist der größere Wert.

• ( Die Vorzeichen sind die gleichen. ) Überprüfen Sie, ob wzu viele Bits vorhanden sind, um ein Float zu sein (mehr als size_t). Wenn ja, what eine größere Größe als v.

• Überprüfen Sie, ob w48 oder weniger Bits vorhanden sind. Wenn ja, kann es sicher in ein C-Doppel gegossen werden, ohne seine Präzision zu verlieren, und mit verglichen werden v.

• ( what mehr als 48 Bits. Wir werden jetzt wals positive Ganzzahl behandeln, nachdem wir die Vergleichsoperation entsprechend geändert haben. )

• Betrachten Sie den Exponenten des Schwimmers v. Wenn der Exponent negativ ist, vist er kleiner als 1und daher kleiner als jede positive ganze Zahl. Andernfalls muss der Exponent kleiner als die Anzahl der Bits wsein w.

• Wenn der Exponent von vgrößer als die Anzahl der Bits wist, vist er größer als w.

• ( Der Exponent entspricht der Anzahl der Bits in w. )

• Die letzte Überprüfung. Split vin die ganzzahlige und gebrochene Teile. Verdoppeln Sie den ganzzahligen Teil und addieren Sie 1, um den Bruchteil zu kompensieren. Verdoppeln Sie jetzt die ganze Zahl w. Vergleichen Sie stattdessen diese beiden neuen Ganzzahlen, um das Ergebnis zu erhalten.

Mit gmpy2Floats und Ganzzahlen mit beliebiger Genauigkeit ist es möglich, eine einheitlichere Vergleichsleistung zu erzielen:

~ $ 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