python3 - xrange() python 3




Pourquoi «1000000000000000 dans la plage(1000000000000001)» est-il si rapide dans Python 3? (6)

Si j'ai bien compris, la fonction range() , qui est en fait un type d'objet dans Python 3 , génère son contenu à la volée, à la manière d'un générateur.

Ceci étant le cas, je me serais attendu à ce que la ligne suivante prenne un temps démesuré, car pour déterminer si 1 quadrillion se situe dans la plage, il faudrait générer un quadrillion de valeurs:

1000000000000000 in range(1000000000000001)

De plus, il semble que peu importe le nombre de zéros ajoutés, le calcul prend plus ou moins le même temps (essentiellement instantané).

J'ai aussi essayé des choses comme ça, mais le calcul est encore presque instantané:

1000000000000000000000 in range(0,1000000000000000000001,10) # count by tens

Si j'essaie d'implémenter ma propre fonction de plage, le résultat n'est pas si bon !!

def my_crappy_range(N):
    i = 0
    while i < N:
        yield i
        i += 1
    return

Qu'est-ce que l'objet range() fait sous le capot qui le rend si rapide?

La réponse de Martijn Pieters a été choisie pour sa complétude, mais la première réponse d’abarnert est également fournie pour une bonne discussion de ce que signifie pour la range une séquence à part entière en Python 3, ainsi que quelques informations / avertissements concernant une incohérence potentielle pour l’optimisation de la fonction __contains__ Implémentations Python. L'autre réponse d'abarnert va plus en détail et fournit des liens pour ceux qui sont intéressés par l'historique de l'optimisation dans Python 3 (et le manque d'optimisation de xrange dans Python 2). Les réponses fournies par poke et par wim fournissent le code source C approprié et des explications aux personnes intéressées.


TL; DR

L'objet renvoyé par range() est en réalité un objet range . Cet objet implémente l'interface itérateur de sorte que vous puissiez parcourir ses valeurs séquentiellement, comme un générateur, mais il implémente également l'interface __contains__ , qui est en réalité appelée ce qui est appelé lorsqu'un objet apparaît à droite de l'opérateur in . La __contains__() renvoie une valeur __contains__() si l'élément est dans l'objet ou non. Les objets range connaissant leurs limites et leur foulée, il est très facile de les implémenter dans O (1).


Il s’agit d’une approche paresseuse de l’évaluation et d’une optimisation supplémentaire de la range . Les valeurs dans les plages n'ont pas besoin d'être calculées avant une utilisation réelle, voire plus loin en raison d'une optimisation supplémentaire.

Au fait, votre entier n'est pas si gros, considérez sys.maxsize

sys.maxsize in range(sys.maxsize) est assez rapide

en raison de l'optimisation - il est facile de comparer un entier donné uniquement avec les valeurs min et max.

mais:

float(sys.maxsize) in range(sys.maxsize) est assez lent .

(dans ce cas, il n'y a pas d'optimisation dans la range , donc si python reçoit un float inattendu, python comparera tous les nombres)

Vous devez être conscient des détails de la mise en œuvre mais ne pas s'y fier, car cela pourrait changer à l'avenir.


Le malentendu fondamental ici est de penser que la range est un générateur. Ce n'est pas. En fait, ce n'est pas n'importe quel type d'itérateur.

Vous pouvez dire cela assez facilement:

>>> a = range(5)
>>> print(list(a))
[0, 1, 2, 3, 4]
>>> print(list(a))
[0, 1, 2, 3, 4]

Si c’était un générateur, le réitérer une fois l’épuiserait:

>>> b = my_crappy_range(5)
>>> print(list(b))
[0, 1, 2, 3, 4]
>>> print(list(b))
[]

Ce qui est en réalité, est une séquence, tout comme une liste. Vous pouvez même tester ceci:

>>> import collections.abc
>>> isinstance(a, collections.abc.Sequence)
True

Cela signifie qu'il doit suivre toutes les règles d'être une séquence:

>>> a[3]         # indexable
3
>>> len(a)       # sized
5
>>> 3 in a       # membership
True
>>> reversed(a)  # reversible
<range_iterator at 0x101cd2360>
>>> a.index(3)   # implements 'index'
3
>>> a.count(3)   # implements 'count'
1

La différence entre une range et une list est qu'une range est une séquence paresseuse ou dynamique ; il ne se souvient pas de toutes ses valeurs, il se souvient simplement de ses start , stop et step , et crée les valeurs à la demande sur __getitem__ .

(Remarque: si vous print(iter(a)) , vous remarquerez que la range utilise le même type de listiterator que list . Comment cela fonctionne-t-il? Un listiterator n’utilise rien de particulier à propos de la list sauf le fait que il fournit une implémentation C de __getitem__ , donc ça marche aussi pour range .)

Or, rien ne dit que la Sequence.__contains__ doit être à temps constant - en fait, pour des exemples évidents de séquences comme list , ce n'est pas le cas. Mais rien ne dit que cela ne peut pas être. Et il est plus facile de mettre en oeuvre range.__contains__ pour le vérifier mathématiquement ( (val - start) % step , mais avec une complexité supplémentaire pour traiter les étapes négatives) que pour générer et tester toutes les valeurs, alors pourquoi ne pas le faire c'est la meilleure façon?

Mais rien dans le langage ne semble garantir que cela se produira. Comme le souligne Ashwini Chaudhari, si vous lui donnez une valeur non intégrale, au lieu de la convertir en entier et d'effectuer le test mathématique, il reviendra à itérer toutes les valeurs et à les comparer une par une. Et juste parce que les versions CPython 3.2+ et PyPy 3.x contiennent cette optimisation, et qu’il s’agit d’une bonne idée évidente et facile à faire, il n’ya aucune raison pour que IronPython ou NewKickAssPython 3.x ne puissent pas l’omettre. (Et en fait, CPython 3.0-3.1 ne l’a pas inclus.)

Si range était en réalité un générateur, comme my_crappy_range , alors il ne serait pas logique de tester __contains__ cette façon, ou du moins la façon dont cela a un sens ne serait pas évidente. Si vous aviez déjà itéré les 3 premières valeurs, 1 est-il toujours in le générateur? Le test pour 1 il provoquer une itération et consommer toutes les valeurs allant jusqu'à 1 (ou jusqu'à la première valeur >= 1 )?


Les autres réponses l'ont déjà bien expliqué, mais j'aimerais proposer une autre expérience illustrant la nature des objets de la plage:

>>> r = range(5)
>>> for i in r:
        print(i, 2 in r, list(r))

0 True [0, 1, 2, 3, 4]
1 True [0, 1, 2, 3, 4]
2 True [0, 1, 2, 3, 4]
3 True [0, 1, 2, 3, 4]
4 True [0, 1, 2, 3, 4]

Comme vous pouvez le constater, un objet intervalle est un objet qui se souvient de son étendue et peut être utilisé plusieurs fois (même en itérant dessus), pas seulement comme un générateur ponctuel.


Si vous vous demandez pourquoi cette optimisation a été ajoutée à la range.__contains__ et pourquoi elle n'a pas été ajoutée à xrange.__contains__ dans 2.7:

Tout d’abord, comme l’a découvert Ashwini Chaudhary, le numéro 1766304 a été ouvert pour optimiser la [x]range.__contains__ . Un correctif pour cela a été accepté et archivé pour la version 3.2 , mais n'a pas été rétroporté à la version 2.7 car "xrange s'est comporté de la sorte depuis si longtemps que je ne vois pas ce que cela nous achète de mettre à jour le correctif si tard." (2,7 était presque sorti à ce moment-là.)

Pendant ce temps:

À l'origine, xrange était un objet pas-tout-à-séquence. Comme le dit la documentation 3.1 :

Les objets Range ont très peu de comportement: ils ne supportent que l'indexation, l'itération et la fonction len .

Ce n'était pas tout à fait vrai. un objet xrange supportait en fait quelques autres choses qui viennent automatiquement avec l'indexation et len *, y compris __contains__ (via la recherche linéaire). Mais personne ne pensait que cela valait la peine de leur faire des séquences complètes à l'époque.

Ensuite, dans le cadre de la mise en œuvre du PEP des classes de base abstraites , il était important de déterminer quels types intégrés devaient être marqués comme implémentant quel ABC, et xrange / range prétend implémenter des collections.Sequence . La xrange , même si elle ne traitait toujours que le même petit comportement ". Personne n'a remarqué ce problème jusqu'au numéro 9213 . Le correctif pour ce problème a non seulement ajouté index et count à la range de 3.2, il a également retravaillé le __contains__ optimisé (qui partage le même calcul avec index et est directement utilisé par count ). ** Ce changement a également été pris en compte pour la version 3.2 et n'a pas été rétroporté à la version 2.x, car "c'est un correctif qui ajoute de nouvelles méthodes". (À ce stade, le statut 2.7 était déjà passé.)

Donc, il y avait deux chances pour que cette optimisation soit rétroportée à 2,7, mais elles ont été rejetées.

* En fait, vous obtenez même une itération gratuitement avec l'indexation seule, mais dans la version 2.3, les objets xrange ont un itérateur personnalisé.

** La première version l'a réellement réimplémentée et s'est trompée - par exemple, elle vous donnerait MyIntSubclass(2) in range(5) == False . Mais la version mise à jour du correctif de Daniel Stutzbach a restauré la majeure partie du code précédent, y compris le repli sur le générique, lent _PySequence_IterSearch qui était antérieur à la range.__contains__ 3.2 _PySequence_IterSearch utilisait implicitement lorsque l'optimisation ne s'applique pas.


Utilisez la source , Luke!

Dans CPython, range(...).__contains__ (un wrapper de méthode) finira par déléguer à un calcul simple qui vérifie si la valeur peut éventuellement être dans la plage. La raison de la vitesse ici est que nous utilisons un raisonnement mathématique sur les limites, plutôt qu'une itération directe de l'objet range . Pour expliquer la logique utilisée:

  1. Vérifiez que le nombre est compris entre start et stop , et
  2. Vérifiez que la valeur de foulée ne "dépasse" pas notre nombre.

Par exemple, 994 est dans la range(4, 1000, 2) car:

  1. 4 <= 994 < 1000 , et
  2. (994 - 4) % 2 == 0 .

Le code C complet est inclus ci-dessous, ce qui est un peu plus détaillé en raison de la gestion de la mémoire et des détails de comptage des références, mais l’idée de base est la suivante:

static int
range_contains_long(rangeobject *r, PyObject *ob)
{
    int cmp1, cmp2, cmp3;
    PyObject *tmp1 = NULL;
    PyObject *tmp2 = NULL;
    PyObject *zero = NULL;
    int result = -1;

    zero = PyLong_FromLong(0);
    if (zero == NULL) /* MemoryError in int(0) */
        goto end;

    /* Check if the value can possibly be in the range. */

    cmp1 = PyObject_RichCompareBool(r->step, zero, Py_GT);
    if (cmp1 == -1)
        goto end;
    if (cmp1 == 1) { /* positive steps: start <= ob < stop */
        cmp2 = PyObject_RichCompareBool(r->start, ob, Py_LE);
        cmp3 = PyObject_RichCompareBool(ob, r->stop, Py_LT);
    }
    else { /* negative steps: stop < ob <= start */
        cmp2 = PyObject_RichCompareBool(ob, r->start, Py_LE);
        cmp3 = PyObject_RichCompareBool(r->stop, ob, Py_LT);
    }

    if (cmp2 == -1 || cmp3 == -1) /* TypeError */
        goto end;
    if (cmp2 == 0 || cmp3 == 0) { /* ob outside of range */
        result = 0;
        goto end;
    }

    /* Check that the stride does not invalidate ob's membership. */
    tmp1 = PyNumber_Subtract(ob, r->start);
    if (tmp1 == NULL)
        goto end;
    tmp2 = PyNumber_Remainder(tmp1, r->step);
    if (tmp2 == NULL)
        goto end;
    /* result = ((int(ob) - start) % step) == 0 */
    result = PyObject_RichCompareBool(tmp2, zero, Py_EQ);
  end:
    Py_XDECREF(tmp1);
    Py_XDECREF(tmp2);
    Py_XDECREF(zero);
    return result;
}

static int
range_contains(rangeobject *r, PyObject *ob)
{
    if (PyLong_CheckExact(ob) || PyBool_Check(ob))
        return range_contains_long(r, ob);

    return (int)_PySequence_IterSearch((PyObject*)r, ob,
                                       PY_ITERSEARCH_CONTAINS);
}

La "viande" de l'idée est mentionnée dans la ligne :

/* result = ((int(ob) - start) % step) == 0 */ 

Pour range_contains , range_contains fonction range_contains au bas de l’extrait de code. Si la vérification de type exacte échoue, nous n'utilisons pas l'algorithme intelligent décrit, mais _PySequence_IterSearch plutôt dans une recherche par itération _PySequence_IterSearch de la plage à l'aide de _PySequence_IterSearch ! Vous pouvez vérifier ce comportement dans l'interpréteur (j'utilise ici la v3.5.0):

>>> x, r = 1000000000000000, range(1000000000000001)
>>> class MyInt(int):
...     pass
... 
>>> x_ = MyInt(x)
>>> x in r  # calculates immediately :) 
True
>>> x_ in r  # iterates for ages.. :( 
^\Quit (core dumped)




python-internals