Sind Tupel effizienter als Listen in Python?

225

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

Schreibgeschützt
quelle
9
Verwandte: "Warum ist Tupel schneller als Liste?"
Cristian Ciupitu
2
Wenn Sie an Speicher interessiert sind, der zwischen verschiedenen Typen verwendet wird, sehen Sie sich diese Darstellung an, die ich erstellt habe: stackoverflow.com/a/30008338/2087463
tmthydvnprt

Antworten:

172

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
Mark Harrison
quelle
66
Nur dass der gleiche Bytecode absolut generiert wird, bedeutet nicht, dass die gleichen Operationen auf der C- (und damit der CPU-) Ebene stattfinden. Versuchen Sie, eine Klasse ListLikemit einer Klasse zu erstellen __getitem__, die etwas schrecklich Langsames tut, und zerlegen Sie sie dann x = ListLike((1, 2, 3, 4, 5)); y = x[2]. Der Bytecode ähnelt eher dem obigen Tupelbeispiel als dem Listenbeispiel. Glauben Sie jedoch wirklich, dass die Leistung ähnlich ist?
Mzz
2
Sie sagen anscheinend, dass einige Typen effizienter sind als andere. Das ist sinnvoll, aber der Overhead von Listen- und Tupelgenerationen scheint orthogonal zum betreffenden Datentyp zu sein, mit der Einschränkung, dass es sich um Listen und Tupel desselben Datentyps handelt.
Mark Harrison
11
Die Anzahl der Bytecodes hat ebenso wie die Anzahl der Codezeilen wenig mit der Ausführungsgeschwindigkeit (und damit der Effizienz und Leistung) zu tun.
Martineau
18
Obwohl der Vorschlag, aus dem Zählen von Operationen etwas abzuleiten, falsch ist, zeigt dies den entscheidenden Unterschied: Konstante Tupel werden als solche im Bytecode gespeichert und nur bei Verwendung referenziert, während Listen zur Laufzeit erstellt werden müssen.
Poolie
6
Diese Antwort zeigt uns, dass Python Tupelkonstanten anerkennt. Das ist gut zu wissen! Aber was passiert, wenn versucht wird, ein Tupel oder eine Liste aus variablen Werten zu erstellen?
Tom
211

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

dF.
quelle
3
Mit welcher Python-Version haben Sie getestet?
Matt Joiner
2
Es ist ein weiterer interessanter Test - python -m timeit "x=tuple(xrange(999999))"vs python -m timeit "x=list(xrange(999999))". Wie zu erwarten ist, dauert das Materialisieren eines Tupels etwas länger als das Auflisten einer Liste.
Hamish Grubijan
3
Scheint bizarr, dass der Tupelzugriff langsamer ist als der Listenzugriff. Wenn Sie jedoch versuchen, dass in Python 2.7 auf meinem Windows 7-PC der Unterschied nur 10% beträgt, ist dies unwichtig.
ToolmakerSteve
51
FWIW, der Listenzugriff ist schneller als der Tupelzugriff in Python 2, jedoch nur, weil es einen Sonderfall für Listen in BINARY_SUBSCR in Python / ceval.c gibt. In Python 3 ist diese Optimierung weg und der Tupelzugriff wird geringfügig schneller als der Listenzugriff.
Raymond Hettinger
3
@yoopoo, der erste Test erstellt eine Liste millionenfach, der zweite erstellt eine Liste einmal und greift millionenfach darauf zu. Das -s "SETUP_CODE"wird vor dem eigentlichen Zeitcode ausgeführt.
Leez
203

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.

Raymond Hettinger
quelle
19
Schließlich setzt jemand die C-Strukturen!
Osman
1
Internally, tuples are stored a little more efficiently than lists, and also tuples can be accessed slightly faster. Wie könnten Sie dann die Ergebnisse der Antwort von dF. erklären?
DRz
5
Wenn Sie mit ~ 50.000 Listen mit ~ 100 Elementlisten arbeiten und diese Struktur in Tupel verschieben, werden die Suchzeiten für mehrere Suchvorgänge um mehrere Größenordnungen verkürzt. Ich glaube, dies liegt an der größeren Cache-Lokalität des Tupels, sobald Sie das Tupel verwenden, da die zweite von Ihnen demonstrierte Indirektionsebene entfernt wurde.
Horta
tuple(some_tuple)Gibt sich nur zurück some_tuple, wenn some_tuplees hashbar ist - wenn sein Inhalt rekursiv unveränderlich und hashbar ist. Andernfalls wird tuple(some_tuple)ein neues Tupel zurückgegeben. Zum Beispiel, wenn some_tupleveränderbare Elemente enthalten sind.
Luciano Ramalho
Tupel sind nicht immer schneller. Betrachten Sie `` `t = () für i im Bereich (1.100): t + = il = [] für i im Bereich (1.1000): a.append (i)` `` Der zweite ist schneller
Melvil James
32

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.

tzot
quelle
1
Was ist die Kompilierungszeit in Python?
Balki
1
@balki: Die Zeit, zu der die Python-Quelle zu Bytecode kompiliert wird (welcher Bytecode möglicherweise als .py [co] -Datei gespeichert wird).
Zot
Ein Zitat wäre toll, wenn möglich.
Grijesh Chauhan
9

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.

Gleichnamig
quelle
15
Es wird weniger Speicherplatz benötigen, aber die Zugriffszeit wird wahrscheinlich etwas langsamer als schneller sein. Für den Zugriff auf ein Element muss der gepackte Wert in eine echte Ganzzahl umgewandelt werden, was den Prozess verlangsamt.
Brian
5

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.

Dev Aggarwal
quelle
4

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

ctcherry
quelle
4
Warum sagen Sie, dass Unveränderlichkeit an und für sich die Effizienz erhöht? Besonders die Effizienz der Instanziierung und des Abrufs?
Blair Conrad
1
Es scheint, dass Marks Antwort über meiner die zerlegten Anweisungen darüber abdeckt, was in Python passiert. Sie können sehen, dass für die Instanziierung weniger Anweisungen erforderlich sind. In diesem Fall ist der Abruf jedoch offensichtlich identisch.
Ctcherry
unveränderliche Tupel haben einen schnelleren Zugriff als veränderbare Listen
noobninja
-6

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

Divakar
quelle