Nach meinem Verständnis generiert die range()
Funktion, die in Python 3 eigentlich ein Objekttyp ist , ihren Inhalt im laufenden Betrieb, ähnlich wie ein Generator.
In diesem Fall hätte ich erwartet, dass die folgende Zeile übermäßig viel Zeit in Anspruch nimmt, da zur Bestimmung, ob 1 Billiarde im Bereich liegt, Billiardenwerte generiert werden müssten:
1000000000000000 in range(1000000000000001)
Außerdem: Es scheint, dass die Berechnung unabhängig von der Anzahl der hinzugefügten Nullen mehr oder weniger dieselbe Zeit in Anspruch nimmt (im Grunde genommen augenblicklich).
Ich habe auch solche Dinge ausprobiert, aber die Berechnung ist immer noch fast augenblicklich:
1000000000000000000000 in range(0,1000000000000000000001,10) # count by tens
Wenn ich versuche, meine eigene Bereichsfunktion zu implementieren, ist das Ergebnis nicht so schön !!
def my_crappy_range(N):
i = 0
while i < N:
yield i
i += 1
return
Was macht das range()
Objekt unter der Haube, das es so schnell macht?
Die Antwort von Martijn Pieters wurde aufgrund ihrer Vollständigkeit ausgewählt. In der ersten Antwort von abarnert finden Sie jedoch eine gute Diskussion darüber, was es bedeutet range
, eine vollwertige Sequenz in Python 3 zu sein, sowie einige Informationen / Warnungen zu möglichen Inkonsistenzen bei der __contains__
Funktionsoptimierung in Python-Implementierungen . Die andere Antwort von abarnert geht etwas detaillierter und enthält Links für diejenigen, die sich für die Geschichte der Optimierung in Python 3 (und die mangelnde Optimierung von xrange
Python 2) interessieren . Antworten von poke und von wim liefern den relevanten C-Quellcode und Erklärungen für diejenigen, die interessiert sind.
quelle
bool
oder einlong
Typ ist. Bei anderen Objekttypen wird es verrückt. Versuchen Sie mit:100000000000000.0 in range(1000000000000001)
range
das ein Generator ist?xrange
die gleiche wie Python3range
?xrange()
Objekte haben keine__contains__
Methode, daher muss die Artikelprüfung alle Artikel durchlaufen. Außerdem gibt es einige andere Veränderungenrange()
, wie es Slicing unterstützt (was wiederum ein zurückesrange
Objekt) und hat nun auchcount
undindex
Methoden , um es mit kompatibel zu machencollections.Sequence
ABC.Antworten:
Das Python 3-
range()
Objekt erzeugt nicht sofort Zahlen. Es ist ein intelligentes Sequenzobjekt , das bei Bedarf Zahlen erzeugt . Alles, was es enthält, sind Ihre Start-, Stopp- und Schrittwerte. Wenn Sie dann über das Objekt iterieren, wird bei jeder Iteration die nächste Ganzzahl berechnet.Das Objekt implementiert auch den
object.__contains__
Hook und berechnet, ob Ihre Nummer Teil seines Bereichs ist. Die Berechnung ist eine (nahezu) konstante Zeitoperation * . Es ist nie erforderlich, alle möglichen Ganzzahlen im Bereich zu durchsuchen.Aus der
range()
Objektdokumentation :range()
Zumindest würde Ihr Objekt also Folgendes tun:Hier fehlen noch einige Dinge, die ein echter
range()
unterstützt (wie die.index()
oder.count()
Methoden, Hashing, Gleichheitstests oder Slicing), aber Sie sollten eine Idee haben.Ich habe auch die
__contains__
Implementierung vereinfacht, um mich nur auf ganzzahlige Tests zu konzentrieren. Wenn Sie einem realenrange()
Objekt einen nicht ganzzahligen Wert (einschließlich Unterklassen vonint
) zuweisen, wird ein langsamer Scan gestartet, um festzustellen, ob eine Übereinstimmung vorliegt, genau wie wenn Sie einen Eindämmungstest für eine Liste aller enthaltenen Werte verwenden. Dies wurde durchgeführt, um weiterhin andere numerische Typen zu unterstützen, die nur Gleichheitstests mit Ganzzahlen unterstützen, von denen jedoch nicht erwartet wird, dass sie auch Ganzzahlarithmetik unterstützen. Siehe das ursprüngliche Python-Problem , mit dem der Containment-Test implementiert wurde.* Nahezu konstante Zeit, da Python-Ganzzahlen unbegrenzt sind und daher auch mathematische Operationen mit zunehmendem N mit der Zeit wachsen, was dies zu einer O-Operation (log N) macht. Da alles in optimiertem C-Code ausgeführt wird und Python Ganzzahlwerte in 30-Bit-Blöcken speichert, wird Ihnen der Speicher ausgehen, bevor Sie aufgrund der Größe der hier beteiligten Ganzzahlen Leistungseinbußen feststellen.
quelle
__getitem__
und haben__len__
, ist die__iter__
Implementierung tatsächlich nicht erforderlich.xrangeiterator
hinzugefügt, weil das nicht schnell genug war. Und dann irgendwo in 3.x (ich bin nicht sicher, ob es 3.0 oder 3.2 war) wurde es geworfen und sie verwenden den gleichenlistiterator
Typ, derlist
verwendet.def __init__(self, *start_stop_step)
und ihn von dort aus analysieren. Die Art und Weise, wie die Argumente jetzt beschriftet sind, ist jetzt etwas verwirrend. Trotzdem +1; Sie haben das Verhalten immer noch definitiv erklärt.range
ist älter als*args
( geschweige denn dieargclinic
API, mit der C-API-Funktionen vollständige Python-Signaturen haben). Einige andere alte Funktionen (und einige neuere Funktionen wiexrange
,slice
unditertools.islice
aus Gründen der Konsistenz) funktionieren auf die gleiche Weise, aber zum größten Teil scheinen Guido und der Rest der Kernentwickler mit Ihnen übereinzustimmen. Die 2.0+ Dokumente beschreibenrange
und Freunde sogar so, als wären sie Überladungen im C ++ - Stil, anstatt die eigentliche verwirrende Signatur anzuzeigen.argclinic
Diskussion, als Nick Coghlan einen Weg fand, um einerange
eindeutige Definition zu ermöglichen : "Bitte machen Sie es den Leuten nicht leichter, meine schlechteste Designentscheidung zu kopieren." Ich bin mir ziemlich sicher, dass er zustimmt, dass diesrange
verwirrend ist, wie geschrieben.Das grundlegende Missverständnis besteht darin, zu denken, dass
range
es sich um einen Generator handelt. Es ist nicht. Tatsächlich ist es keine Art von Iterator.Sie können dies ziemlich leicht sagen:
Wenn es ein Generator wäre, würde eine einmalige Iteration ihn erschöpfen:
Was
range
eigentlich ist, ist eine Sequenz, genau wie eine Liste. Sie können dies sogar testen:Dies bedeutet, dass alle Regeln einer Sequenz eingehalten werden müssen:
Der Unterschied zwischen a
range
und alist
besteht darin, dass arange
eine faule oder dynamische Sequenz ist; es nicht alle seine Werte erinnern, es erinnert nur seinestart
,stop
undstep
, und schafft die Werte auf Anfrage an__getitem__
.(Als Randnotiz werden Sie
print(iter(a))
feststellen, dassrange
derselbelistiterator
Typ wie verwendet wirdlist
. Wie funktioniert das? Alistiterator
verwendet nichts Besonderes,list
außer der Tatsache, dass es eine C-Implementierung von bereitstellt__getitem__
, sodass es gut funktioniertrange
zu.)Nun, es gibt nichts, was besagt, dass
Sequence.__contains__
es eine konstante Zeit sein muss - für offensichtliche Beispiele von Sequenzen wielist
ist dies nicht der Fall . Aber nichts sagt, dass es nicht sein kann. Und es ist einfacher zu implementierenrange.__contains__
, es nur mathematisch zu überprüfen ((val - start) % step
aber mit etwas mehr Komplexität, um mit negativen Schritten umzugehen), als tatsächlich alle Werte zu generieren und zu testen. Warum sollte es also nicht besser sein?Aber es scheint nichts in der Sprache zu geben, was dies garantiert . Wie Ashwini Chaudhari betont, wird, wenn Sie ihm einen nicht ganzzahligen Wert geben, anstatt ihn in eine Ganzzahl umzuwandeln und den mathematischen Test durchzuführen, alle Werte wiederholt und einzeln verglichen. Und nur weil die Versionen CPython 3.2+ und PyPy 3.x diese Optimierung enthalten und dies eine offensichtlich gute Idee ist und einfach zu bewerkstelligen ist, gibt es keinen Grund, warum IronPython oder NewKickAssPython 3.x sie nicht auslassen könnten. (Und tatsächlich hat CPython 3.0-3.1 es nicht enthalten.)
Wenn es
range
tatsächlich ein Generator wäre,my_crappy_range
wäre es nicht sinnvoll, auf__contains__
diese Weise zu testen , oder zumindest wäre es nicht offensichtlich, wie es sinnvoll ist. Wenn Sie bereits die ersten 3 Werte iteriert haben, ist dies1
immer nochin
der Generator? Sollte ein Test darauf1
führen, dass alle Werte bis1
(oder bis zum ersten Wert>= 1
) iteriert und verbraucht werden ?quelle
range
(zusammen mitlist
undtuple
) als Sequenztyp aufgeführt ist .xrange
eine Sequenz. Siehe 2.7 Dokumente . Tatsächlich war es immer eine Fast-Sequenz..__iter__()
Methode, die einen Iterator zurückgibt . Es kann wiederum nur einmal verwendet werden.range
Typen nicht überprüft werden, wenn es keine Ganzzahl ist, da es immer möglich ist,__eq__
dass ein Typ einen Typ hat , der mit kompatibel istint
. Sicher, wirdstr
offensichtlich nicht funktionieren, aber sie wollten die Dinge nicht verlangsamen, indem sie explizit alle Typen überprüften, die dort nicht vorhanden sein können (und schließlichstr
könnte eine Unterklasse überschreiben__eq__
und in der enthalten seinrange
).Nutze die Quelle , Luke!
In CPython wird
range(...).__contains__
(ein Methoden-Wrapper) schließlich an eine einfache Berechnung delegiert, die prüft, ob der Wert möglicherweise im Bereich liegen kann. Der Grund für die Geschwindigkeit hier ist, dass wir mathematische Überlegungen zu den Grenzen verwenden und nicht eine direkte Iteration des Bereichsobjekts . Um die verwendete Logik zu erklären:start
undstop
und liegtZum Beispiel
994
ist inrange(4, 1000, 2)
weil:4 <= 994 < 1000
, und(994 - 4) % 2 == 0
.Der vollständige C-Code ist unten enthalten, der aufgrund der Speicherverwaltung und der Details zur Referenzzählung etwas ausführlicher ist. Die Grundidee ist jedoch vorhanden:
Das "Fleisch" der Idee wird in der Zeile erwähnt :
Als letzte Anmerkung - sehen Sie sich die
range_contains
Funktion am unteren Rand des Code-Snippets an. Wenn die genaue Typprüfung fehlschlägt, verwenden wir nicht den beschriebenen cleveren Algorithmus, sondern greifen auf eine dumme Iterationssuche des Bereichs mit zurück_PySequence_IterSearch
! Sie können dieses Verhalten im Interpreter überprüfen (ich verwende hier v3.5.0):quelle
Um Martijns Antwort zu ergänzen, ist dies der relevante Teil der Quelle (in C, da das Bereichsobjekt in nativem Code geschrieben ist):
Für
PyLong
Objekte (int
in Python 3) wird dierange_contains_long
Funktion verwendet, um das Ergebnis zu bestimmen. Und diese Funktion prüftob
im Wesentlichen, ob sie im angegebenen Bereich liegt (obwohl sie in C etwas komplexer aussieht).Wenn es sich nicht um ein
int
Objekt handelt, wird auf die Iteration zurückgegriffen, bis der Wert gefunden wurde (oder nicht).Die gesamte Logik könnte folgendermaßen in Pseudo-Python übersetzt werden:
quelle
Wenn Sie sich fragen, warum diese Optimierung hinzugefügt
range.__contains__
wurde und warum sie in 2.7 nicht hinzugefügtxrange.__contains__
wurde:Zunächst wurde, wie Ashwini Chaudhary herausfand , die Ausgabe 1766304 explizit zur Optimierung geöffnet
[x]range.__contains__
. Ein Patch dafür wurde akzeptiert und für 3.2 eingecheckt , aber nicht auf 2.7 zurückportiert, weil "xrange sich so lange so verhalten hat, dass ich nicht sehe, was es uns bringt, den Patch so spät festzuschreiben." (2.7 war zu diesem Zeitpunkt fast aus.)Inzwischen:
Ursprünglich
xrange
war es ein nicht ganz sequenziertes Objekt. Wie die 3.1-Dokumente sagen:Das stimmte nicht ganz; ein
xrange
Objekt unterstützt tatsächlich ein paar andere Dinge , die automatisch mit Indizierung und kommenlen
, * einschließlich__contains__
(über lineare Suche). Aber niemand hielt es damals für sinnvoll, sie zu vollständigen Sequenzen zu machen.Im Rahmen der Implementierung des PEP für abstrakte Basisklassen war es dann wichtig herauszufinden, welche eingebauten Typen als Implementierung welcher ABCs markiert werden sollten und
xrange
/ oderrange
zu implementieren behauptetencollections.Sequence
, obwohl sie immer noch nur dasselbe "sehr geringe Verhalten" handhabten. Niemand bemerkte dieses Problem bis zur Ausgabe 9213 . Der Patch für dieses Problem wurde nicht nur hinzugefügtindex
undcount
zu 3.2 hinzugefügtrange
, sondern auch das optimierte überarbeitet__contains__
(das die gleiche Mathematik aufweistindex
und direkt von verwendet wirdcount
). ** Diese Änderung wurde auch für 3.2 übernommen und nicht auf 2.x zurückportiert, da "es sich um einen Bugfix handelt, der neue Methoden hinzufügt". (Zu diesem Zeitpunkt war 2.7 bereits über dem RC-Status.)Es gab also zwei Möglichkeiten, diese Optimierung auf 2,7 zurückportieren zu lassen, aber beide wurden abgelehnt.
* Tatsächlich erhalten Sie die Iteration sogar kostenlos, wenn Sie nur indizieren, aber in 2.3-
xrange
Objekten wurde ein benutzerdefinierter Iterator erstellt.** Die erste Version hat es tatsächlich neu implementiert und die Details falsch verstanden - z. B. würde es Ihnen geben
MyIntSubclass(2) in range(5) == False
. Daniel Stutzbachs aktualisierte Version des Patches stellte jedoch den größten Teil des vorherigen Codes wieder her, einschließlich des Rückgriffs auf die generische, langsame Version, die vor Version_PySequence_IterSearch
3.2range.__contains__
implizit verwendet wurde, wenn die Optimierung nicht angewendet wurde.quelle
xrange.__contains__
, es sieht so aus, als hätten sie es nicht zurück in Python 2 portiert, nur um den Benutzern ein überraschendes Element zu hinterlassen, und es war zu spät, o_O. Dercount
undindex
Patch wurde später hinzugefügt. Datei zu diesem Zeitpunkt: hg.python.org/cpython/file/d599a3f2e72d/Objects/rangeobject.c2to3
mit Hilfe von Bibliotheken wie anstelle von Dual-Version-Code migrieren würdensix
, weshalb wir solche Dinge habendict.viewkeys
, die niemand jemals benutzen wird), und das gab es auch Ein paar Änderungen, die in Version 3.2 einfach zu spät kamen, aber zum größten Teil war 2.7 eine ziemlich beeindruckende Veröffentlichung von "last 2.x ever".Die anderen Antworten haben es bereits gut erklärt, aber ich möchte ein weiteres Experiment anbieten, das die Natur von Entfernungsobjekten veranschaulicht:
Wie Sie sehen können, ist ein Bereichsobjekt ein Objekt, das sich an seinen Bereich erinnert und viele Male verwendet werden kann (auch wenn es durchlaufen wird), nicht nur ein einmaliger Generator.
quelle
Es geht um einen faulen Ansatz bei der Bewertung und eine zusätzliche Optimierung von
range
. Werte in Bereichen müssen erst bei der tatsächlichen Verwendung oder aufgrund zusätzlicher Optimierung noch weiter berechnet werden.Übrigens ist Ihre Ganzzahl nicht so groß
sys.maxsize
sys.maxsize in range(sys.maxsize)
ist ziemlich schnellAufgrund der Optimierung ist es einfach, eine bestimmte Ganzzahl nur mit der minimalen und maximalen Reichweite zu vergleichen.
aber:
Decimal(sys.maxsize) in range(sys.maxsize)
ist ziemlich langsam .(In diesem Fall gibt es keine Optimierung in
range
. Wenn Python also eine unerwartete Dezimalzahl empfängt, vergleicht Python alle Zahlen.)Sie sollten sich eines Implementierungsdetails bewusst sein, auf das Sie sich jedoch nicht verlassen sollten, da sich dies in Zukunft ändern kann.
quelle
float(sys.maxsize) != sys.maxsize)
allerdingssys.maxsize-float(sys.maxsize) == 0
.TL; DR
Das von zurückgegebene Objekt
range()
ist tatsächlich einrange
Objekt. Dieses Objekt implementiert die Iteratorschnittstelle, sodass Sie ihre Werte wie bei einem Generator, einer Liste oder einem Tupel nacheinander durchlaufen können.Es implementiert aber auch die
__contains__
Schnittstelle, die tatsächlich aufgerufen wird, wenn ein Objekt auf der rechten Seite desin
Operators angezeigt wird . Die__contains__()
Methode gibt zurück,bool
ob sich das Element auf der linken Seite desin
Objekts befindet oder nicht . Darange
Objekte ihre Grenzen und Schritte kennen, ist dies in O (1) sehr einfach zu implementieren.quelle
Nehmen Sie ein Beispiel, 997 liegt im Bereich (4, 1000, 3), weil:
4 <= 997 < 1000, and (997 - 4) % 3 == 0.
quelle
Versuchen Sie es
x-1 in (i for i in range(x))
mit großenx
Werten, bei denen ein Generatorverständnis verwendet wird, um das Aufrufen derrange.__contains__
Optimierung zu vermeiden .quelle