Dlaczego „1000000000000000 w zakresie (1000000000000001)” jest tak szybki w Pythonie 3?

Rozumiem, że range()funkcja, która w Pythonie 3 jest typem obiektu , generuje zawartość w locie, podobnie jak generator.

W takim przypadku oczekiwałbym, że następujący wiersz zajmie nadmiernie dużo czasu, ponieważ w celu ustalenia, czy 1 biliard mieści się w zakresie, należałoby wygenerować biliardy:

1000000000000000 in range(1000000000000001)

Co więcej: wydaje się, że bez względu na to, ile zer dodam, obliczenia mniej więcej zajmują tyle samo czasu (w zasadzie natychmiastowe).

Próbowałem też takich rzeczy, ale obliczenia są prawie natychmiastowe:

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

Jeśli spróbuję zaimplementować własną funkcję zakresu, wynik nie będzie tak dobry !!

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

Co range()robi obiekt pod maską, który sprawia, że ​​jest tak szybki?

Odpowiedź Martijna Pietersa została wybrana ze względu na jej kompletność, ale zobacz także pierwszą odpowiedź abarnerta, aby uzyskać dobrą dyskusję na temat tego, co to znaczy rangebyć pełnoprawną sekwencją w Pythonie 3, oraz pewne informacje / ostrzeżenia dotyczące potencjalnej niespójności w zakresie __contains__optymalizacji funkcji w różnych implementacjach Pythona . Inna odpowiedź abarnerta zawiera bardziej szczegółowe informacje i zawiera łącza dla osób zainteresowanych historią stojącą za optymalizacją w Pythonie 3 (i brakiem optymalizacji xrangew Pythonie 2). Odpowiedzi poke i wim zawierają odpowiedni kod źródłowy C i wyjaśnienia dla zainteresowanych.

Obiekt Python 3 range()nie generuje liczb od razu; jest to inteligentny obiekt sekwencji, który wytwarza liczby na żądanie . Wszystko, co zawiera, to wartości początkowe, stop i krokowe, a następnie podczas iteracji nad obiektem następna liczba całkowita jest obliczana dla każdej iteracji.

Obiekt implementuje również object.__contains__hak i oblicza, czy Twój numer należy do jego zakresu. Obliczanie jest operacją (prawie) o stałym czasie ^* . Nigdy nie ma potrzeby skanowania wszystkich możliwych liczb całkowitych w zakresie.

Z range()dokumentacji obiektu :

Zaletą rangetypu na regularny listlub tuplejest to, że obiekt zakres będzie zawsze ten sam (mały) ilość pamięci, bez względu na wielkość zakresie reprezentuje (jak to tylko przechowuje start, stopi stepwartości, obliczania poszczególnych elementów i podzakresy w razie potrzeby).

Zatem przynajmniej twój range()obiekt wykonałby:

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

W dalszym ciągu brakuje kilku rzeczy, które prawdziwe range()wsparcie (takich jak metody .index()lub .count(), mieszanie, testowanie równości lub krojenie), ale powinien dać ci pomysł.

Uprościłem także __contains__implementację, aby skupić się wyłącznie na testach na liczbach całkowitych; jeśli podasz rzeczywistemu range()obiektowi wartość niecałkowitą (łącznie z podklasami int), zainicjowane zostanie powolne skanowanie w celu sprawdzenia, czy istnieje dopasowanie, tak jak w przypadku testu szczelności względem listy wszystkich zawartych wartości. Zrobiono to, aby nadal obsługiwać inne typy liczbowe, które akurat obsługują testowanie równości za pomocą liczb całkowitych, ale nie oczekuje się, aby wspierały również arytmetykę liczb całkowitych. Zobacz oryginalny problem w języku Python, który implementował test powstrzymywania.

* Niemal stały czas, ponieważ liczby całkowite w języku Python są nieograniczone, więc operacje matematyczne również rosną w czasie, gdy N rośnie, co czyni tę operację O (log N). Ponieważ wszystko jest wykonywane w zoptymalizowanym kodzie C, a Python przechowuje wartości całkowite w 30-bitowych porcjach, zabraknie pamięci, zanim zobaczysz jakikolwiek wpływ na wydajność z powodu wielkości zaangażowanych tutaj liczb całkowitych.

Podstawowym nieporozumieniem jest myślenie, że rangejest generatorem. To nie jest. W rzeczywistości nie jest to żaden iterator.

Możesz to łatwo powiedzieć:

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

Gdyby to był generator, iteracja go raz by go wyczerpała:

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

To, co rangetak naprawdę jest, to sekwencja, podobnie jak lista. Możesz nawet to przetestować:

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

Oznacza to, że musi przestrzegać wszystkich zasad bycia sekwencją:

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

Różnica między a rangea listpolega na tym, że a rangejest sekwencją leniwą lub dynamiczną ; nie pamiętam wszystkich jego wartości, to po prostu pamięta jej start, stopi step, i tworzy wartości od zapotrzebowania na __getitem__.

(Na marginesie, jeśli zauważysz print(iter(a)), że rangeużywa tego samego listiteratortypu co list. Jak to działa? A listiteratornie używa niczego specjalnego listpoza tym, że zapewnia implementację C __getitem__, więc działa dobrze dla rangeteż.)

Teraz nic nie mówi o tym, że Sequence.__contains__musi to być stały czas - w rzeczywistości, dla oczywistych przykładów takich sekwencji list, nie jest. Ale nic nie mówi, że nie może być. I łatwiej jest wdrożyć, range.__contains__aby sprawdzić to matematycznie ( (val - start) % stepale z pewną dodatkową złożonością, aby poradzić sobie z negatywnymi krokami) niż faktycznie wygenerować i przetestować wszystkie wartości, więc dlaczego nie zrobić tego lepiej?

Ale wydaje się, że w języku nie ma nic, co gwarantowałoby, że tak się stanie. Jak zauważa Ashwini Chaudhari, jeśli podasz mu wartość niecałkowitą, zamiast konwersji na liczbę całkowitą i wykonania testu matematycznego, wróci do iteracji wszystkich wartości i porównywania ich jeden po drugim. I tylko dlatego, że wersje CPython 3.2+ i PyPy 3.x zawierają tę optymalizację, a jest to oczywisty dobry pomysł i łatwy do zrobienia, nie ma powodu, aby IronPython lub NewKickAssPython 3.x nie mógł tego pominąć. (I faktycznie CPython 3.0-3.1 go nie zawierał.)

Gdyby rangerzeczywiście był generatorem, my_crappy_rangetestowanie w __contains__ten sposób nie miałoby sensu , a przynajmniej sposób, w jaki ma sens, nie byłby oczywisty. Jeśli już iterowałeś już pierwsze 3 wartości, to czy generator jest 1nadal in? Czy testowanie w celu 1spowodowania iteracji i zużycia wszystkich wartości do 1(lub do pierwszej wartości >= 1)?

Użyj źródła , Luke!

W CPython range(...).__contains__(opakowanie metody) ostatecznie deleguje się do prostego obliczenia, które sprawdza, czy wartość może być w zakresie. Powodem prędkości jest tutaj matematyczne rozumowanie granic, a nie bezpośrednia iteracja obiektu zasięgu . Aby wyjaśnić zastosowaną logikę:

1. Sprawdź, czy liczba zawiera się między starti stop, a
2. Sprawdź, czy wartość kroku nie „przekracza” naszej liczby.

Na przykład 994jest, range(4, 1000, 2)ponieważ:

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

Pełny kod C znajduje się poniżej, co jest nieco bardziej szczegółowe ze względu na zarządzanie pamięcią i liczenie referencji, ale podstawowa idea jest taka:

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

„Mięso” pomysłu wspomniano w wierszu :

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

Na koniec - spójrz na range_containsfunkcję u dołu fragmentu kodu. Jeśli dokładna kontrola typu nie powiedzie się, nie używamy opisanego sprytnego algorytmu, zamiast tego wracamy do głupiego wyszukiwania iteracji zakresu za pomocą _PySequence_IterSearch! Możesz sprawdzić to zachowanie w tłumaczu (korzystam z wersji 3.5.0 tutaj):

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

Aby dodać do odpowiedzi Martijna, jest to odpowiednia część źródła (w C, ponieważ obiekt zakresu jest zapisany w kodzie natywnym):

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

Więc dla PyLongobiektów (które jest intw Pythonie 3) użyjerange_contains_long funkcji do ustalenia wyniku. Ta funkcja zasadniczo sprawdza, czy obznajduje się w określonym zakresie (chociaż wygląda nieco bardziej skomplikowanie w C).

Jeśli to nie jest int obiekt, wraca do iteracji, dopóki nie znajdzie wartości (lub nie).

Całą logikę można przetłumaczyć na pseudo-Python w następujący sposób:

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

Jeśli zastanawiasz się, dlaczego dodano tę optymalizację range.__contains__i dlaczego nie dodano jej xrange.__contains__w wersji 2.7:

Po pierwsze, jak odkrył Ashwini Chaudhary, numer 1766304 został jawnie otwarty w celu optymalizacji [x]range.__contains__. Poprawka do tego została zaakceptowana i zarejestrowana w wersji 3.2 , ale nie została przeniesiona do wersji 2.7, ponieważ „xrange zachowywał się w ten sposób przez tak długi czas, że nie widzę, co kupuje nam, aby wprowadzić łatkę tak późno”. (2.7 było prawie na tym etapie.)

W międzyczasie:

Pierwotnie xrangebył to obiekt niezupełnie sekwencyjny. Jak mówią dokumenty 3.1 :

Obiekty zakresu mają bardzo małe zachowanie: obsługują tylko indeksowanie, iterację i lenfunkcję.

To nie była do końca prawda; xrangeobiekt faktycznie obsługiwane kilka innych rzeczy, które przychodzą automatycznie i indeksowania len, ^* w tym__contains__ (poprzez przeszukiwanie liniowe). Ale nikt nie sądził, że warto było robić w tym czasie pełne sekwencje.

Następnie, w ramach implementacji PEP abstrakcyjnych klas podstawowych , ważne było, aby dowiedzieć się, które wbudowane typy powinny zostać oznaczone jako implementujące, które ABC i xrange/ lub rangetwierdziły, że mają zaimplementować collections.Sequence, mimo że nadal obsługiwały tylko to samo „bardzo małe zachowanie”. Nikt nie zauważył tego problemu do wydania 9213 . Łatka dla tego problemu nie tylko została dodana indexi countdo wersji 3.2 range, ale także przerobiła zoptymalizowaną __contains__(która dzieli tę samą matematykę indexi jest bezpośrednio używana count). ^** Ta zmiana dotyczyła również wersji 3.2 i nie została przeniesiona do wersji 2.x, ponieważ „jest to poprawka błędów, która dodaje nowe metody”. (W tym momencie 2.7 był już w stanie rc.)

Były więc dwie szanse na przeniesienie tej optymalizacji do wersji 2.7, ale obie zostały odrzucone.

_{* W rzeczywistości masz nawet iterację za darmo z samym indeksowaniem, ale w 2.3 xrange obiektach masz niestandardowy iterator.}

_{** Pierwsza wersja faktycznie go ponownie wdrożyła i podała błędne dane - np. Dałaby ci MyIntSubclass(2) in range(5) == False. Ale zaktualizowana wersja łatki Daniela Stutzbacha przywróciła większość poprzedniego kodu, w tym powrót do ogólnego, powolnego _PySequence_IterSearch, range.__contains__którego domyślnie używała wersja wcześniejsza niż 3.2, gdy optymalizacja nie ma zastosowania.}

Inne odpowiedzi już to dobrze wyjaśniły, ale chciałbym zaoferować kolejny eksperyment ilustrujący naturę obiektów zasięgu:

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

Jak widać, obiekt zasięgu to obiekt, który pamięta swój zasięg i może być używany wiele razy (nawet podczas iteracji nad nim), a nie tylko generator jednorazowy.

To wszystko o leniwe podejście do oceny i jakimś dodatkowym optymalizacji z range. Wartości w zakresach nie muszą być obliczane do czasu rzeczywistego użycia, a nawet dalej ze względu na dodatkową optymalizację.

Nawiasem mówiąc, twoja liczba całkowita nie jest tak duża, zastanów się sys.maxsize

sys.maxsize in range(sys.maxsize) jest dość szybki

dzięki optymalizacji - łatwo jest porównać podaną liczbę całkowitą tylko z minimalnym i maksymalnym zakresem.

ale:

Decimal(sys.maxsize) in range(sys.maxsize) jest dość wolny .

(w tym przypadku nie ma optymalizacji range, więc jeśli python otrzyma nieoczekiwany po przecinku, python porówna wszystkie liczby)

Powinieneś być świadomy szczegółów implementacji, ale nie powinieneś na nich polegać, ponieważ może to ulec zmianie w przyszłości.

TL; DR

Obiekt zwracany przez range()to tak naprawdę rangeobiekt. Ten obiekt implementuje interfejs iteratora, dzięki czemu możesz kolejno iterować jego wartości, podobnie jak generator, lista lub krotka.

Ale to także implementuje __contains__interfejs, który jest rzeczywiście to, co jest wywoływana, gdy po prawej strony pojawi się przedmiot inoperatora. Że __contains__()metoda zwraca boolna to, czy pozycji na lewej-stronie injest w obiekcie. Ponieważ rangeobiekty znają swoje granice i krok, bardzo łatwo jest to zaimplementować w O (1).

1. Dzięki optymalizacji bardzo łatwo jest porównać podane liczby całkowite tylko z zakresem min. I maks.
2. Powodem, dla którego funkcja range () jest tak szybka w Pythonie 3, jest fakt, że tutaj używamy matematycznego rozumowania granic, a nie bezpośredniej iteracji obiektu zakresu.
3. Aby wyjaśnić logikę tutaj:
   • Sprawdź, czy liczba zawiera się między początkiem a stopem.
   • Sprawdź, czy wartość dokładności kroku nie przekracza naszej liczby.

4. Weźmy przykład, 997 jest w zasięgu (4, 1000, 3), ponieważ:

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

Wypróbuj x-1 in (i for i in range(x))duże xwartości, które używają zrozumienia generatora, aby uniknąć wywoływania range.__contains__optymalizacji.