it-swarm-eu.dev

Sind Tupel effizienter als Listen in Python?

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

191
Readonly

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

In diesem Fall sehen Sie, dass beim Zugriff auf ein Element derselbe Code generiert wird, dass 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
152
Mark Harrison

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

Mit Python ist das ganz 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 ein paar 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 auf jeden Fall schneller, da Sie ein ganz neues Tupel erstellen müssen, um ein Element zu ändern (da Tupel unveränderlich sind) ).

194
dF.

Zusammenfassung

Tupel schneiden in fast jeder Kategorie besser ab als Listen :

1) Tupel können konstant gefaltet sein.

2) Tupel können wiederverwendet anstatt kopiert werden.

3) Tupel sind kompakt und weisen keine Überbelegung auf.

4) Tupel verweisen direkt auf ihre Elemente.

Tupel können konstant gefaltet werden

Konstantentupel können mit Pythons Gucklochoptimierer oder AST-Optimierer vorberechnet werden. Listen werden dagegen von Grund auf neu aufgebaut:

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

Das Ausführen von Tuple(some_Tuple) gibt sich 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 erfordert list(some_list), dass 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 übermäßig zugeordnet werden müssen, um append () - Operationen effizienter zu gestalten.

Dies gibt Tupeln einen schönen Raumvorteil:

>>> 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 verweisen direkt auf ihre Elemente

Verweise auf Objekte werden direkt in ein Tupel-Objekt eingefügt. Im Gegensatz dazu verfügen Listen über eine zusätzliche Indirektionsebene für ein externes Array von Zeigern.

Dies gibt Tupeln einen kleinen Geschwindigkeitsvorteil beim indizierten Nachschlagen und Entpacken:

$ 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

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

Hier 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 Tuple-Objekt die beiden Datenzeiger direkt einbezieht, während das Listenobjekt eine zusätzliche Indirektionsebene für ein externes Array aufweist, das die beiden Datenzeiger enthält.

166

Da Tupel unveränderlich sind, sind sie speichereffizienter. Listet aus Effizienzgründen den gesamten Speicher auf, um Anhänge ohne konstante reallocs zuzulassen. 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 atuple+= (item,) weit vorzuziehen, wenn Sie mit veränderlichen Daten arbeiten. Beachten Sie, dass Tupel als Datensätze ohne Feldnamen behandelt werden sollen.

31
tzot

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

9
Ralph Corderoy

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

4
ctcherry

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

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 heraus mitteln:

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 klar, Tupel haben 101.239% die Zeit oder 1.239% mehr Zeit für die Ausführung der Arbeit im Vergleich zu Listen.

3
Dev Aggarwal