wake-up-neo.com

Warum sind einige float <integer-Vergleiche viermal langsamer als andere?

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

Beispielsweise:

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

Wenn der Gleitkommawert oder die Ganzzahl jedoch um einen bestimmten Betrag verkleinert oder vergrößert wird, wird der Vergleich viel schneller ausgeführt:

>>> 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. mit == Oder >) Wirkt sich nicht auf die Zeiten aus.

Dies ist nicht nur abhängig von der Größe, da die Auswahl größerer oder kleinerer Werte zu schnelleren Vergleichen führen kann. Ich vermute, dass die Bit-Aneinanderreihung auf eine unglückliche Weise zurückzuführen ist.

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

282
Alex Riley

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

Vergleich ist so ziemlich ein Albtraum

Dies gilt insbesondere für den Vergleich eines Floats mit einer Ganzzahl, da Ganzzahlen in Python) im Gegensatz zu Floats willkürlich groß und immer genau sein können. Der Versuch, die Ganzzahl in einen Float umzuwandeln, kann die Genauigkeit verlieren Machen Sie den Vergleich ungenau. Der Versuch, den Gleitkommawert 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 war. Es vergleicht die Vorzeichen der beiden Werte und dann, ob die Ganzzahl "zu groß" ist. Um ein float zu sein, vergleicht man den Exponenten des float mit der Länge der Ganzzahl.Wenn alle diese Prüfungen fehlschlagen, müssen zwei neue Python zu vergleichende Objekte erstellt werden, um zu erhalten das Ergebnis.

Beim Vergleich eines Gleitkommas v mit einer Ganzzahl/Länge w ist der schlimmste Fall der folgende:

  • v und w haben das gleiche Vorzeichen (beide positiv oder beide negativ),
  • die Ganzzahl w enthält wenige Bits, die im size_t Typ (normalerweise 32 oder 64 Bit),
  • die ganze Zahl w hat mindestens 49 Bits,
  • der Exponent des Gleitkommas v entspricht der 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 Gleitkommas 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 größer (oder kleiner) wählen, kann sich die Anzahl der Bits der Ganzzahl oder der Wert des Exponenten ändern, sodass Python das Ergebnis des Vergleichs bestimmen kann ohne die teure Endkontrolle durchzuführen.

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


Der Vergleich im Detail

Das float_richcompare Funktion behandelt den Vergleich zwischen zwei Werten v und w.

Nachfolgend 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 bewirkt. Deshalb habe ich sie an den relevanten Stellen belassen. Ich habe diese Prüfungen auch in einer Liste in der zusammengefasst Fuß der Antwort.

Die Hauptidee ist, die Python= Objekte v und w auf zwei entsprechende C-Doubles, i und j, das dann leicht verglichen werden kann, um das richtige Ergebnis zu erhalten. Sowohl Python 2 als auch Python 3 verwenden dazu die gleichen Ideen (the ehemalige behandelt nur int und long Typen getrennt).

Überprüfen Sie zunächst, ob v definitiv ein Python= float ist, und ordnen Sie es einem C double i zu. Als Nächstes überprüft die Funktion, ob w ist ebenfalls ein Float und ordnet es einem C double j zu. Dies ist das beste Szenario für die Funktion, da alle anderen Prüfungen übersprungen werden können ob vinf oder nan ist:

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 wenn w diese Prüfungen nicht bestanden hat, es kein Python float ist. Jetzt prüft die Funktion, ob es eine Python integer ist Ist dies der Fall, besteht der einfachste Test darin, das Vorzeichen von v und das Vorzeichen von w zu extrahieren (return 0 wenn Null, -1 falls negativ, 1 wenn 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, haben v und w dasselbe Vorzeichen.

Bei der nächsten Überprüfung wird die Anzahl der Bits in der Ganzzahl w gezählt. 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 andererseits die Ganzzahl w 48 oder weniger Bits hat, kann sie sicher in ein C double j umgewandelt und verglichen werden:

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

Von diesem Punkt an wissen wir, dass w 49 oder mehr Bits hat. Es ist praktisch, w als 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];
    }

Die Funktion betrachtet nun den Exponenten des Floats. Denken Sie daran, dass ein Float als Signifikant * 2 geschrieben werden kann (ohne Vorzeichen)exponent 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 Gleitkommawert kleiner als 1 (und daher betragsmäßig kleiner als eine ganze Zahl). Oder, wenn der Exponent kleiner ist als die Anzahl der Bits in w, dann haben wir das v < |w| seit Bedeutung * 2exponent ist kleiner als 2nbits.

Wenn diese beiden Überprüfungen fehlschlagen, prüft die Funktion, ob der Exponent größer als die Anzahl der Bits in w ist. Dies zeigt den Signifikanten * 2exponent ist größer als 2nbits 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 v der Anzahl der Bits in der Ganzzahl w entspricht.

Die einzige Möglichkeit, die beiden Werte jetzt zu vergleichen, besteht darin, aus v und w zwei neue Python) - Ganzzahlen zu erstellen Bruchteil von v, verdoppeln Sie den ganzzahligen Teil, und fügen Sie dann einen hinzu. w wird ebenfalls verdoppelt, und diese beiden neuen Python - Objekte können verglichen werden Geben Sie den korrekten Rückgabewert an. Verwenden Sie ein Beispiel mit kleinen Werten, 4.65 < 4 würde bestimmt durch den Vergleich (2*4)+1 == 9 < 8 == (2*4) (false zurückgeben).

    {
        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 Fehlerüberprüfung und Garbage-Tracking-Funktion ausgelassen. Python erstellt diese neuen Objekte. Es ist unnötig zu erwähnen, dass dies zusätzlichen Aufwand verursacht und erklärt, warum die Werte hervorgehoben wurden in der Frage sind deutlich langsamer zu vergleichen als andere.


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

Sei v ein float und wirf es als C double. Nun, wenn w auch ein Float ist:

  • Überprüfen Sie, ob wnan oder inf ist. Wenn ja, behandeln Sie diesen Sonderfall separat, abhängig vom Typ von w.

  • Wenn nicht, vergleiche v und w direkt anhand ihrer Darstellungen als C-Doppel.

Wenn w eine ganze Zahl ist:

  • Extrahieren Sie die Zeichen von v und w. Wenn sie unterschiedlich sind, wissen wir, dass v und w unterschiedlich sind und welcher Wert größer ist.

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

  • Überprüfen Sie, ob w 48 oder weniger Bits enthält. In diesem Fall kann es sicher in ein C-Double umgewandelt werden, ohne seine Präzision zu verlieren, und mit v verglichen werden.

  • (w hat mehr als 48 Bits. Wir werden nun w als positive Ganzzahl behandeln, nachdem wir die Vergleichsoperation entsprechend geändert haben. )

  • Betrachten Sie den Exponenten des Floats v. Wenn der Exponent negativ ist, ist v kleiner als 1 und damit kleiner als jede positive ganze Zahl. Ist der Exponent kleiner als die Anzahl der Bits in w, muss er kleiner als w sein.

  • Ist der Exponent von v größer als die Anzahl der Bits in w, so ist v größer als w.

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

  • Die Endkontrolle. Teilen Sie v in seine ganzzahligen und gebrochenen Teile auf. Verdoppeln Sie den ganzzahligen Teil und addieren Sie 1, um den Bruchteil zu kompensieren. Verdoppeln Sie nun die ganze Zahl w. Vergleichen Sie stattdessen diese beiden neuen Ganzzahlen, um das Ergebnis zu erhalten.

351
Alex Riley

Mit gmpy2 mit beliebig präzisen Gleitkommazahlen und ganzen Zahlen ist es möglich, eine gleichmäßigere 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
4
denfromufa