¿Por qué algunas comparaciones float

Al comparar flotadores con enteros, algunos pares de valores tardan mucho más en evaluarse que otros valores de magnitud similar.

Por ejemplo: 

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

Pero si el float o entero se hace más pequeño o más grande en cierta cantidad, la comparación se ejecuta mucho más rápidamente:

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

Cambiar el operador de comparación (por ejemplo, usando == o > en su lugar) no afecta los tiempos de ninguna manera notable.

Esto no está únicamente relacionado con la magnitud porque recoger valores más grandes o más pequeños puede resultar en comparaciones más rápidas, por lo que sospecho que se debe a una forma desafortunada en que los bits se alinean.

Claramente, comparar estos valores es más que lo suficientemente rápido para la mayoría de los casos de uso. Simplemente tengo curiosidad por saber por qué Python parece luchar más con algunos pares de valores que con otros.

Author: Alex Riley, 2015-05-07
Source

2 answers

Un comentario en el código fuente de Python para objetos flotantes reconoce que:

La comparación es más o menos una pesadilla

Esto es especialmente cierto cuando se compara un flotador con un entero, porque, a diferencia de los flotadores, los enteros en Python pueden ser arbitrariamente grandes y siempre son exactos. Intentar convertir el entero a un flotador puede perder precisión y hacer que la comparación sea inexacta. Tratar de convertir el flotador a un entero tampoco va a funcionar porque cualquier parte fraccionaria se perderá.

Para evitar este problema, Python realiza una serie de comprobaciones, devolviendo el resultado si una de las comprobaciones tiene éxito. Compara los signos de los dos valores, luego si el entero es "demasiado grande" para ser un flotador, luego compara el exponente del flotador con la longitud del entero. Si todas estas comprobaciones fallan, es necesario construir dos nuevos objetos Python para comparar con el fin de obtener el resultado.

Al comparar un flotador v con un integer / long w, el peor de los casos es que:

  • v y w tienen el mismo signo (ambos positivos o ambos negativos),
  • el entero w tiene pocos bits suficientes para que se pueda mantener en el size_t tipo (típicamente 32 o 64 bits),
  • el entero w tiene al menos 49 bits,
  • el exponente del flotador v es el mismo que el número de bits en w.

Y esto es exactamente lo que tenemos para los valores en el pregunta:

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

Vemos que 49 es tanto el exponente del flotador como el número de bits en el entero. Ambos números son positivos y por lo tanto se cumplen los cuatro criterios anteriores.

Elegir uno de los valores para ser más grande (o más pequeño) puede cambiar el número de bits del entero, o el valor del exponente, y así Python es capaz de determinar el resultado de la comparación sin realizar la costosa comprobación final.

Esto es específico para la implementación de CPython de idioma.

La comparación con más detalle

El float_richcompare la función maneja la comparación entre dos valores v y w.

A continuación se muestra una descripción paso a paso de las comprobaciones que realiza la función. Los comentarios en la fuente de Python son realmente muy útiles cuando se trata de entender lo que hace la función, así que los he dejado en donde sea relevante. También he resumido estas comprobaciones en una lista al pie de la respuesta.

El la idea principal es asignar los objetos Python v y w a dos dobles C apropiados, i y j, que luego se pueden comparar fácilmente para dar el resultado correcto. Tanto Python 2 como Python 3 usan las mismas ideas para hacer esto (el primero solo maneja los tipos int y long por separado).

Lo primero que hay que hacer es comprobar que v es definitivamente un Python float y asignarlo a un C double i. A continuación, la función examina si w es también un flotador y lo asigna a un C double j. Este es el mejor escenario para la función, ya que todas las demás comprobaciones se pueden omitir. La función también comprueba si v es 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;
    }

Ahora sabemos que si w falló estas comprobaciones, no es un float de Python. Ahora la función comprueba si es un entero de Python. Si este es el caso, la prueba más fácil es extraer el signo de v y el signo de w (devuelve 0 si es cero, -1 si es negativo, 1 si es positivo). Si los signos son diferentes, esto es todo la información necesaria para devolver el resultado de la comparación:

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

Si esta comprobación falla, entonces v y w tienen el mismo signo.

La siguiente comprobación cuenta el número de bits en el entero w. Si tiene demasiados bits, entonces no puede sostenerse como un flotador y, por lo tanto, debe ser mayor en magnitud que el flotador 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;
    }

Por otro lado, si el entero w tiene 48 o menos bits, puede girar con seguridad en un doble C j y comparado: 

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

Desde este punto en adelante, sabemos que w tiene 49 o más bits. Será conveniente tratar w como un entero positivo, así que cambie el signo y el operador de comparación según sea necesario: 

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

Ahora la función mira el exponente del flotador. Recuerde que un flotador se puede escribir (ignorando el signo) como significando * 2 exponente y que el significando representa un número entre 0.5 y 1:

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

Esto comprueba dos cosas. Si el exponente es menor que 0 entonces el flotador es menor que 1 (y por lo tanto menor en magnitud que cualquier entero). O, si el exponente es menor que el número de bits en w entonces tenemos que v < |w| desde mantisa * 2exponente está a menos de 2nbits.

Fallando estas dos comprobaciones, la función busca ver si el exponente es mayor que el número de bits en w. Esto demuestra que la mantisa * 2exponente es mayor que 2nbits y así que v > |w|: 

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

Si esta comprobación no tuvo éxito, sabemos que el exponente del flotador v es el mismo que el número de bits en el entero w.

La única forma de comparar los dos valores ahora es construir dos nuevos enteros de Python desde v y w. La idea es descartar la parte fraccionaria de v, duplicar la parte entera, y luego agregar una. w también se duplica y estos dos nuevos objetos Python se pueden comparar para dar el valor de retorno correcto. Usando un ejemplo con valores pequeños, 4.65 < 4 sería determinado por la comparación (2*4)+1 == 9 < 8 == (2*4) (devolviendo 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
    }
}

Por brevedad he omitido la comprobación de errores adicional y el seguimiento de basura que Python tiene que hacer cuando crea estos nuevos objetos. No hace falta decir que esto agrega sobrecarga adicional y explica por qué los valores resaltados en la pregunta son significativamente más lentos de comparar que otros.

Aquí hay un resumen de las comprobaciones que se realizan mediante la comparación función.

Sea v un flotador y colóquelo como un Do doble. Ahora, si w es también un flotador:

  • Compruebe si w es nan o inf. Si es así, maneje este caso especial por separado dependiendo del tipo de w.

  • Si no, compare v y w directamente por sus representaciones como C dobles.

Si w es un entero:

  • Extraiga los signos de v y w. Si son diferentes entonces sabemos que v y w son diferentes y cuál es el valor mayor.

  • (Las señales son las mismas.) Compruebe si w tiene demasiados bits para ser un flotador (más que size_t). Si es así, w tiene mayor magnitud que v.

  • Compruebe si w tiene 48 bits o menos. Si es así, se puede lanzar con seguridad a un doble C sin perder su precisión y en comparación con v.

  • (w tiene más de 48 bits. Lo haremos ahora trate w como un entero positivo que ha cambiado el op de comparación según corresponda.)

  • Considere el exponente del flotador v. Si el exponente es negativo, entonces v es menor que 1 y por lo tanto menor que cualquier entero positivo. Otra cosa, si el exponente es menor que el número de bits en w, entonces debe ser menor que w.

  • Si el exponente de v es mayor que el número de bits en w entonces v es mayor que w.

  • (El exponente es el mismo que el número de bits en w.)

  • La comprobación final. Dividir v en sus partes entera y fraccionaria. Doble la parte entera y agregue 1 para compensar la parte fraccionaria. Ahora duplica el entero w. Compare estos dos nuevos enteros para obtener el resultado.

 350
Author: Alex Riley,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-05-23 12:34:21

Usando gmpy2 con flotadores de precisión arbitraria y enteros es posible obtener un rendimiento de comparación más uniforme: 

~ $ 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
Author: denfromufa,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-04-15 05:00:19