Sind Tupel effizienter als Listen in Python?

Gibt es Leistungsunterschiede zwischen Tupeln und Listen beim Instanziieren und Abrufen von Elementen?

Das disModul zerlegt den Bytecode für eine Funktion und ist nützlich, um den Unterschied zwischen Tupeln und Listen zu erkennen.

In diesem Fall können Sie sehen, dass der Zugriff auf ein Element identischen Code generiert, das Zuweisen eines Tupels jedoch viel schneller ist als das Zuweisen einer Liste.

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

Im Allgemeinen können Sie erwarten, dass Tupel etwas schneller sind. Sie sollten jedoch auf jeden Fall Ihren speziellen Fall testen (wenn der Unterschied die Leistung Ihres Programms beeinträchtigen könnte - denken Sie daran, dass "vorzeitige Optimierung die Wurzel allen Übels ist").

Python macht das sehr einfach: timeit ist dein Freund.

$ 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

und...

$ 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

In diesem Fall ist die Instanziierung für das Tupel fast eine Größenordnung schneller, aber der Elementzugriff ist für die Liste tatsächlich etwas schneller! Wenn Sie also einige Tupel erstellen und viele Male darauf zugreifen, ist es möglicherweise schneller, stattdessen Listen zu verwenden.

Wenn Sie ein Element ändern möchten , ist die Liste natürlich schneller, da Sie ein ganz neues Tupel erstellen müssen, um ein Element davon zu ändern (da Tupel unveränderlich sind).

Zusammenfassung

Tupel schneiden in fast jeder Kategorie besser ab als Listen :

1) Tupel können konstant gefaltet werden .

2) Tupel können wiederverwendet anstatt kopiert werden.

3) Tupel sind kompakt und nicht zu viel zugeordnet.

4) Tupel verweisen direkt auf ihre Elemente.

Tupel können konstant gefaltet werden

Tupel von Konstanten können mit Pythons Gucklochoptimierer oder AST-Optimierer vorberechnet werden. Listen hingegen werden von Grund auf neu erstellt:

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

Tupel müssen nicht kopiert werden

Running tuple(some_tuple)kehrt sofort selbst zurück. Da Tupel unveränderlich sind, müssen sie nicht kopiert werden:

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

Im Gegensatz dazu list(some_list)müssen alle Daten in eine neue Liste kopiert werden:

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

Tupel werden nicht überbelegt

Da die Größe eines Tupels festgelegt ist, kann es kompakter gespeichert werden als Listen, die überbelegt werden müssen, um append () -Operationen effizient zu gestalten.

Dies gibt Tupeln einen schönen Platzvorteil:

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

Hier ist der Kommentar von Objects / listobject.c , der erklärt, was Listen tun:

/* 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.
 */

Tupel beziehen sich direkt auf ihre Elemente

Verweise auf Objekte werden direkt in ein Tupelobjekt aufgenommen. Im Gegensatz dazu verfügen Listen über eine zusätzliche Indirektionsebene für ein externes Array von Zeigern.

Dies gibt Tupeln einen kleinen Geschwindigkeitsvorteil für indizierte Suchvorgänge und das Auspacken:

$ 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

So wird das Tupel (10, 20)gespeichert:

    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;

So wird die Liste [10, 20]gespeichert:

    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;

Beachten Sie, dass das Tupelobjekt die beiden Datenzeiger direkt enthält, während das Listenobjekt eine zusätzliche Indirektionsebene zu einem externen Array aufweist, das die beiden Datenzeiger enthält.

Da Tupel unveränderlich sind, sind sie speichereffizienter. listet aus Effizienzgründen den Speicher insgesamt auf, um Anhänge ohne Konstante reallocs zu ermöglichen . Wenn Sie also eine konstante Folge von Werten in Ihrem Code durchlaufen möchten (z. B. for direction in 'up', 'right', 'down', 'left':), werden Tupel bevorzugt, da solche Tupel in der Kompilierungszeit vorberechnet werden.

Die Zugriffsgeschwindigkeiten sollten gleich sein (beide werden als zusammenhängende Arrays im Speicher gespeichert).

Aber, alist.append(item)ist viel zu bevorzugen , atuple+= (item,)wenn Sie mit veränderbaren Daten umgehen. Denken Sie daran, dass Tupel als Datensätze ohne Feldnamen behandelt werden sollen.

Sie sollten das arrayModul auch in der Standardbibliothek berücksichtigen, wenn alle Elemente in Ihrer Liste oder Ihrem Tupel vom gleichen C-Typ sind. Es benötigt weniger Speicher und kann schneller sein.

Hier ist ein weiterer kleiner Maßstab, nur um es zu tun.

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)

Lassen Sie uns diese herausrechnen:

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

Man kann es fast nicht schlüssig nennen.

Aber sicher, Tupel haben sich im Vergleich zu Listen 101.239%die Zeit oder 1.239%zusätzliche Zeit genommen, um die Arbeit zu erledigen.

Tupel sollten etwas effizienter und deshalb schneller sein als Listen, weil sie unveränderlich sind.

Der Hauptgrund dafür, dass Tuple sehr effizient liest, ist, dass es unveränderlich ist.

Warum sind unveränderliche Objekte leicht zu lesen?

Der Grund dafür ist, dass Tupel im Gegensatz zu Listen im Speichercache gespeichert werden können. Das Programm liest immer aus dem Speicherort der Liste, da es veränderbar ist (kann sich jederzeit ändern).