¿Por qué algunas comparaciones de números flotantes < enteros son cuatro veces más lentas que otras?

13 minutos de lectura

avatar de usuario
Alex Riley

Cuando se comparan números flotantes con números enteros, algunos pares de valores tardan mucho más en evaluarse que otros valores de una magnitud similar.

Por ejemplo:

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

Pero si el flotante o el entero se hacen más pequeños o más grandes en cierta cantidad, la comparación se ejecuta mucho más rápido:

>>> 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 cambio) no afecta los tiempos de ninguna manera notable.

Esto no es solamente relacionado con la magnitud porque elegir 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 alguna desafortunada forma en que se alinean los bits.

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

  • ¿Es lo mismo en 2.7 y 3.x?

    – los cuatro ojos

    7 mayo 2015 a las 12:16

  • Los tiempos anteriores son de Python 3.4: en mi computadora Linux con 2.7 hubo una discrepancia similar en los tiempos (entre 3 y 4 veces y un poco más lento).

    – Alex Riley

    7 mayo 2015 a las 12:20


  • Gracias por el interesante escrito. Tengo curiosidad por saber qué inspiró la pregunta: ¿fueron comparaciones de tiempo aleatorias o hay una historia detrás?

    – Veedrac

    7 mayo 2015 a las 19:18

  • @Veedrac: Gracias. No hay mucha historia: distraídamente me pregunté qué tan rápido se compararon los números flotantes y los números enteros, cronometré algunos valores y noté algunas pequeñas diferencias. Entonces me di cuenta de que no tenía ni idea de cómo Python lograba comparar con precisión números flotantes y enteros grandes. Pasé un tiempo tratando de entender la fuente y aprendí cuál es el peor de los casos.

    – Alex Riley

    7 mayo 2015 a las 20:03


  • @YvesDaoust: no esos valores particulares, no (¡eso hubiera sido una suerte increíble!). Probé varios pares de valores y noté pequeñas diferencias en los tiempos (por ejemplo, comparando un flotador de pequeña magnitud con enteros similares frente a enteros muy grandes). Aprendí sobre el caso 2^49 solo después de mirar la fuente para entender cómo funcionaba la comparación. Elegí los valores en la pregunta porque presentaban el tema de la manera más convincente.

    – Alex Riley

    13 de mayo de 2015 a las 8:23

avatar de usuario
Alex Riley

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 número flotante con un número entero porque, a diferencia de los números flotantes, los números enteros en Python pueden ser arbitrariamente grandes y siempre exactos. Tratar de convertir el entero en un flotante puede perder precisión y hacer que la comparación sea imprecisa. Intentar convertir el flotante en un entero tampoco funcionará porque se perderá cualquier parte fraccionaria.

Para solucionar este problema, Python realiza una serie de comprobaciones y devuelve 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 flotante, luego compara el exponente del flotante con la longitud del entero. Si todas estas comprobaciones fallan, es necesario construir dos nuevos objetos de Python para comparar y obtener el resultado.

Al comparar un flotador v a un entero/largo wel peor de los casos es que:

  • v y w tienen el mismo signo (ambos positivos o ambos negativos),
  • el entero w tiene suficientes bits para que se pueda sostener 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 igual al número de bits en w.

Y esto es exactamente lo que tenemos para los valores en la 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 flotante como el número de bits en el entero. Ambos números son positivos, por lo que se cumplen los cuatro criterios anteriores.

Elegir uno de los valores para que sea mayor (o menor) puede cambiar la cantidad de bits del entero o el valor del exponente, y así Python puede determinar el resultado de la comparación sin realizar la costosa verificación final.

Esto es específico de la implementación CPython del lenguaje.


La comparación con más detalle.

los float_richcompare 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 qué hace la función, por lo que los dejé donde son relevantes. También he resumido estos controles en una lista al pie de la respuesta.

La idea principal es mapear los objetos de 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 int y long tipos por separado).

Lo primero que hay que hacer es comprobar que v es definitivamente un flotador de Python y asignarlo a un doble C i. A continuación, la función analiza si w es también un flotador y lo asigna a un doble C j. Este es el mejor escenario posible 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 flotador de Python. Ahora la función comprueba si es un número 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 (devolver 0 si cero, -1 si es negativo, 1 si es positivo). Si los signos son diferentes, esta es toda 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 verificación falla, entonces v y w tener el mismo signo.

La siguiente verificación cuenta el número de bits en el número entero w. Si tiene demasiados bits, entonces no se puede sostener como un flotador y, por lo tanto, debe ser de mayor 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 número entero w tiene 48 bits o menos, se puede convertir 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;
    }

A partir de este momento, sabemos que w tiene 49 o más bits. Será conveniente tratar w como un entero positivo, 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 flotante se puede escribir (ignorando el signo) como significado * 2exponente y que el significado 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 flotante es menor que 1 (y por lo tanto menor en magnitud que cualquier número entero). O, si el exponente es menor que el número de bits en w entonces tenemos eso v < |w| ya que significación * 2exponente es menos de 2bits.

Si fallan estas dos comprobaciones, la función busca si el exponente es mayor que el número de bits en w. Esto demuestra que significancia * 2exponente es mayor que 2bits y entonces v > |w|:

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

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

La única forma en que se pueden comparar los dos valores ahora es construir dos nuevos enteros de Python a partir de v y w. La idea es descartar la parte fraccionaria de vduplique la parte entera y luego agregue uno. w también se duplica y estos dos nuevos objetos de Python se pueden comparar para dar el valor de retorno correcto. Usando un ejemplo con valores pequeños, 4.65 < 4 estaría determinada por la comparación (2*4)+1 == 9 < 8 == (2*4) (devolviendo falso).

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

Para abreviar, he omitido la verificació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 una sobrecarga adicional y explica por qué los valores resaltados en la pregunta son significativamente más lentos para comparar que otros.


Aquí hay un resumen de las comprobaciones que realiza la función de comparación.

Dejar v ser un flotador y lanzarlo como un doble C. Ahora si w es también un flotador:

  • comprobar 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 se duplica.

Si w es un entero:

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

  • (Los signos son los mismos.) Comprobar si w tiene demasiados bits para ser un flotador (más de size_t). Si es así, w tiene mayor magnitud que v.

  • Comprobar si w tiene 48 o menos bits. Si es así, puede lanzarse con seguridad a un do doble sin perder su precisión y compararse con v.

  • (w Tiene más de 48 bits. ahora vamos a tratar w como un entero positivo habiendo cambiado la operación de comparación según corresponda.)

  • Considere el exponente del flotador v. Si el exponente es negativo, entonces v es menos que 1 y por lo tanto menor que cualquier entero positivo. De lo contrario, 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 después v es mayor que w.

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

  • El cheque final. Separar v en sus partes entera y fraccionaria. Duplica la parte entera y suma 1 para compensar la parte fraccionaria. Ahora duplica el entero w. Compara estos dos nuevos enteros para obtener el resultado.

  • Desarrolladores de Python bien hechos: la mayoría de las implementaciones de lenguaje simplemente habrían solucionado el problema diciendo que las comparaciones de números enteros/flotantes no son exactas.

    – usuario253751

    5 de noviembre de 2016 a las 11:55


avatar de usuario
denfromufa

Usando gmpy2 con números enteros y flotantes de precisión arbitraria, 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

  • Todavía no he usado esta biblioteca, pero parece potencialmente muy útil. ¡Gracias!

    – Alex Riley

    16 de abril de 2016 a las 9:38

  • Es utilizado por sympy y mpmath

    – denfromufa

    16/04/2016 a las 17:43

  • CPython también tiene decimal en la biblioteca estándar

    – denfromufa

    16/04/2016 a las 21:22

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad