Pourquoi certaines comparaisons de nombres entiers sont-elles quatre fois plus lentes que d’autres?

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

La comparaison est à peu près un cauchemar

Cela est particulièrement vrai lorsque l’on compare un flottant à un entier, car, contrairement aux flottants, les entiers en Python peuvent être arbitrairement grands et toujours exacts. Essayer de convertir l’entier en flottant risque de perdre de la précision et de rendre la comparaison imprécise. Essayer de lancer le flottant sur un entier ne fonctionnera pas non plus car une partie fractionnaire sera perdue.

Pour contourner ce problème, Python effectue une série de vérifications, renvoyant le résultat si l’un des contrôles 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 flottant à la longueur de l’entier. Si toutes ces vérifications échouent, il est nécessaire de construire deux nouveaux objects Python à comparer pour obtenir le résultat.

En comparant un flottant v à un entier / long w , le pire des cas est que:

• v et w ont le même signe (à la fois positif ou négatif),
• l’entier w a assez peu de bits qu’il peut size_t dans le type size_t (typiquement 32 ou 64 bits),
• l’entier w a au moins 49 bits,
• l’exposant du flotteur v est le même que le nombre de bits de w .

Et c’est exactement ce que nous avons pour les valeurs dans 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 satisfaits.

Choisir l’une des valeurs pour qu’elle soit plus grande (ou plus petite) peut modifier le nombre de bits de l’entier ou la valeur de l’exposant, et Python peut ainsi 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 détaillée

La fonction float_richcompare gère la comparaison entre deux valeurs v et 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, alors je les ai laissés là où cela était pertinent. 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 objects Python v et w sur deux C doubles appropriés, i et 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 faire cela (le premier ne gère que long types int et long ).

La première chose à faire est de vérifier que v est définitivement un flottant Python et de le mapper sur un double C i . La fonction examine ensuite si w est aussi un flottant et le mappe à un double j C. C’est le meilleur scénario pour la fonction, car toutes les autres vérifications peuvent être ignorées. La fonction vérifie également si v est inf ou 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; } 

Maintenant, nous soaps que si w échec de ces vérifications, ce n’est pas un float Python. Maintenant, la fonction vérifie s’il s’agit d’un entier Python. Si tel est le cas, le test le plus simple consiste à extraire le signe de v et le signe de w (retourne 0 si zéro, -1 si négatif, 1 si positif). Si les signes sont différents, voici 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 échoue, alors v et w ont le même signe.

La vérification suivante compte le nombre de bits dans l'entier w . S'il a trop de bits, il ne peut pas être tenu 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; } 

Par contre, si l'entier w a 48 bits ou moins, il peut être tourné en C double j et comparé en toute sécurité:

  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 soaps que w a 49 bits ou plus. Il convient de traiter w comme un entier positif, donc changez 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 flottant. Rappelons qu’un float peut être écrit (en ignorant le signe) en tant que significand * 2 ^exposant et que le significand 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 si inférieur à tout nombre entier). Ou, si l'exposant est inférieur au nombre de bits de w alors nous avons v < |w| puisque significand * 2 ^exposant est inférieur à 2 ^nbits .

En l'absence de ces deux vérifications, la fonction recherche si l'exposant est supérieur au nombre de bits de w . Cela montre que significand * 2 ^exposant 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 soaps que l'exposant du flottant v est le même que le nombre de bits de l'entier w .

La seule façon de comparer les deux valeurs maintenant est de construire deux nouveaux entiers Python à partir de v et w . L'idée est de supprimer la partie fractionnaire de v , de doubler la partie entière, puis d'en append une. w est également doublé et ces deux nouveaux objects Python peuvent être comparés pour donner la valeur de retour correcte. En utilisant un exemple avec de petites valeurs, 4.65 < 4 serait déterminé par la comparaison (2*4)+1 == 9 < 8 == (2*4) (retourne 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 } } 

Pour faire court, j'ai omis les vérifications d’erreur supplémentaires et le suivi des ordures que Python doit effectuer lors de la création de ces nouveaux objects. Inutile de dire que cela ajoute des frais supplémentaires et explique pourquoi les valeurs mises en évidence dans la question sont beaucoup plus lentes à comparer que d’autres.

Voici un résumé des vérifications effectuées par la fonction de comparaison.

Soit v un flotteur et le transforme en double C. Maintenant, si w est aussi un float:

• Vérifiez si w est nan ou inf . Si c'est le cas, manipulez ce cas particulier séparément en fonction du type de w .

• Sinon, comparez v et w directement par leurs représentations comme C double.

Si w est un entier:

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

• ( Les signes sont les mêmes. ) Vérifiez si w a trop de bits pour être un flottant (plus que size_t ). Si oui, w a une plus grande magnitude que v .

• Vérifiez si w a 48 bits ou moins. Si tel est le cas, il peut être lancé en toute sécurité sur un double C sans perdre sa précision et comparé à v .

• ( w a plus de 48 bits. Nous allons maintenant traiter w comme un entier positif ayant changé l'op de comparaison si approprié. )

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

• Si l'exposant de v est supérieur au nombre de bits de w v est supérieur à w .

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

• Le dernier contrôle Divisez v en ses parties entières et fractionnaires. Doublez la partie entière et ajoutez 1 pour compenser la partie fractionnaire. Maintenant doublez le nombre entier w . Comparez ces deux nouveaux entiers pour obtenir le résultat.

En utilisant gmpy2 avec des flotteurs et des entiers de précision arbitraires, il est possible d’obtenir des performances de comparaison plus uniformes:

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