Question Pourquoi "1000000000000000 dans la gamme (1000000000000001)" si vite dans Python 3?


Je crois comprendre que le range() fonction, qui est en fait un type d'objet dans Python 3, génère son contenu à la volée, similaire à un générateur.

Ceci étant le cas, je m'attendais à ce que la ligne suivante prenne énormément de temps, car pour déterminer si 1 quadrillion est 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 range, le résultat n'est pas si joli !!

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

Quel est le range() objet faisant sous le capot qui le rend si vite?


La réponse de Martijn Pieters a été choisi pour son exhaustivité, mais aussi voir première réponse d'abarnert pour une bonne discussion de ce que cela signifie pour range être un véritable séquence dans Python 3, et quelques informations / avertissements concernant les incohérences potentielles __contains__ optimisation de la fonction dans les implémentations Python. L'autre réponse d'abarnert va plus en détail et fournit des liens pour ceux qui s'intéressent à l'histoire derrière l'optimisation dans Python 3 (et le manque d'optimisation de xrange en Python 2). Réponses par poke et par wim fournir le code source C approprié et des explications pour ceux qui sont intéressés.


1364
2018-05-06 15:32


origine


Réponses:


Le Python 3 range() l'objet ne produit pas de nombres immédiatement; c'est un objet de séquence intelligent qui produit des nombres à la demande. Tout ce qu'il contient est vos valeurs de début, d'arrêt et d'étape, puis, lorsque vous parcourez l'objet, l'entier suivant est calculé à chaque itération.

L'objet met également en œuvre le object.__contains__ crochet, et calcule si votre numéro fait partie de sa gamme. Le calcul est une opération à temps constant O (1). Il n'est jamais nécessaire de parcourir tous les entiers possibles de la plage.

Du range() documentation de l'objet:

L'avantage de la range tapez sur une régulière list ou tuple est qu'un objet range prendra toujours la même (petite) quantité de mémoire, quelle que soit la taille de la plage qu'il représente (car il ne stocke que start, stop et step valeurs, calcul des éléments individuels et des sous-limites si nécessaire).

Donc, au minimum, votre range() objet ferait:

class my_range(object):
    def __init__(self, start, stop=None, step=1):
        if stop is None:
            start, stop = 0, start
        self.start, self.stop, self.step = start, stop, step
        if step < 0:
            lo, hi = stop, start
        else:
            lo, hi = start, stop
        self.length = ((hi - lo - 1) // abs(step)) + 1

    def __iter__(self):
        current = self.start
        if self.step < 0:
            while current > self.stop:
                yield current
                current += self.step
        else:
            while current < self.stop:
                yield current
                current += self.step

    def __len__(self):
        return self.length

    def __getitem__(self, i):
        if i < 0:
            i += self.length
        if 0 <= i < self.length:
            return self.start + i * self.step
        raise IndexError('Index out of range: {}'.format(i))

    def __contains__(self, num):
        if self.step < 0:
            if not (self.stop < num <= self.start):
                return False
        else:
            if not (self.start <= num < self.stop):
                return False
        return (num - self.start) % self.step == 0

Il manque encore plusieurs choses qu'un vrai range() supports (tels que .index() ou .count() méthodes, hachage, tests d'égalité ou tranchage), mais devrait vous donner une idée.

J'ai aussi simplifié le __contains__ implémentation pour se concentrer uniquement sur des tests entiers; si vous donnez un réel range() objecter une valeur non entière (y compris les sous-classes de int), un balayage lent est lancé pour voir s'il y a une correspondance, tout comme si vous utilisiez un test de confinement sur une liste de toutes les valeurs contenues. Cela a été fait pour continuer à prendre en charge d'autres types numériques qui prennent en charge les tests d'égalité avec des entiers, mais qui ne sont pas supposés prendre en charge l'arithmétique des nombres entiers. Voir l'original Problème Python qui a mis en œuvre le test de confinement.


1351
2018-05-06 15:33



Le malentendu fondamental ici est en pensant que range est un générateur. Ce n'est pas. En fait, ce n'est pas une sorte d'itérateur.

Vous pouvez le dire 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, l'itérer une fois l'épuiserait:

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

Quelle range est en fait, 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 un range et un list est-ce un range est un paresseux ou dynamique séquence; il ne se souvient pas de toutes ses valeurs, il se souvient juste de start, stop, et stepet crée les valeurs à la demande __getitem__.

(En note, si vous print(iter(a)), vous remarquerez que range utilise le même listiterator tapez comme list. Comment ça marche? UNE listiterator n'utilise rien de spécial à propos de list sauf pour le fait qu'il fournit une mise en œuvre C de __getitem__, donc ça marche bien pour range aussi.)


Maintenant, il n'y a rien qui dit que Sequence.__contains__ doit être le temps constant, en fait, pour des exemples évidents de séquences comme list, ce n'est pas. Mais il n'y a rien qui le dit ne peut pas être. Et c'est plus facile à mettre en œuvre range.__contains__ juste vérifier mathématiquement ((val - start) % step, mais avec une complexité supplémentaire pour gérer les étapes négatives) que pour générer et tester toutes les valeurs, alors pourquoi ne devrait pas le fait le mieux?

Mais il ne semble pas y avoir quelque chose dans la langue garanties Cela arrivera. Comme le souligne Ashwini Chaudhari, si vous lui donnez une valeur non-intégrale, au lieu de convertir en nombre entier et de faire le test mathématique, il retombera pour itérer toutes les valeurs et les comparer une par une. Et juste parce que les versions de CPython 3.2+ et de PyPy 3.x contiennent cette optimisation, et c'est une bonne idée évidente et facile à faire, il n'y a aucune raison que IronPython ou NewKickAssPython 3.x ne puisse pas l'ignorer. (Et en fait, CPython 3.0-3.1 n'a pas incluez-le.)


Si range en fait étaient un générateur, comme my_crappy_range, alors il ne serait pas logique de tester __contains__ De cette façon, ou du moins la façon dont cela a du sens ne serait pas évidente. Si vous aviez déjà répété les trois premières valeurs, 1 encore in le générateur? Devrait tester pour 1 le provoquer à itérer et consommer toutes les valeurs jusqu'à 1 (ou jusqu'à la première valeur >= 1)?


561
2018-05-06 16:01



Utilisez le la sourceLuke!

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 raisonnement mathématique sur les limites, plutôt que d'une itération directe de l'objet de gamme. Pour expliquer la logique utilisée:

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

Par exemple, 994 est dans 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 verbeux 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 là:

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 */ 

En conclusion, regardez le range_contains fonction 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 retombons dans une recherche d'itération stupide de la plage en utilisant _PySequence_IterSearch! Vous pouvez vérifier ce comportement dans l'interpréteur (j'utilise la version 3.5.0 ici):

>>> 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)

285
2018-05-06 15:41



Pour ajouter à la réponse de Martijn, c'est la partie pertinente de la source (en C, comme l'objet range est écrit en code natif):

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

Donc pour PyLong objets (qui est int en Python 3), il utilisera le range_contains_long fonction pour déterminer le résultat. Et cette fonction vérifie essentiellement si ob est dans la gamme spécifiée (bien que cela semble un peu plus complexe en C).

Si ce n'est pas un int objet, il revient à itérer jusqu'à ce qu'il trouve la valeur (ou non).

Toute la logique pourrait être traduite en pseudo-Python comme ceci:

def range_contains (rangeObj, obj):
    if isinstance(obj, int):
        return range_contains_long(rangeObj, obj)

    # default logic by iterating
    return any(obj == x for x in rangeObj)

def range_contains_long (r, num):
    if r.step > 0:
        # positive step: r.start <= num < r.stop
        cmp2 = r.start <= num
        cmp3 = num < r.stop
    else:
        # negative step: r.start >= num > r.stop
        cmp2 = num <= r.start
        cmp3 = r.stop < num

    # outside of the range boundaries
    if not cmp2 or not cmp3:
        return False

    # num must be on a valid step inside the boundaries
    return (num - r.start) % r.step == 0

106
2018-05-06 15:41



Si vous vous demandez Pourquoi cette optimisation a été ajoutée à range.__contains__et pourquoi n'était pas ajouté à xrange.__contains__ en 2.7:

Tout d'abord, comme l'a découvert Ashwini Chaudhary, numéro 1766304 a été ouvert explicitement pour optimiser [x]range.__contains__. Un patch pour cela était accepté et vérifié pour 3.2, mais pas rétroporté à 2.7 parce que "xrange s'est comporté comme ça pendant si longtemps que je ne vois pas ce qu'il nous achète pour commettre le patch si tard." (2,7 était presque sorti à ce moment-là.)

Pendant ce temps:

Initialement, xrange était un objet pas tout à fait séquence. Comme les docs 3.1 dire:

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

Ce n'était pas tout à fait vrai. un xrange objet effectivement pris en charge un certain nombre d'autres choses qui viennent automatiquement avec l'indexation et len,* comprenant __contains__ (via une recherche linéaire). Mais personne ne pensait que cela valait la peine de leur faire des séquences complètes à ce moment-là.

Ensuite, dans le cadre de la mise en œuvre du Classes de base abstraites PEP, il était important de comprendre quels types d'architecture devraient être marqués comme mettant en œuvre quel ABC, et xrange/range prétendait mettre en œuvre collections.Sequence, même si elle ne traitait toujours que le "très petit comportement". Personne n'a remarqué ce problème jusqu'à numéro 9213. Le correctif pour ce problème non seulement ajouté index et count à 3.2 range, il a également retravaillé les optimisés __contains__ (qui partage le même calcul avec index, et est directement utilisé par count).**  Ce changement est également passé à 3.2, et n'a pas été rétroporté à 2.x, car «c'est un correctif qui ajoute de nouvelles méthodes». (À ce stade, 2,7 était déjà passé le statut rc.)

Donc, il y avait deux chances d'obtenir cette optimisation rétroportée à 2,7, mais ils ont tous deux été rejetés.


* En fait, vous obtenez même l'itération gratuitement avec len et l'indexation, mais en 2.3  xrange objets ont un itérateur personnalisé. Ce qu'ils ont ensuite perdu en 3.x, qui utilise le même listiterator tapez comme list.

** La première version l'a effectivement réimplémentée, et les détails ont été faux - par exemple, cela vous donnerait MyIntSubclass(2) in range(5) == False. Mais la version mise à jour de Daniel Stutzbach du patch restauré la plupart du code précédent, y compris le repli sur le générique, lent _PySequence_IterSearch ce pré-3.2 range.__contains__ était implicitement utilisé lorsque l'optimisation ne s'applique pas.


79
2018-05-06 21:42



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

>>> 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 voir, un objet range est un objet qui se souvient de sa portée et peut être utilisé plusieurs fois (même en itérant dessus), pas seulement un générateur unique.


35
2018-05-06 16:04



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

D'ailleurs, votre nombre entier n'est pas si grand, considérez sys.maxsize

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

en raison de l'optimisation - il est facile de comparer l'entier donné juste avec min et max de gamme.

mais:

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

(dans ce cas, il n'y a pas d'optimisation dans range, donc depuis recevoir un flottement inattendu, python va comparer tous les nombres)


3
2018-03-16 10:47