Czy krotki są bardziej wydajne niż listy w Pythonie?

Czy istnieje różnica w wydajności między krotkami i listami, jeśli chodzi o tworzenie instancji i pobieranie elementów?

disModuł demontuje kodu bajtowego dla funkcji i jest przydatna, aby zobaczyć różnicę między krotki i list.

W tym przypadku widać, że dostęp do elementu generuje identyczny kod, ale przypisanie krotki jest znacznie szybsze niż przypisanie listy.

>>> def a():
...     x=[1,2,3,4,5]
...     y=x[2]
...
>>> def b():
...     x=(1,2,3,4,5)
...     y=x[2]
...
>>> import dis
>>> dis.dis(a)
  2           0 LOAD_CONST               1 (1)
              3 LOAD_CONST               2 (2)
              6 LOAD_CONST               3 (3)
              9 LOAD_CONST               4 (4)
             12 LOAD_CONST               5 (5)
             15 BUILD_LIST               5
             18 STORE_FAST               0 (x)

  3          21 LOAD_FAST                0 (x)
             24 LOAD_CONST               2 (2)
             27 BINARY_SUBSCR
             28 STORE_FAST               1 (y)
             31 LOAD_CONST               0 (None)
             34 RETURN_VALUE
>>> dis.dis(b)
  2           0 LOAD_CONST               6 ((1, 2, 3, 4, 5))
              3 STORE_FAST               0 (x)

  3           6 LOAD_FAST                0 (x)
              9 LOAD_CONST               2 (2)
             12 BINARY_SUBSCR
             13 STORE_FAST               1 (y)
             16 LOAD_CONST               0 (None)
             19 RETURN_VALUE

Ogólnie można oczekiwać, że krotki będą nieco szybsze. Jednak zdecydowanie powinieneś przetestować konkretny przypadek (jeśli różnica może wpłynąć na wydajność twojego programu - pamiętaj, że „przedwczesna optymalizacja jest źródłem wszelkiego zła”).

Python sprawia, że ​​jest to bardzo łatwe: timeit jest twoim przyjacielem.

$ python -m timeit "x=(1,2,3,4,5,6,7,8)"
10000000 loops, best of 3: 0.0388 usec per loop

$ python -m timeit "x=[1,2,3,4,5,6,7,8]"
1000000 loops, best of 3: 0.363 usec per loop

i...

$ python -m timeit -s "x=(1,2,3,4,5,6,7,8)" "y=x[3]"
10000000 loops, best of 3: 0.0938 usec per loop

$ python -m timeit -s "x=[1,2,3,4,5,6,7,8]" "y=x[3]"
10000000 loops, best of 3: 0.0649 usec per loop

Tak więc w tym przypadku tworzenie krotki jest prawie o rząd wielkości szybsze dla krotki, ale dostęp do przedmiotów jest w rzeczywistości nieco szybszy dla listy! Jeśli więc tworzysz kilka krotek i uzyskujesz do nich dostęp wiele razy, użycie list może być szybsze.

Oczywiście, jeśli chcesz zmienić element, lista będzie zdecydowanie szybsza, ponieważ musisz utworzyć zupełnie nową krotkę, aby zmienić jeden element (ponieważ krotek są niezmienne).

Podsumowanie

Krotki mają zwykle lepsze wyniki niż listy w prawie każdej kategorii:

1) Krotki można składać na stałe .

2) Krotki można ponownie wykorzystać zamiast kopiować.

3) Krotki są kompaktowe i nie nadmiernie przydzielają.

4) Krotki odnoszą się bezpośrednio do swoich elementów.

Krotki można składać na stałe

Krotki stałych mogą być wstępnie obliczone przez optymalizator wizjera Pythona lub optymalizator AST. Z drugiej strony listy są tworzone od zera:

    >>> from dis import dis

    >>> dis(compile("(10, 'abc')", '', 'eval'))
      1           0 LOAD_CONST               2 ((10, 'abc'))
                  3 RETURN_VALUE   

    >>> dis(compile("[10, 'abc']", '', 'eval'))
      1           0 LOAD_CONST               0 (10)
                  3 LOAD_CONST               1 ('abc')
                  6 BUILD_LIST               2
                  9 RETURN_VALUE 

Krotki nie muszą być kopiowane

Uruchomienie tuple(some_tuple)natychmiast wraca. Ponieważ krotki są niezmienne, nie trzeba ich kopiować:

>>> a = (10, 20, 30)
>>> b = tuple(a)
>>> a is b
True

Z drugiej strony list(some_list)wymaga skopiowania wszystkich danych na nową listę:

>>> a = [10, 20, 30]
>>> b = list(a)
>>> a is b
False

Krotki nie przydzielają nadmiernie

Ponieważ rozmiar krotki jest stały, może być przechowywany w bardziej zwarty sposób niż listy, które muszą zostać nadmiernie przydzielone, aby operacje append () były wydajne.

Daje to krotkom niezłą przewagę przestrzenną:

>>> import sys
>>> sys.getsizeof(tuple(iter(range(10))))
128
>>> sys.getsizeof(list(iter(range(10))))
200

Oto komentarz Objects / listobject.c, który wyjaśnia, co robią listy:

/* This over-allocates proportional to the list size, making room
 * for additional growth.  The over-allocation is mild, but is
 * enough to give linear-time amortized behavior over a long
 * sequence of appends() in the presence of a poorly-performing
 * system realloc().
 * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
 * Note: new_allocated won't overflow because the largest possible value
 *       is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
 */

Krotki odnoszą się bezpośrednio do ich elementów

Odwołania do obiektów są wbudowane bezpośrednio w krotkę. Natomiast listy mają dodatkową warstwę pośrednią w stosunku do zewnętrznego zestawu wskaźników.

Daje to krotkom niewielką przewagę prędkości podczas indeksowanych wyszukiwań i rozpakowywania:

$ python3.6 -m timeit -s 'a = (10, 20, 30)' 'a[1]'
10000000 loops, best of 3: 0.0304 usec per loop
$ python3.6 -m timeit -s 'a = [10, 20, 30]' 'a[1]'
10000000 loops, best of 3: 0.0309 usec per loop

$ python3.6 -m timeit -s 'a = (10, 20, 30)' 'x, y, z = a'
10000000 loops, best of 3: 0.0249 usec per loop
$ python3.6 -m timeit -s 'a = [10, 20, 30]' 'x, y, z = a'
10000000 loops, best of 3: 0.0251 usec per loop

Oto jak (10, 20)przechowywana jest krotka :

    typedef struct {
        Py_ssize_t ob_refcnt;
        struct _typeobject *ob_type;
        Py_ssize_t ob_size;
        PyObject *ob_item[2];     /* store a pointer to 10 and a pointer to 20 */
    } PyTupleObject;

Oto jak [10, 20]przechowywana jest lista :

    PyObject arr[2];              /* store a pointer to 10 and a pointer to 20 */

    typedef struct {
        Py_ssize_t ob_refcnt;
        struct _typeobject *ob_type;
        Py_ssize_t ob_size;
        PyObject **ob_item = arr; /* store a pointer to the two-pointer array */
        Py_ssize_t allocated;
    } PyListObject;

Zauważ, że obiekt krotki zawiera dwa wskaźniki danych bezpośrednio, podczas gdy obiekt listy ma dodatkową warstwę pośrednią względem zewnętrznej tablicy zawierającej dwa wskaźniki danych.

Krotki, ponieważ są niezmienne, są bardziej wydajne pod względem pamięci; list, w celu zwiększenia wydajności, ogólnie przydziel pamięć, aby umożliwić dołączanie bez stałych reallocs. Tak więc, jeśli chcesz iterować przez stałą sekwencję wartości w swoim kodzie (np. for direction in 'up', 'right', 'down', 'left':), Krotki są preferowane, ponieważ takie krotki są wstępnie obliczane w czasie kompilacji.

Prędkości dostępu powinny być takie same (oba są przechowywane jako ciągłe tablice w pamięci).

Ale alist.append(item)jest znacznie bardziej preferowany, atuple+= (item,)gdy masz do czynienia ze zmiennymi danymi. Pamiętaj, że krotki mają być traktowane jako rekordy bez nazw pól.

Powinieneś również rozważyć arraymoduł w standardowej bibliotece, jeśli wszystkie elementy na liście lub krotce są tego samego typu C. Zajmie mniej pamięci i może być szybszy.

Oto kolejny mały wzorzec, dla samego dobra ..

In [11]: %timeit list(range(100))
749 ns ± 2.41 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [12]: %timeit tuple(range(100))
781 ns ± 3.34 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [1]: %timeit list(range(1_000))
13.5 µs ± 466 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [2]: %timeit tuple(range(1_000))
12.4 µs ± 182 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [7]: %timeit list(range(10_000))
182 µs ± 810 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [8]: %timeit tuple(range(10_000))
188 µs ± 2.38 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [3]: %timeit list(range(1_00_000))
2.76 ms ± 30.5 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [4]: %timeit tuple(range(1_00_000))
2.74 ms ± 31.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [10]: %timeit list(range(10_00_000))
28.1 ms ± 266 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [9]: %timeit tuple(range(10_00_000))
28.5 ms ± 447 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Uśrednijmy te:

In [3]: l = np.array([749 * 10 ** -9, 13.5 * 10 ** -6, 182 * 10 ** -6, 2.76 * 10 ** -3, 28.1 * 10 ** -3])

In [2]: t = np.array([781 * 10 ** -9, 12.4 * 10 ** -6, 188 * 10 ** -6, 2.74 * 10 ** -3, 28.5 * 10 ** -3])

In [11]: np.average(l)
Out[11]: 0.0062112498000000006

In [12]: np.average(t)
Out[12]: 0.0062882362

In [17]: np.average(t) / np.average(l)  * 100
Out[17]: 101.23946713590554

Możesz to nazwać prawie niejednoznaczne.

Ale na pewno krotki zajęły 101.239%czas lub 1.239%dodatkowy czas na wykonanie zadania w porównaniu do list.

Krotki powinny być nieco bardziej wydajne i dlatego szybsze niż listy, ponieważ są niezmienne.

Głównym powodem, dla którego Tuple jest bardzo wydajny w czytaniu, jest to, że jest niezmienny.

Dlaczego niezmienne obiekty są łatwe do odczytania?

Powodem jest to, że krotki mogą być przechowywane w pamięci podręcznej, w przeciwieństwie do list. Program zawsze odczytuje z pamięci miejsca listy, ponieważ jest zmienny (można go zmienić w dowolnym momencie).