Porównywanie zamiany list i pętli jawnych (3 generatory tablicowe szybsze niż 1 dla pętli)

Question

Zrobiłem pracę domową i przypadkowo odkryłem dziwną niespójność w szybkości algorytmu. Oto 2 wersje kodu o tej samej funkcji bur z 1 różnicą: w pierwszej wersji używam 3-krotnego generatora tablicowego do filtrowania pewnej tablicy, aw drugiej wersji używam 1 dla pętli z 3 instrukcjami if, aby wykonać tę samą pracę filtru.

Więc tutaj jest kod 1st wersji:

def kth_order_statistic(array, k): 
    pivot = (array[0] + array[len(array) - 1]) // 2 
    l = [x for x in array if x < pivot] 
    m = [x for x in array if x == pivot] 
    r = [x for x in array if x > pivot] 
    if k <= len(l): 
      return kth_order_statistic(l, k) 
    elif k > len(l) + len(m): 
      return kth_order_statistic(r, k - len(l) - len(m)) 
    else: 
      return m[0] 

A oto kod 2nd wersji:

def kth_order_statistic2(array, k): 
    pivot = (array[0] + array[len(array) - 1]) // 2 
    l = [] 
    m = [] 
    r = [] 
    for x in array: 
     if x < pivot: 
      l.append(x) 
     elif x > pivot: 
      r.append(x) 
     else: 
      m.append(x) 

    if k <= len(l): 
     return kth_order_statistic2(l, k) 
    elif k > len(l) + len(m): 
     return kth_order_statistic2(r, k - len(l) - len(m)) 
    else: 
     return m[0] 

wyjście ipython dla 1 wersji:

In [4]: %%timeit 
    ...: A = range(100000) 
    ...: shuffle(A) 
    ...: k = randint(1, len(A)-1) 
    ...: order_statisctic(A, k) 
    ...: 
10 loops, best of 3: 120 ms per loop 

a dla 2 wersja:

In [5]: %%timeit 
    ...: A = range(100000) 
    ...: shuffle(A) 
    ...: k = randint(1, len(A)-1) 
    ...: kth_order_statistic2(A, k) 
    ...: 
10 loops, best of 3: 169 ms per loop 

Dlaczego pierwsza wersja jest szybsza od drugiej? Zrobiłem także trzecią wersję, która używa funkcji filter() zamiast generatora tablicowego i była wolniejsza niż druga wersja (ma 218 ms na pętlę).

Answer 1

Zdefiniujmy funkcje będziemy musieli odpowiedzieć na pytanie i timeit nich

In [18]: def iter(): 
    l = [x for x in range(100) if x > 10] 
    ....: 

In [19]: %timeit iter() 
100000 loops, best of 3: 7.92 µs per loop 

In [20]: def loop(): 
    l = [] 
    for x in range(100): 
     if x > 10: 
      l.append(x) 
    ....: 

In [21]: %timeit loop() 
10000 loops, best of 3: 20 µs per loop 

In [22]: def loop_fast(): 
    l = [] 
    for x in range(100): 
     if x > 10: 
      pass 
    ....: 

In [23]: %timeit loop_fast() 
100000 loops, best of 3: 4.69 µs per loop 

widzimy, że pętle for bez polecenia append są tak szybkie jak zrozumienie listy. W rzeczywistości, jeśli mamy do obejrzenia kodu bajtowego widzimy, że w przypadku pytona listowych jest w stanie użyć polecenia wbudowanej kodu bajtowego nazwie LIST_APPEND zamiast:

• załadować listy: 40 LOAD_FAST
• obciążenia atrybut: 43 LOAD_ATTRIBUTE
• Wywołać funkcję załadowana: (?) 49 CALL_FUNCTION
• Unload lista: 52 POP_TOP

Jak widać z wyjścia poniżej poprzedniego kodu bajtowego są missin g ze zrozumieniem listy i funkcją "loop_fast". Porównanie czasu trzech funkcji jest jasne, że odpowiadają one za różne terminy trzech metod.

In [27]: dis.dis(iter) 
    2   0 BUILD_LIST    0 
      3 LOAD_GLOBAL   0 (range) 
      6 LOAD_CONST    1 (1) 
      9 LOAD_CONST    2 (100) 
      12 CALL_FUNCTION   2 
      15 GET_ITER 
     >> 16 FOR_ITER    24 (to 43) 
      19 STORE_FAST    0 (x) 
      22 LOAD_FAST    0 (x) 
      25 LOAD_CONST    2 (100) 
      28 COMPARE_OP    4 (>) 
      31 POP_JUMP_IF_FALSE  16 
      34 LOAD_FAST    0 (x) 
      37 LIST_APPEND   2 
      40 JUMP_ABSOLUTE   16 
     >> 43 STORE_FAST    1 (l) 
      46 LOAD_CONST    0 (None) 
      49 RETURN_VALUE 

In [28]: dis.dis(loop) 
    2   0 BUILD_LIST    0 
      3 STORE_FAST    0 (1) 

    3   6 SETUP_LOOP   51 (to 60) 
      9 LOAD_GLOBAL   0 (range) 
      12 LOAD_CONST    1 (1) 
      15 LOAD_CONST    2 (100) 
      18 CALL_FUNCTION   2 
      21 GET_ITER 
     >> 22 FOR_ITER    34 (to 59) 
      25 STORE_FAST    1 (x) 

    4   28 LOAD_FAST    1 (x) 
      31 LOAD_CONST    3 (10) 
      34 COMPARE_OP    4 (>) 
      37 POP_JUMP_IF_FALSE  22 

    5   40 LOAD_FAST    0 (l) 
      43 LOAD_ATTR    1 (append) 
      46 LOAD_FAST    1 (x) 
      49 CALL_FUNCTION   1 
      52 POP_TOP 
      53 JUMP_ABSOLUTE   22 
      56 JUMP_ABSOLUTE   22 
     >> 59 POP_BLOCK 
     >> 60 LOAD_CONST    0 (None) 
      63 RETURN_VALUE 

In [29]: dis.dis(loop_fast) 
    2   0 BUILD_LIST    0 
      3 STORE_FAST    0 (1) 

    3   6 SETUP_LOOP   38 (to 47) 
      9 LOAD_GLOBAL   0 (range) 
      12 LOAD_CONST    1 (1) 
      15 LOAD_CONST    2 (100) 
      18 CALL_FUNCTION   2 
      21 GET_ITER 
     >> 22 FOR_ITER    21 (to 46) 
      25 STORE_FAST    1 (x) 

    4   28 LOAD_FAST    1 (x) 
      31 LOAD_CONST    3 (10) 
      34 COMPARE_OP    4 (>) 
      37 POP_JUMP_IF_FALSE  22 

    5   40 JUMP_ABSOLUTE   22 
      43 JUMP_ABSOLUTE   22 
     >> 46 POP_BLOCK 
     >> 47 LOAD_CONST    0 (None) 
      50 RETURN_VALUE 

Answer 2

Używanie prostego for jest szybsze niż list comprehesion. Jest prawie 2 razy szybszy. Sprawdź poniżej wyników:

Korzystanie list comprehension: 58 usec

moin@moin-pc:~$ python -m timeit "[i for i in range(1000)]" 
10000 loops, best of 3: 58 usec per loop 

Korzystanie for pętla: 37,1 usec

moin@moin-pc:~$ python -m timeit "for i in range(1000): i" 
10000 loops, best of 3: 37.1 usec per loop 

Ale w twoim przypadku, for bierze więcej czasu niż listy ze zrozumieniem nie dlatego, że pętla YOVE for wolna. Ale z powodu .append() używasz w ramach kodu.

Z append() w for loop`: 114 usec

moin@moin-pc:~$ python -m timeit "my_list = []" "for i in range(1000): my_list.append(i)" 
10000 loops, best of 3: 114 usec per loop 

który wyraźnie pokazuje, że jest .append() który bierze dwukrotnie czasu potrzebnego for pętli.

Jednak na storing the "list.append" in different variable: 69,3 usec

moin@moin-pc:~$ python -m timeit "my_list = []; append = my_list.append" "for i in range(1000): append(i)" 
10000 loops, best of 3: 69.3 usec per loop 

Istnieje ogromna poprawa wydajności w porównaniu do ostatniego przypadku w powyższych porównań, a wynik jest dość porównywalna z list comprehension. Oznacza to, że zamiast wywoływać za każdym razem my_list.append(), wydajność można poprawić, przechowując referencję funkcji w innej zmiennej tj. append_func = my_list.append i wykonując połączenie, używając tej zmiennej append_func(i).

Co również dowodzi, że szybciej wywołuje funkcję klasy przechowywaną w zmiennej w porównaniu do bezpośredniego wywoływania funkcji za pomocą obiektu klasy.

Dziękuję Stefan za zwrócenie uwagi na ostatnią sprawę.

Answer 3

Struktura algorytmiczna różni się, a struktura warunkowa ma być obciążona. test do dodania do r i m może zostać odrzucony w poprzednim teście. Bardziej rygorystyczne porównanie dotyczące pętli for z append i listowego byłoby sprzeczne z nieoptymalnej poniżej

for x in array: 
     if x < pivot: 
      l.append(x) 
for x in array: 
     if x== pivot: 
      m.append(x) 
for x in array: 
     if x > pivot: 
      r.append(x) 

Answer 4

Załóżmy, że rozwieje wątpliwości: druga wersja jest nieco szybciej: listowego są szybsze, jeszcze dwie tablice przelotowe i aż warunkowe są odrzucane w jednej iteracji.

def kth_order_statistic1(array,k): 
    pivot = (array[0] + array[len(array) - 1]) // 2 
    l = [x for x in array if x < pivot] 
    m = [x for x in array if x == pivot] 
    r = [x for x in array if x > pivot] 

    if k <= len(l): 
     return kth_order_statistic1(l, k) 
    elif k > len(l) + len(m): 
     return kth_order_statistic1(r, k - len(l) - len(m)) 
    else: 
     return m[0] 


def kth_order_statistic2(array,k): 
    pivot = (array[0] + array[len(array) - 1]) // 2 
    l = [] 
    m = [] 
    r = [] 
    for x in array: 
     if x < pivot: 
      l.append(x) 
     elif x > pivot: 
      r.append(x) 
     else: 
      m.append(x) 

    if k <= len(l): 
     return kth_order_statistic2(l, k) 
    elif k > len(l) + len(m): 
     return kth_order_statistic2(r, k - len(l) - len(m)) 
    else: 
     return m[0] 

def kth_order_statistic3(array,k): 
    pivot = (array[0] + array[len(array) - 1]) // 2 
    l = [] 
    m = [] 
    r = [] 

    for x in array: 
     if x < pivot: l.append(x) 
    for x in array: 
     if x== pivot: m.append(x) 
    for x in array: 
     if x > pivot: r.append(x) 

    if k <= len(l): 
     return kth_order_statistic3(l, k) 
    elif k > len(l) + len(m): 
     return kth_order_statistic3(r, k - len(l) - len(m)) 
    else: 
     return m[0] 

import time 
import random 
if __name__ == '__main__': 

    A = range(100000) 
    random.shuffle(A) 
    k = random.randint(1, len(A)-1) 

    start_time = time.time() 
    for x in range(1000) : 
     kth_order_statistic1(A,k) 
    print("--- %s seconds ---" % (time.time() - start_time)) 

    start_time = time.time() 
    for x in range(1000) : 
     kth_order_statistic2(A,k) 
    print("--- %s seconds ---" % (time.time() - start_time)) 

    start_time = time.time() 
    for x in range(1000) : 
     kth_order_statistic3(A,k) 
    print("--- %s seconds ---" % (time.time() - start_time)) 

python : 
--- 25.8894710541 seconds --- 
--- 24.073086977 seconds --- 
--- 32.9823839664 seconds --- 

ipython 
--- 25.7450709343 seconds --- 
--- 22.7140650749 seconds --- 
--- 35.2958850861 seconds --- 

Czas może się różnić w zależności od losowania, ale różnice między trzema są prawie takie same.