Sono tuple più efficiente rispetto alle liste in Python?
https://stackoverflow.com/questions/68630
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
C'è qualche differenza di prestazioni tra tuple e liste quando si tratta di creazione di istanze e di recupero di elementi?
Soluzione
Il dis modulo smonta il byte di codice per una funzione è utile per vedere la differenza tra tuple e liste.
In questo caso, si può vedere che l'accesso a un elemento genera codice identico, ma che l'assegnazione di una tupla è molto più veloce rispetto all'assegnazione di un elenco.
>>> 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
Altri suggerimenti
In generale, ci si potrebbe aspettare tuple per essere leggermente più veloce.Tuttavia, si dovrebbe sicuramente prova il tuo caso specifico, se la differenza potrebbe influire sulle prestazioni del vostro programma -- ricordate "l'ottimizzazione è la radice di ogni male").
Python rende questo molto facile: timeit è il tuo amico.
$ 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
e...
$ 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
Quindi, in questo caso, la creazione di istanze di quasi un ordine di grandezza più veloce per la tupla, ma l'elemento di accesso è in realtà un po ' più veloce per la lista!Quindi, se si sta creando un paio di tuple e l'accesso a loro e molte volte, si può effettivamente essere più veloce di utilizzare gli elenchi, invece.
Naturalmente, se si desidera cambiare un elemento, l'elenco sarà sicuramente più veloce, dato che si avrebbe bisogno di creare una nuova tupla per modificare un elemento di (in quanto le tuple sono immutabili).
Riepilogo
Tuple tendono a fare meglio elenchi in quasi tutte le categorie:
1) le Tuple possono essere costante piegato.
2) le Tuple possono essere riutilizzate invece di copiare.
3) le Tuple sono compatti e di non allocare.
4) le Tuple riferimento direttamente i loro elementi.
Le tuple possono essere costante piegato
Tuple di costanti possono essere pre-calcolate da Python spioncino optimizer o AST-optimizer.Le liste, invece, ottenere costruito da zero:
>>> 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
Tuple non devono essere copiati
In esecuzione tuple(some_tuple) torna subito in sé.Dal momento che le tuple sono immutabili, non devono essere copiati:
>>> a = (10, 20, 30)
>>> b = tuple(a)
>>> a is b
True
In contrasto, list(some_list) richiede che tutti i dati vengano copiati in una nuova lista:
>>> a = [10, 20, 30]
>>> b = list(a)
>>> a is b
False
Tuple non allocare
Dal momento che una tupla è fisso, può essere conservato più compatto rispetto alle liste che hanno bisogno di più di assegnazione per rendere append() operazioni efficienti.
Questo dà tuple un bel vantaggio di spazio:
>>> import sys
>>> sys.getsizeof(tuple(iter(range(10))))
128
>>> sys.getsizeof(list(iter(range(10))))
200
Ecco il commento da Oggetti/listobject.c che spiega che le liste stanno facendo:
/* 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.
*/
Tuple di fare riferimento direttamente al loro elementi
I riferimenti agli oggetti sono incorporati direttamente in una tupla oggetto.In contrasto, le liste hanno un ulteriore livello di riferimento indiretto esterno ad un array di puntatori.
Questo dà tuple un piccolo vantaggio in velocità per indicizzati ricerche e disimballaggio:
$ 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
Qui è come la tupla (10, 20) di archiviazione:
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;
Qui è come l'elenco [10, 20] di archiviazione:
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;
Nota che la tupla oggetto incorpora i due puntatori dati direttamente mentre la lista oggetto ha un ulteriore livello di riferimento indiretto a un esterno vettore contenente i dati di due puntatori.
Tuple, essendo immutabile, sono la memoria più efficiente;le liste, per l'efficienza, overallocate di memoria per consentire aggiunge senza una costante reallocs.Quindi, se si desidera scorrere un costante sequenza di valori di codice (es. for direction in 'up', 'right', 'down', 'left':), le tuple sono preferibili, in quanto tali tuple pre-calcolati in fase di compilazione.
La velocità di accesso deve essere la stessa (sono entrambi memorizzati come contigui array in memoria).
Ma, alist.append(item) è molto preferito atuple+= (item,) quando hai a che fare con il mutevole dati.Ricordate, le tuple sono destinati ad essere trattati come record senza nomi di campo.
Si dovrebbe anche prendere in considerazione il array modulo nella libreria standard, se tutti gli elementi della lista o di una tupla sono dello stesso tipo C.Ci vorrà meno di memoria e può essere più veloce.
Le tuple devono essere leggermente più efficiente e, per questo, più veloce, rispetto alle liste perché sono immutabili.
Ecco un altro po ' di benchmark, solo per il gusto di farlo..
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)
Lasciate che la media di questi:
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
Si può chiamare quasi inconcludente.
Ma certo, tuple preso 101.239% il tempo, o 1.239% tempo extra per fare il lavoro rispetto alle liste.
La ragione principale per la Tupla di essere molto efficiente nella lettura, è perché è immutabile.
Perché gli oggetti immutabili sono di facile lettura?
Il motivo è tuple possono essere memorizzati nella cache di memoria, a differenza di liste.Il programma di leggere sempre dalle liste di memoria di posizione, come è mutevole (può cambiare in qualsiasi momento).
