Warum ist "1000000000000000 in Reichweite (1000000000000001)" in Python 3 so schnell?

2115

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 xrangePython 2) interessieren . Antworten von poke und von wim liefern den relevanten C-Quellcode und Erklärungen für diejenigen, die interessiert sind.

Rick unterstützt Monica
quelle
70
Beachten Sie, dass dies nur dann der Fall ist, wenn das Element, das wir überprüfen, ein booloder ein longTyp ist. Bei anderen Objekttypen wird es verrückt. Versuchen Sie mit:100000000000000.0 in range(1000000000000001)
Ashwini Chaudhary
10
Wer hat dir gesagt, dass rangedas ein Generator ist?
Abarnert
7
@abarnert Ich denke, die Bearbeitung, die ich vorgenommen habe, hat die Verwirrung intakt gelassen.
Rick unterstützt Monica
5
@AshwiniChaudhary ist nicht Python2 xrangedie gleiche wie Python3range ?
Superbest
28
@ Superbest- xrange()Objekte haben keine __contains__Methode, daher muss die Artikelprüfung alle Artikel durchlaufen. Außerdem gibt es einige andere Veränderungen range(), wie es Slicing unterstützt (was wiederum ein zurückes rangeObjekt) und hat nun auch countund indexMethoden , um es mit kompatibel zu machen collections.SequenceABC.
Ashwini Chaudhary

Antworten:

2170

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 :

Der Vorteil des rangeTyps über einen regulären listoder tupleist , dass ein Kreisobjekt die gleiche (kleine) Menge an Speichern immer nehmen, unabhängig von der Größe des Bereichs stellt es (wie es nur die speichert start, stopund stepWerte, einzelne Elemente und Unterbereiche Berechnung wie benötigt).

range()Zumindest würde Ihr Objekt also Folgendes tun:

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, step = stop, start, -step
        else:
            lo, hi = start, stop
        self.length = 0 if lo > hi else ((hi - lo - 1) // 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

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 realen range()Objekt einen nicht ganzzahligen Wert (einschließlich Unterklassen von int) 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.

Martijn Pieters
quelle
58
Unterhaltsame Tatsache: Da Sie eine funktionierende Implementierung von __getitem__und haben __len__, ist die __iter__Implementierung tatsächlich nicht erforderlich.
Lucretiel
2
@Lucretiel: In Python 2.3 wurde speziell ein Special xrangeiteratorhinzugefü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 gleichen listiteratorTyp, der listverwendet.
Abarnert
1
Ich würde den Konstruktor als definieren 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.
Cody Piersall
1
@CodyPiersall: Leider ist das die Signatur des Initialisierers der realen Klasse. rangeist älter als *args( geschweige denn die argclinicAPI, mit der C-API-Funktionen vollständige Python-Signaturen haben). Einige andere alte Funktionen (und einige neuere Funktionen wie xrange, sliceund itertools.isliceaus 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 beschreiben rangeund Freunde sogar so, als wären sie Überladungen im C ++ - Stil, anstatt die eigentliche verwirrende Signatur anzuzeigen.
abarnert
2
@CodyPiersall: Eigentlich ist hier ein Zitat von Guido aus der argclinicDiskussion, als Nick Coghlan einen Weg fand, um eine rangeeindeutige 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 dies rangeverwirrend ist, wie geschrieben.
Abarnert
844

Das grundlegende Missverständnis besteht darin, zu denken, dass rangees sich um einen Generator handelt. Es ist nicht. Tatsächlich ist es keine Art von Iterator.

Sie können dies ziemlich leicht sagen:

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

Wenn es ein Generator wäre, würde eine einmalige Iteration ihn erschöpfen:

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

Was rangeeigentlich ist, ist eine Sequenz, genau wie eine Liste. Sie können dies sogar testen:

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

Dies bedeutet, dass alle Regeln einer Sequenz eingehalten werden müssen:

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

Der Unterschied zwischen a rangeund a listbesteht darin, dass a rangeeine faule oder dynamische Sequenz ist; es nicht alle seine Werte erinnern, es erinnert nur seine start, stopund step, und schafft die Werte auf Anfrage an __getitem__.

(Als Randnotiz werden Sie print(iter(a))feststellen, dass rangederselbe listiteratorTyp wie verwendet wird list. Wie funktioniert das? A listiteratorverwendet nichts Besonderes, listaußer der Tatsache, dass es eine C-Implementierung von bereitstellt __getitem__, sodass es gut funktioniert rangezu.)


Nun, es gibt nichts, was besagt, dass Sequence.__contains__es eine konstante Zeit sein muss - für offensichtliche Beispiele von Sequenzen wie listist dies nicht der Fall . Aber nichts sagt, dass es nicht sein kann. Und es ist einfacher zu implementieren range.__contains__, es nur mathematisch zu überprüfen ( (val - start) % stepaber 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 rangetatsächlich ein Generator wäre, my_crappy_rangewä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 dies 1immer noch inder Generator? Sollte ein Test darauf 1führen, dass alle Werte bis 1(oder bis zum ersten Wert >= 1) iteriert und verbraucht werden ?

abarnert
quelle
10
Dies ist eine ziemlich wichtige Sache, um klar zu kommen. Ich nehme an, die Unterschiede zwischen Python 2 und 3 haben zu meiner Verwirrung in diesem Punkt geführt. Auf jeden Fall hätte ich feststellen sollen, dass da range(zusammen mit listund tuple) als Sequenztyp aufgeführt ist .
Rick unterstützt Monica
4
@ RickTeachey: Eigentlich ist in 2.6+ (ich denke; vielleicht 2.5+) auch xrangeeine Sequenz. Siehe 2.7 Dokumente . Tatsächlich war es immer eine Fast-Sequenz.
Abarnert
5
@ RickTeachey: Eigentlich habe ich mich geirrt; In 2.6-2.7 (und 3.0-3.1) behauptet es, eine Sequenz zu sein, aber es ist immer noch nur eine Fast-Sequenz. Siehe meine andere Antwort.
Abarnert
2
Es ist kein Iterator, es ist eine Sequenz (Iterable in Bezug auf Java, IEnumerable von C #) - etwas mit einer .__iter__()Methode, die einen Iterator zurückgibt . Es kann wiederum nur einmal verwendet werden.
Smit Johnth
4
@ThomasAhle: Weil rangeTypen 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 ist int. Sicher, wird stroffensichtlich 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ßlich strkönnte eine Unterklasse überschreiben __eq__und in der enthalten sein range).
ShadowRanger
377

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:

  1. Überprüfen Sie, ob die Zahl zwischen startund stopund liegt
  2. Stellen Sie sicher, dass der Schrittwert unsere Zahl nicht "überschreitet".

Zum Beispiel 994ist in range(4, 1000, 2)weil:

  1. 4 <= 994 < 1000, und
  2. (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:

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

Das "Fleisch" der Idee wird in der Zeile erwähnt :

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

Als letzte Anmerkung - sehen Sie sich die range_containsFunktion 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):

>>> 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)
wim
quelle
144

Um Martijns Antwort zu ergänzen, ist dies der relevante Teil der Quelle (in C, da das Bereichsobjekt in nativem Code geschrieben ist):

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

Für PyLongObjekte ( intin Python 3) wird die range_contains_longFunktion verwendet, um das Ergebnis zu bestimmen. Und diese Funktion prüft obim Wesentlichen, ob sie im angegebenen Bereich liegt (obwohl sie in C etwas komplexer aussieht).

Wenn es sich nicht um ein intObjekt 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:

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
Sack
quelle
11
@ChrisWesseling: Ich denke, dies sind Informationen, die unterschiedlich genug sind (und genug davon), dass die Bearbeitung von Martijns Antwort hier nicht angemessen gewesen wäre. Es ist ein Urteilsspruch, aber die Leute irren normalerweise auf der Seite, die Antworten anderer Leute nicht drastisch zu ändern.
Abarnert
105

Wenn Sie sich fragen, warum diese Optimierung hinzugefügt range.__contains__wurde und warum sie in 2.7 nicht hinzugefügt xrange.__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 xrangewar es ein nicht ganz sequenziertes Objekt. Wie die 3.1-Dokumente sagen:

Bereichsobjekte haben nur ein sehr geringes Verhalten: Sie unterstützen nur die Indizierung, Iteration und die lenFunktion.

Das stimmte nicht ganz; ein xrangeObjekt unterstützt tatsächlich ein paar andere Dinge , die automatisch mit Indizierung und kommen len, * 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/ oder rangezu implementieren behaupteten collections.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ügt indexund countzu 3.2 hinzugefügt range, sondern auch das optimierte überarbeitet __contains__(das die gleiche Mathematik aufweist indexund direkt von verwendet wird count). ** 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_IterSearch3.2 range.__contains__implizit verwendet wurde, wenn die Optimierung nicht angewendet wurde.

abarnert
quelle
4
Aus den Kommentaren hier: Verbessern Siexrange.__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. Der countund index Patch wurde später hinzugefügt. Datei zu diesem Zeitpunkt: hg.python.org/cpython/file/d599a3f2e72d/Objects/rangeobject.c
Ashwini Chaudhary
12
Ich habe den finsteren Verdacht, dass einige Kern-Python-Entwickler Teil der "harten Liebe" zu Python 2.x sind, weil sie die Leute ermutigen wollen, zum weit überlegenen Python3 zu wechseln :)
wim
4
Ich wette auch, dass es eine enorme Belastung ist, alte Versionen um neue Funktionen zu erweitern. Stellen Sie sich vor, Sie gingen zu Oracle und sagten: "Ich bin auf Java 1.4 und verdiene Lambda-Ausdrücke! Backportieren Sie sie umsonst."
Rob Grant
2
@ RickTeachey Ja, es ist nur ein Beispiel. Wenn ich 1.7 sagen würde, würde es immer noch gelten. Es ist ein quantitativer Unterschied, nicht qualitativ. Grundsätzlich können die (unbezahlten) Entwickler in 3.x nicht für immer coole neue Sachen machen und sie für diejenigen, die kein Upgrade durchführen möchten, auf 2.x zurückportieren. Es ist eine große und lächerliche Belastung. Glaubst du, dass mit meiner Argumentation immer noch etwas nicht stimmt?
Rob Grant
3
@ RickTeachey: 2.7 war zwischen 3.1 und 3.2, nicht um 3.3. Und das bedeutet, dass 2.7 in rc war, als die letzten Änderungen an 3.2 vorgenommen wurden, was das Verständnis der Fehlerkommentare erleichtert. Wie auch immer, ich denke, sie haben im Nachhinein ein paar Fehler gemacht (insbesondere unter der Annahme, dass die Leute 2to3mit Hilfe von Bibliotheken wie anstelle von Dual-Version-Code migrieren würden six, weshalb wir solche Dinge haben dict.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".
Abarnert
47

Die anderen Antworten haben es bereits gut erklärt, aber ich möchte ein weiteres Experiment anbieten, das die Natur von Entfernungsobjekten veranschaulicht:

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

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.

Stefan Pochmann
quelle
27

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 schnell

Aufgrund 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.

Sławomir Lenart
quelle
4
Seien Sie vorsichtig, wenn Sie große ganze Zahlen schweben lassen. Auf den meisten Maschinen float(sys.maxsize) != sys.maxsize)allerdings sys.maxsize-float(sys.maxsize) == 0.
Holdenweb
18

TL; DR

Das von zurückgegebene Objekt range()ist tatsächlich ein rangeObjekt. 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 des inOperators angezeigt wird . Die __contains__()Methode gibt zurück, boolob sich das Element auf der linken Seite des inObjekts befindet oder nicht . Da rangeObjekte ihre Grenzen und Schritte kennen, ist dies in O (1) sehr einfach zu implementieren.

RBF06
quelle
0
  1. Aufgrund der Optimierung ist es sehr einfach, bestimmte Ganzzahlen nur mit dem Min- und Max-Bereich zu vergleichen.
  2. Der Grund dafür, dass die range () - Funktion in Python3 so schnell ist, ist, dass wir hier eher mathematisches Denken für die Grenzen verwenden als eine direkte Iteration des range-Objekts.
  3. Zur Erklärung der Logik hier:
    • Überprüfen Sie, ob die Nummer zwischen Start und Stopp liegt.
    • Überprüfen Sie, ob der Wert für die Schrittgenauigkeit nicht über unserer Zahl liegt.
  4. Nehmen Sie ein Beispiel, 997 liegt im Bereich (4, 1000, 3), weil:

    4 <= 997 < 1000, and (997 - 4) % 3 == 0.

Naruto
quelle
1
Können Sie die Quelle dafür teilen? Selbst wenn das legitim klingt, wäre es gut, diese Behauptungen durch tatsächlichen Code
Nico Haase
Ich denke, dies ist ein Beispiel dafür, wie es umgesetzt werden könnte. Nicht genau so, wie es implementiert wird. Obwohl keine Referenz angegeben ist, ist es ein guter Hinweis, der gut genug ist, um zu verstehen, warum die Überprüfung der Aufnahme auf die Reichweite viel schneller sein kann als die Liste oder das Tupel
Mohammed Shareef C
0

Versuchen Sie es x-1 in (i for i in range(x))mit großen xWerten, bei denen ein Generatorverständnis verwendet wird, um das Aufrufen der range.__contains__Optimierung zu vermeiden .

benjimin
quelle