Frage Warum ist "1000000000000000 im Bereich (1000000000000001)" in Python 3 so schnell?


Es ist mein Verständnis, dass das range() Funktion, die eigentlich ist ein Objekttyp in Python 3, generiert seinen Inhalt im laufenden Betrieb, ähnlich wie ein Generator.

Da dies der Fall ist, hätte ich erwartet, dass die folgende Zeile übermäßig viel Zeit in Anspruch nimmt, denn um zu bestimmen, ob 1 Billiarde im Bereich liegt, müssten eine Billiarde Werte generiert werden:

1000000000000000 in range(1000000000000001)

Außerdem: Es scheint, dass egal wie viele Nullen ich addiere, die Berechnung mehr oder weniger die gleiche Zeit benötigt (im Grunde sofort).

Ich habe auch so etwas probiert, 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 ist der range() Objekt unter der Haube, die es so schnell macht?


Martijn Pieters 'Antwort wurde für seine Vollständigkeit gewählt, aber auch gesehen Abarnerts erste Antwort für eine gute Diskussion dessen, was es bedeutet range ein vollwertiges sein Sequenz in Python 3 und einige Informationen / Warnungen bezüglich möglicher Inkonsistenzen für __contains__ Funktionsoptimierung in Python-Implementierungen Abarnerts andere Antwort geht etwas genauer auf und bietet Links für diejenigen, die sich für die Geschichte hinter der Optimierung in Python 3 interessieren (und die fehlende Optimierung von xrange in Python 2). Antworten durch stochern und von wim Stellen Sie den relevanten C-Quellcode und Erklärungen für Interessierte zur Verfügung.


1364
2018-05-06 15:32


Ursprung


Antworten:


Das Python 3 range() Objekt erzeugt keine Zahlen sofort; es ist ein intelligentes Sequenzobjekt, das Zahlen erzeugt auf Nachfrage. Alles, was es enthält, sind Ihre Start-, Stopp- und Schrittwerte. Wenn Sie dann über das Objekt iterieren, wird die nächste ganze Zahl für jede Iteration berechnet.

Das Objekt implementiert auch die object.__contains__ Haken, und berechnet wenn Ihre Nummer Teil ihrer Reichweite ist. Die Berechnung ist eine O (1) konstante Zeitoperation. Es ist niemals notwendig, alle möglichen Ganzzahlen im Bereich zu durchsuchen.

Von dem range() Objektdokumentation:

Der Vorteil der range Tippen Sie über einen regulären list oder tuple ist, dass ein Bereichsobjekt immer die gleiche (kleine) Speichermenge annimmt, unabhängig von der Größe des Bereichs, den es darstellt (da es nur die start, stop und step Werte, Berechnung einzelner Elemente und Unterbereiche nach Bedarf).

Also zumindest range() Objekt würde 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 = 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

Hier fehlen noch einige Dinge, die echt sind range() unterstützt (wie die .index() oder .count() Methoden, Hashing, Gleichheitsprüfung oder Slicing), sollte Ihnen aber eine Idee geben.

Ich habe auch das vereinfacht __contains__ Implementierung, um sich nur auf ganzzahlige Tests zu konzentrieren; wenn du ein echtes gibst range() Objekt einen nicht ganzzahligen Wert (einschließlich Unterklassen von int), wird ein langsamer Scan gestartet, um festzustellen, ob eine Übereinstimmung vorliegt, so als ob Sie einen Containment-Test für eine Liste aller enthaltenen Werte verwenden würden. Dies wurde getan, um weiterhin andere numerische Typen zu unterstützen, die zufällig Gleichheitsprüfungen mit ganzen Zahlen unterstützen, aber es wird nicht erwartet, dass sie auch Ganzzahlarithmetik unterstützen. Siehe das Original Python-Problem das implementierte den Eindämmtest.


1351
2018-05-06 15:33



Das grundlegende Missverständnis besteht darin, dies zu denken range ist ein Generator. Es ist nicht. In der Tat ist es keine Art von Iterator.

Das kannst du ganz einfach 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 die Iteration es einmal erschöpfen:

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

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

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

Das bedeutet, dass es allen Regeln folgen muss, eine Sequenz zu sein:

>>> 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 range und ein list ist das ein range ist ein faul oder dynamisch Sequenz; es erinnert sich nicht an alle seine Werte, es erinnert nur an seine start, stop, und step, und erstellt die Werte bei Bedarf auf __getitem__.

(Als Randnotiz, wenn Sie print(iter(a))Das wirst du bemerken range benutzt das selbe listiterator Geben Sie als ein list. Wie funktioniert das? EIN listiterator benutzt nichts besonderes list abgesehen von der Tatsache, dass es eine C-Implementierung von bietet __getitem__, so funktioniert es gut für range auch.)


Jetzt gibt es nichts, was das sagt Sequence.__contains__ es muss konstante Zeit sein - in der Tat, für offensichtliche Beispiele von Sequenzen wie listist es nicht. Aber es gibt nichts, was es sagt kippen Sein. Und es ist einfacher zu implementieren range.__contains__ um 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, also warum sollte nicht macht es den besseren Weg?

Aber in der Sprache scheint es nichts zu geben Garantien das wird passieren. Ashwini Chaudhari weist darauf hin, dass, wenn Sie ihm einen nicht-ganzzahligen Wert geben, anstatt in eine Ganzzahl zu konvertieren und den mathematischen Test durchzuführen, wird er darauf zurückgreifen, alle Werte zu iterieren und sie einzeln zu vergleichen. Und gerade weil CPython 3.2+ und PyPy 3.x-Versionen diese Optimierung enthalten, und es eine offensichtliche gute Idee und einfach zu machen ist, gibt es keinen Grund, dass IronPython oder NewKickAssPython 3.x es nicht auslassen könnte. (Und tatsächlich CPython 3.0-3.1 nicht schließe es ein.)


Ob range eigentlich war ein Generator, wie my_crappy_range, dann wäre es nicht sinnvoll zu testen __contains__ so oder zumindest so, wie es Sinn macht, wäre nicht offensichtlich. Wenn Sie die ersten 3 Werte bereits wiederholt haben, ist 1 immer noch in der Generator? Sollte testen für 1 veranlaßt es, alle Werte bis zu iterieren und zu konsumieren 1 (oder bis zum ersten Wert >= 1)


561
2018-05-06 16:01



Benutze die Quelle, Luke!

In CPython, range(...).__contains__ (ein Methodenwrapper) wird schließlich zu einer einfachen Berechnung delegieren, die überprüft, ob der Wert möglicherweise in dem Bereich sein kann. Der Grund für die Geschwindigkeit hier ist, dass wir verwenden mathematisches Nachdenken über die Grenzen statt einer direkten Iteration des Bereichsobjekts. Um die verwendete Logik zu erklären:

  1. Überprüfen Sie, ob die Nummer zwischen liegt start und stop, und
  2. Stellen Sie sicher, dass der Schrittwert nicht über unsere Nummer hinausgeht.

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

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

Der vollständige C-Code ist unten enthalten, was wegen der Details zur Speicherverwaltung und Referenzzählung ein wenig ausführlicher ist, aber die Grundidee ist:

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 erwähnt die Linie:

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

Als letzte Anmerkung - schauen Sie sich die range_contains Funktion am unteren Rand des Code-Snippets. Wenn die genaue Typprüfung fehlschlägt, verwenden wir nicht den beschriebenen cleveren Algorithmus, sondern greifen stattdessen auf eine dumme Iterationssuche des Bereichs zurück _PySequence_IterSearch! Sie können dieses Verhalten im Interpreter überprüfen (ich verwende v3.5.0 hier):

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



Um Martijns Antwort hinzuzufügen, ist dies der relevante Teil von die Quelle (in C, da das Bereichsobjekt in systemeigenem 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);
}

So für PyLong Objekte (was ist int in Python 3), wird es die verwenden range_contains_long Funktion, um das Ergebnis zu bestimmen. Und diese Funktion überprüft im Wesentlichen, ob ob ist im angegebenen Bereich (obwohl es in C etwas komplexer aussieht).

Wenn es nicht ein ist int Objekt, es fällt zurück zu wiederholen, bis es den Wert findet (oder nicht).

Die ganze Logik könnte wie folgt 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

106
2018-05-06 15:41



Wenn Sie sich fragen Warum Diese Optimierung wurde hinzugefügt range.__contains__und warum es war nicht hinzugefügt zu xrange.__contains__ in 2.7:

Erstens, wie Ashwini Chaudhary entdeckte, Ausgabe 1766304 wurde explizit zur Optimierung geöffnet [x]range.__contains__. Ein Patch dafür war akzeptiert und eingecheckt für 3.2, aber nicht auf 2.7 zurückversetzt, weil "xrange sich so lange so verhalten hat, dass ich nicht sehe, was es uns so spät kauft, um den Patch zu machen." (2.7 war zu diesem Zeitpunkt fast out.)

Inzwischen:

Ursprünglich, xrange war ein Nicht-Sequenz-Objekt. Wie die 3.1 Dokumente sagen:

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

Das war nicht ganz richtig; ein xrange Objekt tatsächlich unterstützt ein paar andere Dinge, die automatisch mit der Indizierung kommen und len,* einschließlich __contains__ (über lineare Suche). Aber niemand dachte, dass es sich lohnte, ihnen zu dieser Zeit vollständige Sequenzen zu geben.

Dann, als Teil der Implementierung der Abstrakte Basisklassen PEP, war es wichtig herauszufinden, welche eingebauten Typen als welche ABCs zu implementieren markiert werden, und xrange/range behauptete zu implementieren collections.Sequence, obwohl es immer noch nur das "sehr kleine Verhalten" behandelte. Niemand bemerkte dieses Problem bis Ausgabe 9213. Der Patch für dieses Problem wurde nicht nur hinzugefügt index und count zu 3.2 rangeEs hat auch das optimierte überarbeitet __contains__ (die die gleiche Mathematik mit teilt indexund wird direkt von verwendet count).**  Dieser Wandel ging auch für 3.2 und wurde nicht auf 2.x zurückportiert, weil "es ein Bugfix ist, der neue Methoden hinzufügt". (Zu diesem Zeitpunkt war 2.7 bereits vergangen, RC-Status.)

Es gab also zwei Möglichkeiten, diese Optimierung auf 2,7 zurück zu portieren, aber beide wurden abgelehnt.


* In der Tat, erhalten Sie sogar Iteration kostenlos mit len und Indizierung, aber in 2.3  xrange Objekte haben einen benutzerdefinierten Iterator. Was sie dann in 3.x verloren haben, das nutzt dasselbe listiterator Geben Sie als ein list.

** Die erste Version hat es tatsächlich neu implementiert und die Details falsch verstanden - z. B. würde es dir geben MyIntSubclass(2) in range(5) == False. Aber die aktualisierte Version von Daniel Stutzbach des Patches wiederhergestellt die meisten der vorherigen Code, einschließlich der Fallback auf die generische, langsam _PySequence_IterSearch das vor 3.2 range.__contains__ wurde implizit verwendet, wenn die Optimierung nicht zutrifft.


79
2018-05-06 21:42



Die anderen Antworten haben es bereits gut erklärt, aber ich möchte ein weiteres Experiment anbieten, das die Art von Bereichsobjekten 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, handelt es sich bei einem Bereichsobjekt um ein Objekt, das sich an seinen Bereich erinnert und viele Male (auch während des Iterierens) verwendet werden kann, nicht nur ein einmaliger Generator.


35
2018-05-06 16:04



Es geht nur um einen faulen Ansatz bei der Bewertung und einige zusätzliche Optimierungen von range. Werte in Bereichen müssen nicht bis zur tatsächlichen Verwendung oder aufgrund zusätzlicher Optimierung noch weiter berechnet werden.

Nebenbei bemerkt ist Ihre ganze Zahl nicht so groß sys.maxsize

sys.maxsize in range(sys.maxsize)  ist ziemlich schnell

aufgrund der Optimierung - es ist einfach, die angegebene Ganzzahl nur mit dem minimalen und maximalen Bereich zu vergleichen.

aber:

float(sys.maxsize) in range(sys.maxsize)  ist ziemlich langsam.

(In diesem Fall gibt es keine Optimierung in range, da seit dem unerwarteten Float erhalten, wird Python alle Zahlen vergleichen)


3
2018-03-16 10:47