Je crois comprendre que la range()
fonction, qui est en fait un type d'objet en Python 3 , génère son contenu à la volée, semblable à un générateur.
Cela étant le cas, je m'attendais à ce que la ligne suivante prenne un temps excessif, 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 que j'ajoute, le calcul prend plus ou moins le même temps (essentiellement instantané).
J'ai également 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 agréable !!
def my_crappy_range(N):
i = 0
while i < N:
yield i
i += 1
return
Que fait l' range()
objet sous le capot qui le rend si rapide?
La réponse de Martijn Pieters a été choisie pour son exhaustivité, mais voir également la première réponse d'Abarnert pour une bonne discussion de ce que cela signifie pour range
être une séquence à part entière dans Python 3, et quelques informations / avertissements concernant l'incohérence potentielle pour __contains__
l'optimisation des fonctions 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
dans Python 2). Les réponses par poke et par wim fournissent le code source C pertinent et des explications pour ceux qui sont intéressés.
la source
bool
oulong
, avec d'autres types d'objets, cela deviendra fou. Essayez avec:100000000000000.0 in range(1000000000000001)
range
c'était un générateur?xrange
identique à Python3range
?xrange()
objets @Superbest n'ont pas de__contains__
méthode, donc la vérification des éléments doit parcourir tous les éléments. De plus , il y a peu d' autres changements dansrange()
, comme il prend en charge le découpage (qui retourne à nouveau unrange
objet) et maintenant aussicount
etindex
méthodes pour le rendre compatible aveccollections.Sequence
ABC.Réponses:
L'
range()
objet Python 3 ne produit pas de nombres immédiatement; c'est un objet de séquence intelligent qui produit des nombres à la demande . Il ne contient que vos valeurs de début, d'arrêt et de pas, puis lorsque vous parcourez l'objet, l'entier suivant est calculé à chaque itération.L'objet implémente également le
object.__contains__
crochet et calcule si votre numéro fait partie de sa plage. Le calcul est une opération à temps constant (presque) * . Il n'est jamais nécessaire de parcourir tous les entiers possibles de la plage.De la
range()
documentation de l' objet :Donc, au minimum, votre
range()
objet ferait:Il manque encore plusieurs éléments pris en charge par un réel
range()
(tels que les méthodes.index()
ou.count()
, le hachage, les tests d'égalité ou le découpage), mais devraient vous donner une idée.J'ai également simplifié l'
__contains__
implémentation pour me concentrer uniquement sur les tests entiers; si vous donnez à unrange()
objet réel une valeur non entière (y compris les sous-classes deint
), un balayage lent est lancé pour voir s'il existe une correspondance, tout comme si vous utilisez un test de confinement par rapport à une liste de toutes les valeurs contenues. Cela a été fait pour continuer à prendre en charge d'autres types numériques qui se trouvent juste à prendre en charge les tests d'égalité avec des entiers, mais qui ne devraient pas également prendre en charge l'arithmétique des entiers. Voir le problème Python d' origine qui implémentait le test de confinement.* Temps presque constant car les entiers Python sont illimités et donc les opérations mathématiques augmentent également dans le temps à mesure que N croît, ce qui en fait une opération O (log N). Comme tout est exécuté dans du code C optimisé et que Python stocke les valeurs entières dans des morceaux de 30 bits, vous manquerez de mémoire avant de voir un impact sur les performances en raison de la taille des entiers impliqués ici.
la source
__getitem__
et__len__
, l'__iter__
implémentation est en fait inutile.xrangeiterator
été ajoutée spécifiquement parce que ce n'était pas assez rapide. Et puis quelque part dans 3.x (je ne sais pas si c'était 3.0 ou 3.2), il a été lancé et ils utilisent le mêmelistiterator
type que celuilist
utilisé.def __init__(self, *start_stop_step)
et l'analyserais à partir de là; la façon dont les arguments sont étiquetés maintenant est maintenant un peu déroutante. Néanmoins, +1; vous avez toujours définitivement expliqué le comportement.range
est plus ancienne que*args
(et encore moins l'argclinic
API qui permet aux fonctions C-API d'avoir des signatures Python complètes). Quelques autres anciennes fonctions (et quelques fonctions plus récentes, commexrange
,slice
etitertools.islice
, pour des raisons de cohérence) fonctionnent de la même manière, mais pour la plupart, Guido et le reste des développeurs principaux semblent d'accord avec vous. Les docs 2.0+ décrivent mêmerange
et amis comme s'il s'agissait de surcharges de style C ++ plutôt que de montrer la signature réelle déroutante.argclinic
discussion, lorsque Nick Coghlan a trouvé un moyen de permettre de définirrange
sans ambiguïté: "Veuillez ne pas faciliter la copie de ma pire décision de conception." Donc, je suis presque sûr qu'il convient que celarange
prête à confusion comme écrit.Le malentendu fondamental ici est de penser que
range
c'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:
S'il s'agissait d'un générateur, l'itérer une fois l'épuiserait:
En
range
réalité, c'est une séquence, tout comme une liste. Vous pouvez même tester ceci:Cela signifie qu'il doit suivre toutes les règles d'une séquence:
La différence entre a
range
et alist
est que arange
est une séquence paresseuse ou dynamique ; il ne se rappelle pas toutes ses valeurs, il vient se souvient de sonstart
,stop
etstep
, et crée les valeurs à la demande sur__getitem__
.(Comme une note de côté, si vous
print(iter(a))
, vous remarquerez que lesrange
utilisations du mêmelistiterator
type quelist
. Comment ça marche? Alistiterator
ne pas utiliser quoi que ce soit de spécial ,list
sauf pour le fait qu'il fournit une implémentation C__getitem__
, il fonctionne très bien pourrange
aussi.)Maintenant, rien ne dit que le temps
Sequence.__contains__
doit être constant - en fait, pour des exemples évidents de séquences commelist
, ce n'est pas le cas. Mais rien ne dit que cela ne peut pas être. Et il est plus facile à implémenterrange.__contains__
de simplement le vérifier mathématiquement ((val - start) % step
, mais avec une complexité supplémentaire pour gérer les étapes négatives) que de générer et de tester réellement toutes les valeurs, alors pourquoi ne le ferait-il pas mieux?Mais il ne semble pas y avoir quoi que ce soit dans la langue qui garantisse 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 de faire le test mathématique, cela 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 c'est une bonne idée évidente et facile à faire, il n'y a aucune raison pour qu'IronPython ou NewKickAssPython 3.x ne puissent pas le laisser de côté. (Et en fait, CPython 3.0-3.1 ne l'a pas inclus.)
Si en
range
fait, c'était un générateur,my_crappy_range
alors ça n'aurait pas de sens de tester de__contains__
cette façon, ou du moins la façon dont ça aurait du sens ne serait pas évidente. Si vous avez déjà répété les 3 premières valeurs, est-ce1
toujoursin
le générateur? Le test doit-1
il le faire itérer et consommer toutes les valeurs jusqu'à1
(ou jusqu'à la première valeur>= 1
)?la source
range
est répertorié (aveclist
ettuple
) comme type de séquence .xrange
c'est aussi une séquence. Voir 2.7 documents . En fait, c'était toujours une quasi-séquence..__iter__()
méthode qui retournera un itérateur. Il ne peut à son tour être utilisé qu'une seule fois.range
ne vérifie pas les types quand ce n'est pas un entier, car il est toujours possible qu'un type ait un__eq__
qui est compatible avecint
. Bien sûr,str
cela ne fonctionnera évidemment pas, mais ils ne voulaient pas ralentir les choses en vérifiant explicitement tous les types qui ne peuvent pas y être (et après tout, unestr
sous - classe pourrait remplacer__eq__
et être contenue dans lerange
).Utilisez la source , Luke!
En 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 plage . Pour expliquer la logique utilisée:start
etstop
, etPar exemple,
994
c'estrange(4, 1000, 2)
parce que:4 <= 994 < 1000
, et(994 - 4) % 2 == 0
.Le code C complet est inclus ci-dessous, ce qui est un peu plus détaillé à cause 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à:
La "viande" de l'idée est mentionnée dans la ligne :
Pour terminer, regardez la
range_contains
fonction en bas de l'extrait de code. Si la vérification de type exacte échoue, nous n'utilisons pas l'algorithme intelligent décrit, mais nous retombons à 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 ici la v3.5.0):la source
Pour ajouter à la réponse de Martijn, ceci est la partie pertinente de la source (en C, car l'objet range est écrit en code natif):
Donc, pour les
PyLong
objets (qui estint
en Python 3), il utilisera larange_contains_long
fonction pour déterminer le résultat. Et cette fonction vérifie essentiellement si seob
trouve dans la plage spécifiée (bien qu'elle semble un peu plus complexe en C).S'il ne s'agit pas d'un
int
objet, il revient à l'itération jusqu'à ce qu'il trouve la valeur (ou non).Toute la logique pourrait être traduite en pseudo-Python comme ceci:
la source
Si vous vous demandez pourquoi cette optimisation a été ajoutée
range.__contains__
et pourquoi elle n'a pas été ajoutéexrange.__contains__
en 2.7:Tout d'abord, comme Ashwini Chaudhary l'a découvert, le problème 1766304 a été ouvert explicitement pour être optimisé
[x]range.__contains__
. Un correctif a été accepté et archivé pour la version 3.2 , mais il n'a pas été rétroporté vers la version 2.7 car "xrange s'est comporté comme ça depuis si longtemps que je ne vois pas ce qu'il nous achète pour valider le correctif si tard." (2.7 était presque sorti à ce moment-là.)Pendant ce temps:
À l'origine,
xrange
était un objet pas tout à fait séquence. Comme le disent les documents 3.1 :Ce n'était pas tout à fait vrai; un
xrange
objet a en fait pris en charge quelques autres choses qui viennent automatiquement avec l'indexation etlen
, * y compris__contains__
(via la recherche linéaire). Mais personne ne pensait qu'il valait la peine d'en 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 devraient être marqués comme implémentant quels ABC et
xrange
/ ourange
prétendaient implémentercollections.Sequence
, même s'il ne traitait toujours que le même "très petit comportement". Personne n'a remarqué ce problème jusqu'au numéro 9213 . Le patch pour cette question non seulement ajoutéindex
etcount
à 3,2 derange
, il a également retravaillé l'optimisation__contains__
(qui partage le même calcul avecindex
, et est directement utilisé parcount
). ** Cette modification est également entrée dans la version 3.2 et n'a pas été rétroportée vers 2.x, car "c'est un correctif qui ajoute de nouvelles méthodes". (À ce stade, 2.7 avait déjà dépassé le statut rc.)Il y avait donc deux chances d'obtenir cette optimisation rétroportée à 2,7, mais elles ont toutes deux été rejetées.
* En fait, vous obtenez même l'itération gratuitement avec l'indexation seule, mais dans 2.3 les
xrange
objets ont un itérateur personnalisé.** La première version l'a en fait réimplémentée et s'est trompée de détails — par exemple, elle vous donnerait
MyIntSubclass(2) in range(5) == False
. Mais la version mise à jour de Daniel Stutzbach du correctif a restauré la plupart du code précédent, y compris le retour au générique, lent_PySequence_IterSearch
que la version antérieure à 3.2range.__contains__
utilisait implicitement lorsque l'optimisation ne s'appliquait pas.la source
xrange.__contains__
, il semble qu'ils ne l'ont pas rétroporté sur Python 2 juste pour laisser un élément de surprise aux utilisateurs et il était trop tard o_O. Le patchcount
et a été ajouté plus tard. Fichier à ce moment: hg.python.org/cpython/file/d599a3f2e72d/Objects/rangeobject.cindex
2to3
au lieu de via le code à double version avec l'aide de bibliothèques commesix
, c'est pourquoi nous avons obtenu des choses commedict.viewkeys
ça que personne n'utilisera jamais), et il y avait quelques changements qui sont venus trop tard dans la 3.2, mais la plupart du temps la 2.7 était une version "2.x 2. jamais" assez impressionnante.Les autres réponses l'ont déjà bien expliqué, mais je voudrais proposer une autre expérience illustrant la nature des objets de la gamme:
Comme vous pouvez le voir, un objet de plage est un objet qui se souvient de sa plage et peut être utilisé plusieurs fois (même en itérant dessus), pas seulement un générateur ponctuel.
la source
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 davantage en raison d'une optimisation supplémentaire.Soit dit en passant, votre entier n'est pas si grand, considérez
sys.maxsize
sys.maxsize in range(sys.maxsize)
est assez rapideen raison de l'optimisation - il est facile de comparer un entier donné uniquement avec le min et le max de la plage.
mais:
Decimal(sys.maxsize) in range(sys.maxsize)
est assez lent .(dans ce cas, il n'y a pas d'optimisation dans
range
, donc si python reçoit Decimal inattendu, python comparera tous les nombres)Vous devez être au courant d'un détail d'implémentation, mais vous ne devez pas vous y fier, car cela pourrait changer à l'avenir.
la source
float(sys.maxsize) != sys.maxsize)
cependantsys.maxsize-float(sys.maxsize) == 0
.TL; DR
L'objet retourné par
range()
est en fait unrange
objet. Cet objet implémente l'interface de l'itérateur afin que vous puissiez parcourir ses valeurs séquentiellement, tout comme un générateur, une liste ou un tuple.Mais il implémente également l'
__contains__
interface qui est en fait ce qui est appelé lorsqu'un objet apparaît sur le côté droit de l'in
opérateur. La__contains__()
méthode renvoie unbool
élément indiquant si l'élément du côté gauche dein
l'objet se trouve ou non dans l'objet. Puisque lesrange
objets connaissent leurs limites et leur foulée, c'est très facile à implémenter dans O (1).la source
Prenons un exemple, 997 est dans la plage (4, 1000, 3) parce que:
4 <= 997 < 1000, and (997 - 4) % 3 == 0.
la source
Essayez
x-1 in (i for i in range(x))
de grandesx
valeurs, qui utilisent une compréhension du générateur pour éviter d'appeler l'range.__contains__
optimisation.la source