Warum ist die Tupel schneller als Liste in Python?

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.

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.

Einem Bereich, wo eine Liste ist vor allem schneller ist der Bau von einem generator, und insbesondere, Liste Verstehens sind viel schneller als die des nächsten Tupels entspricht, tuple() mit einem generator-argument:

$ python --version
Python 3.6.0rc2
$ python -m timeit 'tuple(x * 2 for x in range(10))'
1000000 loops, best of 3: 1.34 usec per loop
$ python -m timeit 'list(x * 2 for x in range(10))'
1000000 loops, best of 3: 1.41 usec per loop
$ python -m timeit '[x * 2 for x in range(10)]'
1000000 loops, best of 3: 0.864 usec per loop

Beachten Sie insbesondere, dass tuple(generator) scheint ein kleines bisschen schneller als list(generator), aber [elem for elem in generator] ist viel schneller als beide.