python - troncare - virgola mobile esercizi svolti




Perché alcuni confronti float<interi sono quattro volte più lenti di altri? (2)

Un commento nel codice sorgente di Python per oggetti float riconosce che:

Il confronto è praticamente un incubo

Ciò è particolarmente vero quando si confronta un float con un numero intero, perché, a differenza dei float, i numeri interi in Python possono essere arbitrariamente grandi e sono sempre esatti. Cercare di lanciare il numero intero su un float potrebbe perdere precisione e rendere impreciso il confronto. Cercare di lanciare il float su un numero intero non funzionerà nemmeno perché qualsiasi parte frazionaria andrà persa.

Per aggirare questo problema, Python esegue una serie di controlli, restituendo il risultato se uno dei controlli ha esito positivo. Confronta i segni dei due valori, quindi se l'intero è "troppo grande" per essere un float, quindi confronta l'esponente del float con la lunghezza dell'intero. Se tutti questi controlli falliscono, è necessario costruire due nuovi oggetti Python da confrontare per ottenere il risultato.

Quando si confronta un float v con un numero intero / long w , il caso peggiore è che:

  • v e w hanno lo stesso segno (sia positivo che entrambi negativi),
  • l'intero w ha pochi bit sufficienti per poter essere mantenuto nel tipo size_t (in genere 32 o 64 bit),
  • l'intero w ha almeno 49 bit,
  • l'esponente del float v è uguale al numero di bit in w .

E questo è esattamente ciò che abbiamo per i valori nella domanda:

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

Vediamo che 49 è sia l'esponente del float che il numero di bit nell'intero. Entrambi i numeri sono positivi e quindi i quattro criteri sopra sono soddisfatti.

La scelta di uno dei valori più grandi (o più piccoli) può modificare il numero di bit dell'intero o il valore dell'esponente, quindi Python è in grado di determinare il risultato del confronto senza eseguire il costoso controllo finale.

Questo è specifico per l'implementazione CPython del linguaggio.

Il confronto in modo più dettagliato

La funzione float_richcompare gestisce il confronto tra due valori v e w .

Di seguito è riportata una descrizione dettagliata dei controlli eseguiti dalla funzione. I commenti nella fonte Python sono in realtà molto utili quando si cerca di capire cosa fa la funzione, quindi li ho lasciati pertinenti. Ho anche riassunto questi controlli in un elenco ai piedi della risposta.

L'idea principale è quella di mappare gli oggetti Python v e w su due doppi C appropriati, j , che possono quindi essere facilmente confrontati per dare il risultato corretto. Sia Python 2 che Python 3 usano le stesse idee per fare questo (il primo gestisce solo int e long tipi separatamente).

La prima cosa da fare è verificare che v sia decisamente un float Python e mapparlo su un doppio C in i . Successivamente la funzione esamina se w è anche un float e lo mappa su una C doppia j . Questo è lo scenario migliore per la funzione poiché è possibile saltare tutti gli altri controlli. La funzione controlla anche se v è inf o 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;
    }

Ora sappiamo che se w fallito questi controlli, non è un float Python. Ora la funzione controlla se è un numero intero Python. In questo caso, il test più semplice è quello di estrarre il segno di v e il segno di w (restituisce 0 se zero, -1 se negativo, 1 se positivo). Se i segni sono diversi, queste sono tutte le informazioni necessarie per restituire il risultato del confronto:

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

Se questo controllo ha esito negativo, v e w hanno lo stesso segno.

Il controllo successivo conta il numero di bit nell'intero w . Se ha troppi bit, allora non può essere tenuto come un float e quindi deve avere una grandezza maggiore del 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;
    }

D'altra parte, se l'intero w ha 48 o meno bit, può tranquillamente trasformarsi in una C doppia j e confrontare:

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

Da questo punto in poi, sappiamo che w ha 49 o più bit. Sarà conveniente trattare w come un numero intero positivo, quindi cambia il segno e l'operatore di confronto come necessario:

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

Ora la funzione guarda l'esponente del galleggiante. Ricorda che un float può essere scritto (ignorando il segno) come significante * 2 esponente e che il significante rappresenta un numero compreso tra 0,5 e 1:

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

Questo controlla due cose. Se l'esponente è inferiore a 0, il galleggiante è minore di 1 (e quindi di dimensioni inferiori rispetto a qualsiasi numero intero). Oppure, se l'esponente è inferiore al numero di bit in w allora abbiamo v < |w| poiché significante * 2 esponente è inferiore a 2 nbit .

In mancanza di questi due controlli, la funzione cerca di vedere se l'esponente è maggiore del numero di bit in w . Questo dimostra che significante * 2 esponente è maggiore di 2 nbit e quindi v > |w| :

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

Se questo controllo non ha esito positivo, sappiamo che l'esponente del float v è uguale al numero di bit nell'intero w .

L'unico modo per confrontare i due valori ora è costruire due nuovi numeri interi Python da v e w . L'idea è di scartare la parte frazionaria di v , raddoppiare la parte intera e quindi aggiungerne una. w viene raddoppiato e questi due nuovi oggetti Python possono essere confrontati per fornire il valore di ritorno corretto. Usando un esempio con valori piccoli, 4.65 < 4 sarebbe determinato dal confronto (2*4)+1 == 9 < 8 == (2*4) (restituendo 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
    }
}

Per brevità ho tralasciato il controllo degli errori aggiuntivo e il tracciamento dei rifiuti che Python deve fare quando crea questi nuovi oggetti. Inutile dire che questo aggiunge un sovraccarico aggiuntivo e spiega perché i valori evidenziati nella domanda sono significativamente più lenti da confrontare rispetto ad altri.

Ecco un riepilogo dei controlli eseguiti dalla funzione di confronto.

Lascia che v sia un float e lancialo come double C. Ora, se w è anche un float:

  • Controlla se w è nan o inf . In tal caso, maneggiare questa custodia speciale separatamente in base al tipo di w .

  • In caso contrario, confrontare v e w direttamente dalle loro rappresentazioni come doppi di C.

Se w è un numero intero:

  • Estrarre i segni di v e w . Se sono diversi, allora sappiamo che v e w sono diversi e qual è il valore maggiore.

  • ( I segni sono gli stessi. ) Controlla se w ha troppi bit per essere un float (più di size_t ). In tal caso, w ha una magnitudine maggiore di v .

  • Controlla se w ha 48 o meno bit. In tal caso, può essere lanciato in modo sicuro su una doppia C senza perdere la sua precisione e confrontato con v .

  • ( w ha più di 48 bit. Tratteremo ora w come un numero intero positivo dopo aver modificato l'operazione di confronto nel modo appropriato. )

  • Considera l'esponente del galleggiante v . Se l'esponente è negativo, allora v è inferiore a 1 e quindi inferiore a qualsiasi numero intero positivo. Altrimenti, se l'esponente è inferiore al numero di bit in w allora deve essere inferiore a w .

  • Se l'esponente di v è maggiore del numero di bit in w allora v è maggiore di w .

  • ( L'esponente è uguale al numero di bit in w . )

  • Il controllo finale. Dividi v nelle sue parti intere e frazionarie. Raddoppia la parte intera e aggiungi 1 per compensare la parte frazionaria. Ora raddoppia il numero intero w . Confronta invece questi due nuovi numeri interi per ottenere il risultato.

Quando si confrontano float con numeri interi, alcune coppie di valori richiedono molto più tempo per essere valutate rispetto ad altri valori di grandezza simile.

Per esempio:

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

Ma se il float o il numero intero vengono resi più piccoli o più grandi di una certa quantità, il confronto viene eseguito molto più rapidamente:

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

La modifica dell'operatore di confronto (ad esempio utilizzando == o > invece) non influisce in alcun modo sui tempi.

Questo non è solo correlato alla grandezza perché la selezione di valori maggiori o minori può portare a confronti più rapidi, quindi sospetto che sia in qualche modo sfortunato che i bit si allineano.

Chiaramente, il confronto di questi valori è più che abbastanza veloce per la maggior parte dei casi d'uso. Sono semplicemente curioso di sapere perché Python sembra lottare più con alcune coppie di valori che con altre.


Usando gmpy2 con float e numeri interi di precisione arbitraria è possibile ottenere prestazioni di confronto più uniformi:

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




python-internals