Sind Tupel effizienter als Listen in Python?
https://stackoverflow.com/questions/68630
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Gibt es einen Unterschied in der Leistung zwischen Tupeln und Listen, wenn es darum geht, Instanziierung und Abrufen von Elementen?
Lösung
Der dis Modul zerlegt den Bytecode für eine Funktion und ist nützlich, um sehen Sie den Unterschied zwischen Tupeln und Listen.
In diesem Fall können Sie sehen, dass ein Element Zugriff auf identischen Code generiert, sondern dass ein Tupel Zuweisung ist viel schneller als eine Liste zuweisen.
>>> 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
Andere Tipps
In der Regel können Sie Tupeln erwarten etwas schneller sein. Allerdings sollten Sie auf jeden Fall Ihren speziellen Fall testen. (Wenn der Unterschied könnte die Leistung Ihres Programms auswirken - erinnern „vorzeitige Optimierung ist die Wurzel aller Übel“)
Python macht dies 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
So in diesem Fall Instanziierung ist fast eine Größenordnung schneller für das Tupel, aber Artikel Zugang ist tatsächlich etwas schneller für die Liste! Also, wenn Sie ein paar Tupel zu schaffen und sie viele, viele Male zugegriffen wird, kann es tatsächlich schneller sein Listen stattdessen zu verwenden.
Natürlich, wenn Sie möchten, Veränderung ein Element, wird die Liste auf jeden Fall schneller sein, da Sie ein völlig neues Tupel erstellen bräuchten ein Element davon zu ändern (da Tupel unveränderlich ist).
Zusammenfassung
Tupeln tendenziell besser ab als Listen in fast jeder Kategorie:
1) Tupeln können konstant gefaltet .
2) Tupeln können statt kopiert wiederverwendet werden.
3) Tupeln sind kompakt und nicht über-zuweisen.
4) Tupeln direkt ihre Elemente verweisen.
Tupeln konstant gefaltet
seinTupeln von Konstanten kann durch Python Guckloch-Optimierer oder AST-Optimierer vorberechnet werden. Listen, auf der anderen Seite bekommen verbauten von Grund auf:
>>> 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
Tupeln müssen nicht kopiert werden
Beim Laufen tuple(some_tuple) kehrt sofort selbst. Da Tupel unveränderlich sind, sie müssen nicht kopiert werden:
>>> a = (10, 20, 30)
>>> b = tuple(a)
>>> a is b
True
Im Gegensatz dazu benötigt list(some_list) alle Daten in eine neue Liste kopiert werden:
>>> a = [10, 20, 30]
>>> b = list(a)
>>> a is b
False
Tupeln nicht über zuteilen
Da eine Größe des Tupels fixiert ist, kann es kompakter als Listen gespeichert werden, die müssen über zuteilen machen anhängen () Operationen effizienter zu gestalten.
Das gibt Tupel einen schönen Raum Vorteil:
>>> import sys
>>> sys.getsizeof(tuple(iter(range(10))))
128
>>> sys.getsizeof(list(iter(range(10))))
200
Hier ist der Kommentar von Objekten / listobject.c , das 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.
*/
Tupeln beziehen sich direkt auf ihre Elemente
Verweise auf Objekte werden direkt in einem Tupel Objekt eingebaut. Im Gegensatz dazu Listen haben eine zusätzliche Schicht von Dereferenzierung zu einem externen Feld von Zeigern.
Das gibt Tupeln einen kleinen Geschwindigkeitsvorteil für indizierte Lookups 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 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 ist, wie die Liste [10, 20] gespeichert ist:
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 der zwei Datenzeiger direkt integriert, während die Liste Objekt eine zusätzliche Ebene der Indirektheit zu einer externen Anordnung Halten der beiden Datenzeiger hat.
Tupeln, wobei unveränderlich, sind mehr Speicher effizienter zu gestalten; Listen, für Effizienz, overallocate Speicher zu ermöglichen, um anhängen ohne ständige reallocs. Also, wenn Sie durch eine konstante Folge von Werten in Ihrem Code wiederholen mögen (zB for direction in 'up', 'right', 'down', 'left':) wird Tupeln bevorzugt, da solche Tupel vorausberechneten in der Kompilierung ist.
Zugriffsgeschwindigkeiten sollten gleich sein (sie beide als zusammenhängender Arrays im Speicher abgelegt werden).
Aber ist alist.append(item) viel lieber atuple+= (item,), wenn Sie mit veränderbaren Daten umgehen. Denken Sie daran, sind Tupel bestimmt ohne Feldnamen behandelt als Datensätze werden.
Sie sollten auch die array Modul in der Standardbibliothek prüfen, ob alle Elemente in der Liste oder Tupel des gleichen C-Typs sind. Es wird weniger Speicherplatz verbrauchen und schneller sein.
Tupeln sollten etwas effizienter und deswegen schneller, als Listen, weil sie unveränderlich sind.
Hier ist ein weiterer kleiner Maßstab, nur um es ..
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 auszumitteln:
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
Sie können es nennen fast nicht schlüssig.
Aber sicher, Tupeln nahm 101.239% die Zeit oder 1.239% zusätzliche Zeit, um die Arbeit zu tun im Vergleich zu Listen.
Der Hauptgrund für Tuple beim Lesen sehr effizient zu sein, weil es unveränderlich ist.
Warum unveränderliche Objekte sind leicht zu lesen?
Der Grund dafür ist Tupel kann in der Cache-Speicher gespeichert werden, im Gegensatz zu Listen. Das Programm immer von der Listen Speicherplatz lesen, wie es ist wandelbar (kann jederzeit ändern).
