Dlaczego pętla nad zakresem () w Pythonie jest szybsza niż użycie pętli while?

81

Któregoś dnia robiłem testy porównawcze Pythona i znalazłem coś interesującego. Poniżej znajdują się dwie pętle, które robią mniej więcej to samo. Wykonanie pętli 1 trwa około dwa razy dłużej niż pętli 2.

Pętla 1:

int i = 0
while i < 100000000:
  i += 1

Pętla 2:

for n in range(0,100000000):
  pass

Dlaczego pierwsza pętla jest o wiele wolniejsza? Wiem, że to trywialny przykład, ale wzbudził moje zainteresowanie. Czy jest coś szczególnego w funkcji range (), która czyni ją bardziej wydajną niż zwiększanie zmiennej w ten sam sposób?

A. Dorton
źródło

Odpowiedzi:

159

zobacz demontaż kodu bajtowego Pythona, możesz uzyskać bardziej konkretny pomysł

użyj pętli while:

1           0 LOAD_CONST               0 (0)
            3 STORE_NAME               0 (i)

2           6 SETUP_LOOP              28 (to 37)
      >>    9 LOAD_NAME                0 (i)              # <-
           12 LOAD_CONST               1 (100000000)      # <-
           15 COMPARE_OP               0 (<)              # <-
           18 JUMP_IF_FALSE           14 (to 35)          # <-
           21 POP_TOP                                     # <-

3          22 LOAD_NAME                0 (i)              # <-
           25 LOAD_CONST               2 (1)              # <-
           28 INPLACE_ADD                                 # <-
           29 STORE_NAME               0 (i)              # <-
           32 JUMP_ABSOLUTE            9                  # <-
      >>   35 POP_TOP
           36 POP_BLOCK

Korpus pętli ma 10 op

zakres zastosowania:

1           0 SETUP_LOOP              23 (to 26)
            3 LOAD_NAME                0 (range)
            6 LOAD_CONST               0 (0)
            9 LOAD_CONST               1 (100000000)
           12 CALL_FUNCTION            2
           15 GET_ITER
      >>   16 FOR_ITER                 6 (to 25)        # <-
           19 STORE_NAME               1 (n)            # <-

2          22 JUMP_ABSOLUTE           16                # <-
      >>   25 POP_BLOCK
      >>   26 LOAD_CONST               2 (None)
           29 RETURN_VALUE

Korpus pętli ma 3 op

Czas uruchomienia kodu w C jest znacznie krótszy niż w przypadku interpretera i można go zignorować.

kcwu
źródło
2
W rzeczywistości korpus pętli w pierwszym demontażu ma 10 operacji (skok z pozycji 32 do 9). W obecnej implementacji CPythona interpretacja każdego kodu bajtowego skutkuje dość dużym prawdopodobieństwem w kosztownym odgałęzieniu pośrednim błędnie przewidzianym w CPU (skok do implementacji następnego kodu bajtowego). Jest to konsekwencja obecnej implementacji CPythona, JIT są wdrażane przez pustą jaskółkę, PyPy i inne najprawdopodobniej stracą ten narzut. Najlepsi z nich będą również w stanie specjalizować się w typach, aby przyspieszyć o rząd wielkości.
Ants Aasma
5
użyj modułu "dis". Zdefiniuj swój kod w funkcji, a następnie wywołaj dis.disco (func .__ code__)
kcwu
Czy należałoby zatem powiedzieć, że na wyższym poziomie whilepętla musi wykonać porównanie każdej iteracji?
davidhood2
35

range() jest zaimplementowany w C, podczas gdy i += 1 jest interpretowany.

Używanie xrange()może sprawić, że będzie to jeszcze szybsze w przypadku dużych liczb. Począwszy od Pythona 3.0 range()przebiega tak samo, jak poprzednio xrange().

Georg Schölly
źródło
15

Trzeba powiedzieć, że w pętli while odbywa się wiele tworzenia i niszczenia obiektów.

i += 1

jest taki sam jak:

i = i + 1

Ale ponieważ inte Pythona są niezmienne, nie modyfikuje istniejącego obiektu; raczej tworzy zupełnie nowy przedmiot o nowej wartości. To w zasadzie:

i = new int(i + 1)   # Using C++ or Java-ish syntax

Odśmiecacz będzie miał również dużo do wyczyszczenia. „Tworzenie obiektów jest drogie”.

Piotr
źródło
4

Ponieważ częściej uruchamiasz kod napisany w języku C w interpretatorze. tj. i + = 1 jest w Pythonie, więc wolno (względnie), podczas gdy range (0, ...) to jedno wywołanie w C, pętla for będzie wykonywana również głównie w C.

John Montgomery
źródło
1

Większość wywołań metod wbudowanych w Pythonie jest uruchamianych jako kod C. Kod, który należy zinterpretować, jest znacznie wolniejszy. Pod względem wydajności pamięci i szybkości wykonywania różnica jest gigantyczna. Wewnętrzne elementy Pythona zostały maksymalnie zoptymalizowane i najlepiej jest skorzystać z tych optymalizacji.

drogi Boże
źródło
0

Myślę, że tutaj odpowiedź jest nieco bardziej subtelna niż sugerują inne odpowiedzi, chociaż jej istota jest poprawna: pętla for jest szybsza, ponieważ więcej operacji odbywa się w C, a mniej w Pythonie .

Mówiąc dokładniej, w przypadku pętli for w C zachodzą dwie rzeczy, które w pętli while są obsługiwane w Pythonie:

  1. W pętli while porównanie i < 100000000jest wykonywane w Pythonie, podczas gdy w pętli for zadanie jest przekazywane do iteratora programu range(100000000), który wewnętrznie wykonuje iterację (a zatem sprawdza granice) w C.

  2. W pętli while aktualizacja pętli i += 1odbywa się w Pythonie, podczas gdy w pętli for ponownie iterator range(100000000), napisany w C, wykonuje i+=1(lub ++i).

Widzimy, że jest to połączenie obu tych rzeczy, które przyspiesza pętlę for, dodając je ręcznie, aby zobaczyć różnicę.

import timeit

N = 100000000


def while_loop():
    i = 0
    while i < N:
        i += 1


def for_loop_pure():
    for i in range(N):
        pass


def for_loop_with_increment():
    for i in range(N):
        i += 1


def for_loop_with_test():
    for i in range(N):
        if i < N: pass


def for_loop_with_increment_and_test():
    for i in range(N):
        if i < N: pass
        i += 1


def main():
    print('while loop\t\t', timeit.timeit(while_loop, number=1))
    print('for pure\t\t', timeit.timeit(for_loop_pure, number=1))
    print('for inc\t\t\t', timeit.timeit(for_loop_with_increment, number=1))
    print('for test\t\t', timeit.timeit(for_loop_with_test, number=1))
    print('for inc+test\t', timeit.timeit(for_loop_with_increment_and_test, number=1))


if __name__ == '__main__':
    main()

Próbowałem tego zarówno z liczbą 100000000 jako stałą, jak i zmienną, Nco byłoby bardziej typowe.

# inline constant N
while loop      3.5131139
for pure        1.3211338000000001
for inc         3.5477727000000003
for test        2.5209639
for inc+test    4.697028999999999

# variable N
while loop      4.1298240999999996
for pure        1.3526357999999998
for inc         3.6060175
for test        3.1093069
for inc+test    5.4753364

Jak widać, w obu przypadkach whileczas jest bardzo zbliżony do różnicy for inc+testi for pure. Zauważ również, że w przypadku, gdy używamy Nzmiennej, whilema dodatkowe spowolnienie w celu wielokrotnego sprawdzania wartości N, ale fornie.

To naprawdę szalone, że takie trywialne modyfikacje mogą skutkować ponad 3-krotnym przyspieszeniem kodu , ale to właśnie Python dla Ciebie. I nawet nie zaczynaj od tego, kiedy w ogóle możesz użyć wbudowanego na pętli ....

mCoding
źródło