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

2111

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.

Rick wspiera Monikę
źródło
70
Zauważ, że dzieje się tak tylko wtedy, gdy sprawdzany element to a boollub longtyp, w przypadku innych typów obiektów zwariuje. Spróbuj z:100000000000000.0 in range(1000000000000001)
Ashwini Chaudhary
10
Kto ci powiedział, że rangeto generator?
abarnert
7
@abarnert Myślę, że dokonana przeze mnie zmiana pozostawiła zamieszanie nietknięta.
Rick wspiera Monikę
5
@AshwiniChaudhary nie jest Python2 xrangetaki sam jak Python3range ?
Superbest
28
@Najlepsze xrange()obiekty nie mają __contains__metody, więc sprawdzanie elementów musi przebiegać przez wszystkie elementy. Dodatkowo istnieje kilka innych zmian range(), jak obsługuje krojenie (który ponownie zwraca rangeobiekt) i teraz też ma counti indexmetody, aby był kompatybilny z collections.SequenceABC.
Ashwini Chaudhary

Odpowiedzi:

2167

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.

Martijn Pieters
źródło
58
Ciekawostka: ponieważ masz działającą implementację __getitem__i __len__, __iter__implementacja jest w rzeczywistości niepotrzebna.
Lucretiel
2
@ Lucretiel: W Pythonie 2.3xrangeiterator dodano specjalną wersję , ponieważ nie była wystarczająco szybka. A potem gdzieś w 3.x (nie jestem pewien, czy to był 3.0 czy 3.2) został odrzucony i używają tego samego listiteratortypu, który listużywa.
abarnert
1
Zdefiniowałbym konstruktora jako def __init__(self, *start_stop_step)i parsowałbym go stamtąd; sposób, w jaki argumenty są teraz oznaczane, jest nieco mylący. Niemniej jednak +1; nadal zdecydowanie wyjaśniłeś zachowanie.
Cody Piersall
1
@CodyPiersall: Niestety, jest to podpis inicjalizatora klasy prawdziwej. rangejest starszy niż *args(znacznie mniej argclinicAPI, który pozwala funkcjom C-API mieć pełne podpisy w języku Python). Kilka innych starych funkcje (i kilka nowsze funkcje, jak xrange, slicei itertools.islice, dla konsystencji) działają tak samo, ale w przeważającej części, Guido i reszta deweloperów podstawowych wydaje się z tobą zgodzić. Dokumenty w wersji 2.0+ opisują nawet rangeznajomych, jakby były przeciążeniem w stylu C ++, zamiast pokazywać mylący podpis.
abarnert
2
@CodyPiersall: Tak naprawdę, oto cytat z argclinicdyskusji Guido , kiedy Nick Coghlan wymyślił sposób rangejednoznacznego zdefiniowania : „Nie ułatwiaj ludziom kopiowania mojej najgorszej decyzji projektowej”. Jestem więc prawie pewien, że zgadza się, że rangejest to mylące, jak napisano.
abarnert
843

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

abarnert
źródło
10
Jest to bardzo ważna rzecz, aby wyjaśnić. Przypuszczam, że różnice między Pythonem 2 i 3 mogły prowadzić do mojego zamieszania w tej kwestii. W każdym razie powinienem był zauważyć, że rangejest wymieniony (wraz z listi tuple) jako typ sekwencji .
Rick wspiera Monikę
4
@RickTeachey: W rzeczywistości w wersji 2.6+ (myślę, może 2.5+) xrangejest też sekwencją. Zobacz dokumenty 2.7 . W rzeczywistości zawsze była to prawie sekwencja.
abarnert
5
@RickTeachey: Właściwie się myliłem; w wersjach 2.6-2.7 (i 3.0-3.1) twierdzi, że jest sekwencją, ale wciąż jest to prawie sekwencja. Zobacz moją drugą odpowiedź.
abarnert
2
To nie jest iterator, to sekwencja (iterowalna pod względem Java, IEnumerable C #) - coś z .__iter__()metodą, która zwróci iterator. Z kolei można go użyć tylko raz.
Smit Johnth,
4
@ThomasAhle: Ponieważ rangenie sprawdza typów, gdy nie jest liczbą całkowitą, ponieważ zawsze jest możliwe, że typ __eq__jest zgodny z int. Pewnie,str oczywiście nie zadziała, ale nie chcieli spowolnić rzeczy poprzez jawne sprawdzenie wszystkich typów, które nie mogą tam być (a przecież strpodklasa mogłaby zastąpić __eq__i być zawarta w range).
ShadowRanger,
377

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)
wim
źródło
144

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
szturchać
źródło
11
@ChrisWesseling: Myślę, że jest to wystarczająco inna informacja (i dość jej), że edytowanie odpowiedzi Martijna nie byłoby tutaj odpowiednie. To wezwanie do osądu, ale ludzie zwykle mylą się, nie wprowadzając drastycznych zmian w odpowiedziach innych ludzi.
abarnert
105

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.

abarnert
źródło
4
Z komentarzy tutaj: poprawxrange.__contains__ , wygląda na to, że nie dokonali backportowania go do Pythona 2, aby zostawić element zaskoczenia dla użytkowników i było już za późno. countI index plaster dodano później. Plik w tym czasie: hg.python.org/cpython/file/d599a3f2e72d/Objects/rangeobject.c
Chaudhary
12
Mam złowrogie podejrzenie, że niektórzy deweloperzy Pythona są stronniczi wobec „twardej miłości” do Pythona 2.x, ponieważ chcą zachęcić ludzi do przejścia na znacznie lepszego python3 :)
wim
4
Założę się, że dodanie nowych funkcji do starych wersji jest ogromnym obciążeniem. Wyobraź sobie, że poszedłeś do Oracle i powiedziałeś: „Słuchaj, korzystam z Java 1.4 i zasłużyłem na wyrażenia lambda! Zaportuj je za darmo”.
Rob Grant,
2
@RickTeachey tak, to tylko przykład. Gdybym powiedział 1.7, nadal by to miało zastosowanie. To różnica ilościowa, a nie jakościowa. Zasadniczo (nieopłacani) deweloperzy nie mogą wiecznie tworzyć fajnych nowych rzeczy w wersji 3.x i przenieść je do wersji 2.x dla tych, którzy nie chcą aktualizacji. To ogromny i absurdalny ciężar. Czy uważasz, że nadal coś jest nie tak z moim rozumowaniem?
Rob Grant,
3
@RickTeachey: 2,7 było między 3,1 a 3,2, a nie około 3,3. A to oznacza, że ​​2.7 był w wersji rc, kiedy weszły ostatnie zmiany w wersji 3.2, co ułatwia zrozumienie komentarzy na temat błędów. W każdym razie myślę, że popełnili kilka błędów z perspektywy czasu (zwłaszcza zakładając, że ludzie przeprowadzą migrację 2to3zamiast za pomocą podwójnego kodu przy pomocy bibliotek takich jak six, dlatego dostaliśmy takie rzeczy, dict.viewkeysktórych nikt nigdy nie użyje), i były kilka zmian, które pojawiły się zbyt późno w wersji 3.2, ale w przeważającej części 2.7 było imponującą wersją „ostatniej wersji 2.x”.
abarnert
47

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.

Stefan Pochmann
źródło
27

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.

Sławomir Lenart
źródło
4
Uważaj na pływające duże liczby całkowite. float(sys.maxsize) != sys.maxsize)Mimo to na większości maszyn sys.maxsize-float(sys.maxsize) == 0.
holdenweb,
18

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

RBF06
źródło
0
  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.

Naruto
źródło
1
Czy możesz udostępnić źródło tego? Nawet jeśli to zabrzmi legalnie, dobrze byłoby poprzeć te roszczenia faktycznym kodem
Nico Haase,
Myślę, że jest to przykład tego, który można wdrożyć. Nie jest to dokładny sposób implementacji. Chociaż nie podano żadnego odniesienia, jest to dobra wskazówka wystarczająco dobra, aby zrozumieć, dlaczego sprawdzanie włączenia dla zasięgu może być znacznie szybsze niż lista lub krotka
Mohammed Shareef C
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.

Benjimin
źródło