Vraag Waarom is "1000000000000000 binnen bereik (1000000000000001)" zo snel in Python 3?


Het is mijn begrip dat de range() functie, dat is eigenlijk een objecttype in Python 3, genereert zijn inhoud on the fly, vergelijkbaar met een generator.

Aangezien dit het geval was, had ik verwacht dat de volgende regel een buitensporige hoeveelheid tijd zou innemen, omdat om te bepalen of 1 quadrillion binnen het bereik valt, er een quadriljoenwaarde zou moeten worden gegenereerd:

1000000000000000 in range(1000000000000001)

Verder: het lijkt erop dat het niet uitmaakt hoeveel nullen ik toevoeg, de berekening neemt min of meer evenveel tijd in beslag (in feite onmiddellijk).

Ik heb ook dingen als deze geprobeerd, maar de berekening is nog steeds bijna onmiddellijk:

1000000000000000000000 in range(0,1000000000000000000001,10) # count by tens

Als ik mijn eigen bereikfunctie probeer te implementeren, is het resultaat niet zo leuk !!

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

Wat is de range() object dat onder de motorkap doet dat het zo snel maakt?


Martijn Pieters 'antwoord werd gekozen voor zijn volledigheid, maar zie ook abarnert's eerste antwoord voor een goede discussie over waar het voor betekent range een volwaardige zijn volgorde in Python 3, en enige informatie / waarschuwing met betrekking tot potentiële inconsistentie voor __contains__ functie-optimalisatie bij Python-implementaties. het andere antwoord van abarnert gaat in wat meer detail en biedt links voor diegenen die geïnteresseerd zijn in de geschiedenis achter de optimalisatie in Python 3 (en gebrek aan optimalisatie van xrange in Python 2). antwoorden door poke en door wim verstrek de relevante C-broncode en uitleg voor diegenen die geïnteresseerd zijn.


1364
2018-05-06 15:32


oorsprong


antwoorden:


De Python 3 range() object produceert niet onmiddellijk cijfers; het is een slim sequentieobject dat getallen produceert op aanvraag. Het bevat alleen uw begin-, stop- en stapwaarden, en vervolgens, terwijl u over het object heen loopt, wordt het volgende gehele getal berekend voor elke iteratie.

Het object implementeert ook de object.__contains__ haak, en berekent als uw nummer deel uitmaakt van het bereik. Berekening is een O (1) constante tijd operatie. Het is nooit nodig om alle mogelijke gehele getallen in het bereik te scannen.

Van de range() object documentatie:

Het voordeel van de range typ een reguliere list of tuple is dat een bereikobject altijd dezelfde (kleine) hoeveelheid geheugen zal hebben, ongeacht de grootte van het bereik dat het weergeeft (omdat het alleen de start, stop en step waarden, individuele items en subbereiken berekenen indien nodig).

Dus op zijn minst, jouw range() object zou doen:

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

Dit is nog steeds een aantal dingen die een echte missen range() ondersteunt (zoals de .index() of .count() methoden, hashing, testen van gelijkheid of slicing), maar zou u een idee moeten geven.

Ik vereenvoudigde ook de __contains__ implementatie om alleen te focussen op integere tests; als je een real geeft range() object een niet-integer waarde (inclusief subklassen van int), wordt een langzame scan gestart om te zien of er een overeenkomst is, net alsof u een containment-test gebruikt tegen een lijst met alle ingesloten waarden. Dit is gedaan om andere numerieke typen te ondersteunen die toevallig gelijkheidstests met gehele getallen ondersteunen, maar waarvan ook niet wordt verwacht dat ze ook de gehele rekenen ondersteunen. Zie het origineel Python probleem die de containment-test heeft uitgevoerd.


1351
2018-05-06 15:33



Het fundamentele misverstand hier is om dat te denken range is een generator. Het is niet. In feite is het geen enkele vorm van iterator.

Je kunt dit vrij eenvoudig vertellen:

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

Als het een generator was, zou het een keer itereren het uitputten:

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

Wat range eigenlijk is, is een reeks, net als een lijst. U kunt dit zelfs testen:

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

Dit betekent dat het alle regels moet volgen om een ​​reeks te zijn:

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

Het verschil tussen een range en een list is dat een range is een lui of dynamisch volgorde; het onthoudt niet al zijn waarden, het onthoudt het gewoon start, stop, en step, en maakt de waarden op aanvraag aan __getitem__.

(Als een kanttekening, als u print(iter(a)), dat merk je range gebruikt hetzelfde listiterator type als list. Hoe werkt dat? EEN listiterator gebruikt hier niets bijzonders over list behalve het feit dat het een C-implementatie van __getitem__, dus het werkt prima voor range te.)


Nu, er is niets dat dat zegt Sequence.__contains__ moet een constante tijd zijn - in feite, voor voor de hand liggende voorbeelden van sequenties zoals list, dat is het niet. Maar er is niets dat het zegt kan niet worden. En het is gemakkelijker te implementeren range.__contains__ om het gewoon wiskundig te controleren ((val - start) % step, maar met wat extra complexiteit om met negatieve stappen om te gaan) dan om alle waarden daadwerkelijk te genereren en te testen, dus waarom moet niet doet het het op de betere manier?

Maar er lijkt niets in de taal te zijn garanties dit zal gebeuren. Zoals Ashwini Chaudhari opmerkt, als je het een niet-integrale waarde geeft, in plaats van te converteren naar integer en de wiskundige test te doen, zal het terugvallen op iteratie van alle waarden en ze één voor één vergelijken. En alleen omdat CPython 3.2+ en PyPy 3.x-versies deze optimalisatie bevatten, en het is een logisch goed idee en gemakkelijk te doen, er is geen reden dat IronPython of NewKickAssPython 3.x het niet zouden kunnen negeren. (En in feite CPython 3.0-3.1 niet opnemen.)


Als range eigenlijk was een generator, zoals my_crappy_range, dan zou het niet logisch zijn om te testen __contains__ op deze manier, of op zijn minst de manier waarop het zinvol is, zou niet voor de hand liggen. Als je de eerste drie waarden al hebt herhaald, is dat het geval 1 nog steeds in de generator? Moet testen voor 1 zorg ervoor dat het alle waarden herhaalt en consumeert tot 1 (of tot de eerste waarde >= 1)?


561
2018-05-06 16:01



Gebruik de bron, Luke!

In CPython, range(...).__contains__ (een methode-wrapper) zal uiteindelijk delegeren naar een eenvoudige berekening die controleert of de waarde mogelijk binnen het bereik valt. De reden voor de snelheid hier is die we gebruiken wiskundig redeneren over de grenzen, in plaats van een directe iteratie van het bereikobject. Om de gebruikte logica te verklaren:

  1. Controleer of het aantal tussen ligt start en stop, en
  2. Controleer of de stapswaarde niet ons nummer "overschrijdt".

Bijvoorbeeld, 994 is in range(4, 1000, 2) omdat:

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

De volledige C-code is hieronder opgenomen, die wat gedetailleerder is vanwege geheugenbeheer en verwijzingsdetails, maar het basisidee is daar:

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

Het "vlees" van het idee wordt genoemd in de lijn:

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

Als laatste opmerking - kijk naar de range_contains functie onderaan het codefragment. Als de exacte typecontrole mislukt, gebruiken we niet het slimme algoritme dat wordt beschreven, maar gaan we terug naar een domme iteratiezoekopdracht van het bereik met _PySequence_IterSearch! U kunt dit gedrag in de interpreter controleren (hier gebruik ik 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)

285
2018-05-06 15:41



Om toe te voegen aan het antwoord van Martijn, is dit het relevante deel van de bron (in C, omdat het bereikobject is geschreven in native code):

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

Dus voor PyLong objecten (dat is int in Python 3), zal het de range_contains_long functie om het resultaat te bepalen. En die functie controleert in wezen of ob bevindt zich in het opgegeven bereik (hoewel het er in C iets ingewikkelder uitziet).

Als het geen is int object, het valt terug naar itereren totdat het de waarde vindt (of niet).

De hele logica zou op deze manier in pseudo-Python kunnen worden vertaald:

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



Als je je afvraagt waarom deze optimalisatie is toegevoegd aan range.__contains__en waarom was niet toegevoegd aan xrange.__contains__ in 2.7:

Ten eerste, zoals Ashwini Chaudhary ontdekte, kwestie 1766304 werd expliciet geopend om te optimaliseren [x]range.__contains__. Een patch hiervoor was geaccepteerd en ingecheckt voor 3.2, maar niet teruggestuurd naar 2.7 omdat "xrange zich zo lang heeft gedragen dat ik niet zie wat het ons koopt om de patch zo laat te plegen." (2,7 was bijna op dat punt.)

Ondertussen:

Oorspronkelijk, xrange was een niet-heel-reeks object. Als de 3.1 documenten zeggen:

Range-objecten hebben heel weinig gedrag: ze ondersteunen alleen indexering, iteratie en de len functie.

Dit was niet helemaal waar; een xrange object heeft feitelijk een aantal andere dingen ondersteund die automatisch worden geïndexeerd met indexering en len,* inclusief __contains__ (via lineair zoeken). Maar niemand dacht dat het de moeite waard was om ze op dat moment volledige reeksen te maken.

Vervolgens, als onderdeel van de implementatie van de Abstracte basisklassen PEP, het was belangrijk om erachter te komen welke ingebouwde typen moeten worden gemarkeerd als implementerende welke ABC's, en xrange/range beweerde te implementeren collections.Sequence, hoewel het nog steeds hetzelfde "zeer weinig gedrag" behandelde. Niemand merkte dat probleem tot kwestie 9213. De patch voor dat probleem is niet alleen toegevoegd index en count tot 3.2's range, het werkte ook opnieuw de geoptimaliseerde __contains__ (die dezelfde wiskunde deelt met index, en wordt direct gebruikt door count).**  Deze verandering ging ook voor 3.2, en werd niet teruggezet naar 2.x, omdat "het een bugfix is ​​die nieuwe methoden toevoegt". (Op dit moment was 2.7 al voorbij de rc-status.)

Er waren dus twee kansen om deze optimalisatie terug naar 2.7 te krijgen, maar ze werden allebei afgewezen.


* In feite krijg je zelfs gratis iteratie len en indexeren, maar in 2.3  xrange objecten hebben een aangepaste iterator. Die ze vervolgens verloren hebben in 3.x, die hetzelfde gebruikt listiterator type als list.

** De eerste versie heeft het opnieuw geïmplementeerd en de details zijn verkeerd, bijvoorbeeld MyIntSubclass(2) in range(5) == False. Maar Daniel Stutzbach's bijgewerkte versie van de patch herstelde de meeste van de vorige code, inclusief de fallback naar de generieke, traag _PySequence_IterSearch dat pre-3.2 range.__contains__ werd impliciet gebruikt wanneer de optimalisatie niet van toepassing is.


79
2018-05-06 21:42



De andere antwoorden legden het al goed uit, maar ik zou graag een ander experiment aanbieden dat de aard van bereikobjecten illustreert:

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

Zoals u kunt zien, is een bereikobject een object dat het bereik onthoudt en vele malen kan worden gebruikt (zelfs als het wordt herhaald), en niet alleen een eenmalige generator.


35
2018-05-06 16:04



Het draait allemaal om een ​​luie benadering van de evaluatie en wat extra optimalisatie van range. Waarden in bereiken hoeven niet te worden berekend tot het werkelijke gebruik, of zelfs verder als gevolg van extra optimalisatie.

Trouwens, je integer is niet zo groot, overweeg sys.maxsize

sys.maxsize in range(sys.maxsize)  is vrij snel

vanwege optimalisatie - het is gemakkelijk om een ​​gegeven geheel getal te vergelijken met min en max van het bereik.

maar:

float(sys.maxsize) in range(sys.maxsize)  is vrij langzaam.

(in dit geval is er geen optimalisatie in range, dus sinds onverwacht float ontvangt, vergelijkt python alle getallen)


3
2018-03-16 10:47