Warum ist Tupel schneller als Liste?

Berichtet die "speed of construction" - Verhältnis gilt nur für Konstante Tupel (diejenigen, deren Elemente ausgedrückt werden, indem Literale). Sorgfältig beobachten (und wiederholen Sie die auf Ihrem Computer-Sie müssen nur geben Sie die Befehle in einer shell/Befehls-Fenster!)...:

$ python3.1 -mtimeit -s'x,y,z=1,2,3' '[x,y,z]'
1000000 loops, best of 3: 0.379 usec per loop
$ python3.1 -mtimeit '[1,2,3]'
1000000 loops, best of 3: 0.413 usec per loop

$ python3.1 -mtimeit -s'x,y,z=1,2,3' '(x,y,z)'
10000000 loops, best of 3: 0.174 usec per loop
$ python3.1 -mtimeit '(1,2,3)'
10000000 loops, best of 3: 0.0602 usec per loop

$ python2.6 -mtimeit -s'x,y,z=1,2,3' '[x,y,z]'
1000000 loops, best of 3: 0.352 usec per loop
$ python2.6 -mtimeit '[1,2,3]'
1000000 loops, best of 3: 0.358 usec per loop

$ python2.6 -mtimeit -s'x,y,z=1,2,3' '(x,y,z)'
10000000 loops, best of 3: 0.157 usec per loop
$ python2.6 -mtimeit '(1,2,3)'
10000000 loops, best of 3: 0.0527 usec per loop

Habe ich nicht die Messungen auf 3.0, weil ich natürlich nicht herum-es ist völlig veraltet und es gibt absolut kein Grund zu halten Sie herum, seit 3.1 ist überlegen in jeder Hinsicht (Python 2.7, wenn Sie aktualisieren können, um es Maßnahmen, wie Sie fast 20% schneller als 2.6 in jeder Aufgabe-und 2,6, wie Sie sehen, ist schneller als 3.1 -- so, wenn Sie Pflege ernst über die Leistung, Python 2.7 ist wirklich der einzige Veröffentlichung, die Sie sollten gehen!).

Trotzdem, der entscheidende Punkt hier ist, dass, in jeder Python-Version, bauen Sie eine Liste von Konstanten Literale ist etwa die gleiche Geschwindigkeit, oder etwas langsamer, als es aus der Werte verwiesen wird, die von Variablen; aber Tupel Verhalten sich sehr unterschiedlich -- Gebäude ein Tupel aus Konstanten Literale ist in der Regel drei mal so schnell wie der Bau von Werte verwiesen wird, die von Variablen! Sie Fragen sich vielleicht, wie das sein kann, richtig?-)

Antwort: ein Tupel aus Konstanten Literale können leicht identifiziert werden, durch die der Python-compiler als eine, unveränderliche Konstante-literal selbst: so ist es im wesentlichen genauso gebaut wurde, einmal, wenn der compiler wandelt den Quellcode in Bytecode, und verstaut in der "Konstanten-Tabelle" der jeweiligen Funktion oder Modul. Wenn diese bytecodes ausführen, die Sie gerade benötigen, um wieder die vordefinierte Konstante Tupel-hey presto!-)

Dieser einfachen Optimierung nicht angewandt werden können, zu Listen, da eine Liste ist ein veränderliches Objekt, so ist es wichtig, dass, wenn der gleiche Ausdruck wie [1, 2, 3] führt zweimal (in einer Schleife -- die timeit - Modul macht die Schleife auf Ihrem Namen;-), ein frisches, neues list-Objekt ist konstruiert, jedes mal wieder neu-und das Baugewerbe (wie der Bau eines Tupels, wenn der compiler nicht trivial identifizieren es als compile-time-Konstante und unveränderliche Objekt) braucht eine Weile.

Dass gesagt wird, die Tupel-Konstruktion (wenn beide Konstruktionen haben tatsächlich
auftreten) immer noch etwa doppelt so schnell als Liste Bau-und , dass Diskrepanz kann erklärt werden durch die Tupel ist die schiere Einfachheit, die andere Antworten haben, die immer wieder genannt. Aber, dass Einfachheit nicht berücksichtigt, für eine Beschleunigung von sechs mal oder mehr, als Sie beobachten, wenn Sie nur vergleichen Sie den Bau von Listen und Tupeln mit einfachen Konstanten Literale als Ihre Einzelteile!_)

InformationsquelleAutor der Antwort Alex Martelli

Alex gab eine großartige Antwort, aber ich werde versuchen zu erweitern auf ein paar Dinge finde ich erwähnenswert. Etwaige performance-Unterschiede sind in der Regel klein und Umsetzung spezifischer: so nicht Wetten der farm auf Sie.

In CPython, Tupel gespeichert sind in einem einzigen block des Speichers, also die Schaffung eines neuen Tupel beinhaltet, im schlimmsten Fall ein einziger Anruf, um Speicher zuzuweisen. Listen zugeordnet sind, in zwei Blöcke: die Feste mit allen Python-Objekt information, und eine variable-sized-block für die Daten. Das ist Teil der Grund, warum die Schaffung eines Tupel schneller ist, aber es wahrscheinlich erklärt sich auch der leichte Unterschied in der Indexierung Geschwindigkeit, wie es ist eine weniger Zeiger zu Folgen.

Gibt es auch Optimierungen in CPython zu reduzieren, Speicher-Zuweisungen: de-Liste zugewiesen-Objekte gespeichert werden auf eine freie Liste, so dass Sie wiederverwendet werden kann, aber die Zuteilung nicht-leere Liste benötigt noch eine Zuweisung von Speicher für die Daten. Tupel gespeichert sind, auf den 20 freien Listen für unterschiedliche sortierte Tupel, so dass die Zuteilung einer kleinen Tupel wird oft benötigt keine memory allocation Anrufe zu allen.

Optimierungen wie diese sind hilfreich in der Praxis, aber Sie kann auch machen es riskant ist, hängen zu sehr auf die Ergebnisse der 'timeit' und sind natürlich völlig unterschiedlich aus, wenn Sie sich bewegen, um so etwas wie IronPython, wo der Speicher Zuweisung funktioniert ganz anders.

InformationsquelleAutor der Antwort Duncan

Zusammenfassung

Tupel neigen dazu, bessere Leistungen zu erbringen als Listen in fast jeder Kategorie:

1) - Tupel werden kann Konstante gefaltet.

2) Tupel können wiederverwendet werden, anstatt kopiert.

3) Tupel sind kompakt und nicht zu zuordnen.

4) Tupel direkt auf Ihre Elemente.

Tupel kann konstant gefaltet

Tupel von Konstanten kann vorausberechnete von Python ' s peephole optimizer oder AST-Optimierer. Listen, auf der anderen Seite, gebaut-von Grund auf neu:

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

Läuft tuple(some_tuple) kehrt sofort selbst. Da Tupel sind unveränderlich, Sie müssen nicht kopiert werden:

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

Im Gegensatz dazu list(some_list) erfordert, alle Daten werden kopiert, um eine neue Liste:

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

Tupel nicht mehr reservieren,

Da ein Tupel die Größe fixiert ist, kann es gespeichert werden kompakter als die Listen, die Notwendigkeit zu über-weisen Sie machen append() Operationen effizient.

Dieser Tupel gibt einen schönen Platz Vorteil:

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

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

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

Referenzen auf Objekte sind, fließen direkt in ein Tupel-Objekt. Im Gegensatz dazu Listen haben eine zusätzliche Schicht der Dereferenzierung zu einem externen array von Zeigern.

Dieser Tupel gibt einen kleinen speed-Vorteil für indizierte Suchvorgänge und 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

Hier ist, wie die Tupel (10, 20) ist 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 ist, wie die Liste [10, 20] ist 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 Tupel-Objekt umfasst die beiden Daten Zeiger direkt, während die Liste-Objekt hat eine zusätzliche Schicht der Dereferenzierung zu einem externen array, die die zwei Daten Pointer.

InformationsquelleAutor der Antwort Raymond Hettinger

Tupel identifiziert werden, die von python compiler als eine unveränderliche Konstante
also compiler erzeugt nur einen Eintrag in der hash-Tabelle und nie geändert

Listen sind mutable-Objekte.Also compiler aktualisieren Sie den Eintrag, wenn wir die Liste aktualisieren
so ist es etwas langsamer angehen zu vergleichen, um Tupel

InformationsquelleAutor der Antwort y durga prasad