Dlaczego "10000000000000000000 w zakresie (100000000000000001)" jest tak szybki w Pythonie 3?

Fundamentalnym nieporozumieniem jest myślenie, że jest generatorem. Nie jest. W rzeczywistości nie jest to żaden iterator.

Możesz to powiedzieć dość łatwo:

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

Gdyby był generatorem, iteracja raz by go wyczerpała:

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

Czym range w rzeczywistości jest sekwencja, tak jak lista. Możesz nawet przetestować to:

>>> 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 range i a list to, że a range jest leniwym lub dynamicznym ciągiem; nie pamięta wszystkich swoich wartości, tylko pamięta swoje start, stop, i step, i tworzy wartości na żądanie na __getitem__.

(na marginesie, jeśli print(iter(a)), zauważysz, że range używa tego samego typu listiterator, co list. Jak to działa? A listiterator nie używa niczego specjalnego w list z wyjątkiem faktu, że dostarcza implementację C __getitem__, więc działa dobrze dla range też.)

Teraz, nie ma nic, co mówi, że Sequence.__contains__ musi być stały czas-w rzeczywistości, dla oczywistych przykładów sekwencji, takich jak list, nie jest. ale nie ma nic, co mówi, że nie może {46]} być. I łatwiej jest zaimplementowaćrange.__contains__ po prostu sprawdzić to matematycznie ((val - start) % step, ale z pewną dodatkową złożonością do radzenia sobie z negatywnymi krokami) niż faktycznie generować i testować wszystkie wartości, więc dlaczego nie powinno to robić lepiej?

Ale nie wydaje się być wszystko, co w języku gwarantuje to się stanie. Jak podkreśla Ashwini Chaudhari, jeśli nadasz jej wartość nieintegralną, zamiast przekształcić ją w liczbę całkowitą i wykonać test matematyczny, powróci do iteracji wszystkich wartości i porównania ich jeden po drugim. I tylko dlatego, że CPython 3.2+ i PyPy 3.wersje x zawierają tę optymalizację i jest to oczywisty dobry pomysł i łatwy do zrobienia, nie ma powodu, aby IronPython lub NewKickAssPython 3.x couldn ' t leave it Wynocha. (A w rzeczywistości CPython 3.0-3.1 nie zawierał tego.)

Gdyby range rzeczywiście były generatorem, jak my_crappy_range, to testowanie __contains__ w ten sposób nie miałoby sensu, a przynajmniej sposób, w jaki to ma sens, nie byłby oczywisty. Jeśli już iterowałeś pierwsze 3 wartości, to czy 1 nadal in jest generatorem? Czy testowanie dla 1 spowoduje iterację i pochłonie wszystkie wartości do 1 (lub do pierwszej wartości >= 1)?

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

W Cpythonie, range(...).__contains__ (wrapper metody)ostatecznie deleguje się do prostego obliczenia, które sprawdza, czy wartość może być w zakresie. Powodem prędkości jest to, że używamy matematycznego rozumowania o granicach, a nie bezpośredniej iteracji obiektu range. Aby wyjaśnić zastosowaną logikę:

1. sprawdź, czy liczba jest pomiędzy start i stop, oraz
2. sprawdź, czy wartość kroku nie "step over" nasz numer.

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

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

Pełny kod C znajduje się poniżej, co jest nieco bardziej wyraziste ze względu na zarządzanie pamięcią i szczegóły zliczania odniesień, ale podstawowa idea jest tam:

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" idei jest wymienione w linii :

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

Jako ostatnia uwaga-spójrz na funkcję range_contains u dołu fragmentu kodu. Jeśli dokładne sprawdzenie typu nie powiedzie się, wtedy 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 interpreterze (używam tutaj 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)

Aby dodać do odpowiedzi Martijna, jest to odpowiednia część źródła (W C, ponieważ obiekt range jest napisany 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);
}

Tak więc dla obiektów PyLong (co jest {[3] } w Pythonie 3), będzie on używał funkcji range_contains_long do określenia wyniku. I ta funkcja zasadniczo sprawdza, czy ob znajduje się w podanym zakresie (chociaż w C wygląda to nieco bardziej skomplikowanie).

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

Całą logikę można by 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 ta optymalizacja została dodana do range.__contains__, a dlaczego nie została dodana do w 2.7:

Po pierwsze, jak odkrył Ashwini Chaudhary, numer 1766304 został otwarty jawnie, aby zoptymalizować [x]range.__contains__. Patch do tego został zaakceptowany i sprawdzony dla 3.2, ale nie został ponownie przeniesiony do 2.7, ponieważ " xrange zachowywał się tak przez tak długi czas, że nie widzę, co kupi nam zatwierdzenie patcha tak późno."(2.7 było prawie na tym punkt.)

Tymczasem:

Pierwotnie, xrange był obiektem niezupełnie sekwencyjnym. Jak 3.1 docs mówią:

Obiekty Range zachowują się bardzo słabo: obsługują tylko indeksowanie, iterację i funkcję len.

To nie do końca prawda; obiekt xrange faktycznie obsługiwał kilka innych rzeczy, które przychodzą automatycznie z indeksowaniem i len,^* W tym __contains__ (poprzez wyszukiwanie liniowe). Ale nikt nie pomyślał, że warto je robić pełne sekwencje w tym czasie.

Następnie, w ramach implementacji abstrakcyjnych klas bazowych PEP, ważne było, aby dowiedzieć się, które typy wbudowane powinny być oznaczone jako implementujące które ABCs i xrange/range twierdził, że zaimplementował collections.Sequence, mimo że nadal obsługiwał tylko to samo "bardzo małe zachowanie". Nikt nie zauważył tego problemu, dopóki numer 9213 . Łatka do tego problemu nie tylko dodała index i count do 3.2 range, ale także ponownie zadziałała zoptymalizowana __contains__ (która dzieli tę samą matematykę z index i jest bezpośrednio używana przez count).^**ta zmiana weszła również na 3.2 i nie została przeniesiona do 2.x, ponieważ "jest to poprawka, która dodaje nowe metody". (W tym momencie, 2.7 był już po RC status.)

Były dwie szanse na przywrócenie tej optymalizacji do 2.7, ale obie zostały odrzucone.

_{* w rzeczywistości otrzymujesz nawet iterację za darmo z len i indeksowaniem, ale w 2.3 xrange obiekty mają własny iterator. Który następnie przegrali w 3.x, który używa tego samego typu listiterator co list.}

_{** pierwsza wersja faktycznie go zaimplementowała i pomyliła szczegóły-np. dałaby Ci MyIntSubclass(2) in range(5) == False. Jednak zaktualizowana wersja poprawki Daniela Stutzbacha przywróciła większość poprzedniego kodu, włączając w to powrót do ogólnego, powolnego _PySequence_IterSearch, którego przed 3.2 range.__contains__ domyślnie używała, gdy optymalizacja nie ma zastosowania.}

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

>>> 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 range jest obiektem, który zapamiętuje swój zakres i może być używany wiele razy( nawet podczas iteracji nad nim), a nie tylko jednorazowym generatorem.

Chodzi o leniwe podejście do oceny i dodatkową optymalizację range. Wartości w zakresach nie muszą być obliczane do rzeczywistego użycia, a nawet dalsze ze względu na dodatkową optymalizację.

Przy okazji twoja liczba całkowita nie jest taka duża, rozważ sys.maxsize

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

Ze względu na optymalizację - łatwo porównać daną liczbę całkowitą tylko z min i max zakresu.

Ale:

float(sys.maxsize) in range(sys.maxsize) jest dość powolny .

(w tym przypadku nie ma optymalizacji w range, więc ponieważ otrzymamy nieoczekiwany float, python porówna wszystkie liczby)