Pourquoi certaines comparaisons float <integer sont-elles quatre fois plus lentes que d'autres?

Lorsque vous comparez des flottants à des nombres entiers, certaines paires de valeurs prennent beaucoup plus de temps à être évaluées que d'autres valeurs de même ampleur.

Par exemple:

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

Mais si le flottant ou l'entier est réduit ou agrandi d'une certaine quantité, la comparaison s'exécute beaucoup plus rapidement:

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

Changer l'opérateur de comparaison (par exemple en utilisant ==ou à la >place) n'affecte pas les temps de manière notable.

Ce n'est pas uniquement lié à la magnitude, car choisir des valeurs plus grandes ou plus petites peut entraîner des comparaisons plus rapides, donc je soupçonne que cela est dû à une façon malheureuse que les bits s'alignent.

De toute évidence, la comparaison de ces valeurs est plus que suffisamment rapide pour la plupart des cas d'utilisation. Je suis simplement curieux de savoir pourquoi Python semble lutter plus avec certaines paires de valeurs qu'avec d'autres.

Un commentaire dans le code source Python pour les objets flottants reconnaît que:

La comparaison est à peu près un cauchemar

Cela est particulièrement vrai lors de la comparaison d'un flottant à un entier, car, contrairement aux flottants, les entiers en Python peuvent être arbitrairement grands et sont toujours exacts. Essayer de convertir l'entier en un flottant peut perdre en précision et rendre la comparaison inexacte. Essayer de convertir le flotteur en un entier ne fonctionnera pas non plus car toute partie fractionnaire sera perdue.

Pour contourner ce problème, Python effectue une série de vérifications, renvoyant le résultat si l'une des vérifications réussit. Il compare les signes des deux valeurs, puis si l'entier est "trop ​​grand" pour être un flottant, puis compare l'exposant du flotteur à la longueur de l'entier. Si toutes ces vérifications échouent, il est nécessaire de construire deux nouveaux objets Python à comparer afin d'obtenir le résultat.

Lorsque l'on compare un flottant và un entier / long w, le pire des cas est que:

• vet wavoir le même signe (positif ou négatif),
• l'entier wa assez peu de bits pour pouvoir être contenu dans le size_ttype (typiquement 32 ou 64 bits),
• l'entier wa au moins 49 bits,
• l'exposant du flottant vest le même que le nombre de bits w.

Et c'est exactement ce que nous avons pour les valeurs de la question:

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

Nous voyons que 49 est à la fois l'exposant du flottant et le nombre de bits dans l'entier. Les deux chiffres sont positifs et les quatre critères ci-dessus sont donc remplis.

Choisir une des valeurs pour être plus grande (ou plus petite) peut changer le nombre de bits de l'entier, ou la valeur de l'exposant, et ainsi Python est capable de déterminer le résultat de la comparaison sans effectuer la vérification finale coûteuse.

Ceci est spécifique à l'implémentation CPython du langage.

La comparaison plus en détail

La float_richcomparefonction gère la comparaison entre deux valeurs vet w.

Vous trouverez ci-dessous une description pas à pas des contrôles effectués par la fonction. Les commentaires dans la source Python sont en fait très utiles lorsque vous essayez de comprendre ce que fait la fonction, je les ai donc laissés là où ils sont pertinents. J'ai également résumé ces vérifications dans une liste au bas de la réponse.

L'idée principale est de mapper les objets Python vet wdeux C doubles appropriés, iet j, qui peuvent ensuite être facilement comparés pour donner le résultat correct. Python 2 et Python 3 utilisent les mêmes idées pour ce faire (l'ancien ne gère intet ne longtape que séparément).

La première chose à faire est de vérifier que vest sans aucun doute un flotteur Python et la carte à un C à double i. Suivant la fonction examine si west aussi un flotteur et cartes à C doubles j. Il s'agit du meilleur scénario pour la fonction, car toutes les autres vérifications peuvent être ignorées. La fonction vérifie également si vest infou 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;
    }

Nous savons maintenant que si wces vérifications ont échoué, ce n'est pas un flotteur Python. Maintenant, la fonction vérifie s'il s'agit d'un entier Python. Si tel est le cas, le test le plus simple est d'extraire le signe de vet le signe de w(retourner 0si zéro, -1si négatif, 1si positif). Si les signes sont différents, ce sont toutes les informations nécessaires pour retourner le résultat de la comparaison:

    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 cette vérification a échoué, alors vet wportez le même signe.

La vérification suivante compte le nombre de bits dans l'entier w. S'il contient trop de bits, il ne peut pas être considéré comme un flottant et doit donc être plus grand que le flotteur 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'un autre côté, si l'entier wa 48 bits ou moins, il peut en toute sécurité être transformé en double C jet comparé:

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

À partir de ce moment, nous savons qu'il wa 49 bits ou plus. Il sera commode de traiter wcomme un entier positif, changez donc le signe et l'opérateur de comparaison si nécessaire:

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

Maintenant, la fonction regarde l'exposant du flotteur. Rappelons qu'un flottant peut s'écrire (signe ignorant) comme ^{exposant de} significande * 2 et que la significande représente un nombre compris entre 0,5 et 1:

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

Cela vérifie deux choses. Si l'exposant est inférieur à 0, le flottant est inférieur à 1 (et donc plus petit que n'importe quel entier). Ou, si l'exposant est inférieur au nombre de bits, walors nous avons cela v < |w|puisque l' ^exposant significand * 2 est inférieur à 2 ^nbits .

A défaut de ces deux vérifications, la fonction cherche à voir si l'exposant est supérieur au nombre de bits w. Cela montre que l' ^exposant significand * 2 est supérieur à 2 ^nbits et donc v > |w|:

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

Si cette vérification n'a pas réussi, nous savons que l'exposant du flottant vest le même que le nombre de bits dans l'entier w.

La seule façon de comparer les deux valeurs maintenant est de construire deux nouveaux entiers Python à partir de vet w. L'idée est de supprimer la partie fractionnaire de v, de doubler la partie entière, puis d'en ajouter une. west également doublé et ces deux nouveaux objets Python peuvent être comparés pour donner la valeur de retour correcte. L'utilisation d'un exemple avec de petites valeurs 4.65 < 4serait déterminée par la comparaison (2*4)+1 == 9 < 8 == (2*4)(retour faux).

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

Par souci de concision, j'ai omis la vérification d'erreur supplémentaire et le suivi des ordures que Python doit faire lorsqu'il crée ces nouveaux objets. Il va sans dire que cela ajoute des frais généraux supplémentaires et explique pourquoi les valeurs mises en évidence dans la question sont beaucoup plus lentes à comparer que les autres.

Voici un résumé des contrôles effectués par la fonction de comparaison.

Soit vun flotteur et lancez-le comme un double C. Maintenant, si west également un flotteur:

• Vérifiez si west nanou inf. Si c'est le cas, manipulez ce cas spécial séparément en fonction du type de w.

• Sinon, comparez vet wdirectement par leurs représentations comme C doubles.

Si west un entier:

• Extraire les signes de vet w. S'ils sont différents, alors nous savons vet wsommes différents et quelle est la plus grande valeur.

• ( Les signes sont les mêmes. ) Vérifiez s'il y wa trop de bits pour être un flottant (plus que size_t). Si oui, wa une magnitude supérieure à v.

• Vérifiez s'il wa 48 bits ou moins. Si c'est le cas, il peut être coulé en toute sécurité dans un double C sans perdre sa précision et par rapport à v.

• ( wa plus de 48 bits. Nous allons maintenant traiter wcomme un entier positif ayant changé l'op de comparaison comme il convient. )

• Considérez l'exposant du flotteur v. Si l'exposant est négatif, il vest alors inférieur 1et donc inférieur à tout entier positif. Sinon, si l'exposant est inférieur au nombre de bits, wil doit être inférieur à w.

• Si l'exposant de vest supérieur au nombre de bits, walors vest supérieur à w.

• ( L'exposant est le même que le nombre de bits w. )

• Le contrôle final. Divisé ven ses parties entières et fractionnaires. Doublez la partie entière et ajoutez 1 pour compenser la partie fractionnaire. Maintenant, doublez l'entier w. Comparez plutôt ces deux nouveaux entiers pour obtenir le résultat.

Utilisation gmpy2de flotteurs de précision arbitraires et des entiers , il est possible d'obtenir une comparaison plus uniforme performance:

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