Les tuples sont-ils plus efficaces que les listes en Python?
https://stackoverflow.com/questions/68630
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Existe-t-il une différence de performances entre les n-uplets et les listes en ce qui concerne l'instanciation et la récupération d'éléments?
La solution
Le module dis désassemble le code octet. pour une fonction et est utile pour voir la différence entre les tuples et les listes.
Dans ce cas, vous pouvez voir que l'accès à un élément génère un code identique, mais que l'attribution d'un tuple est beaucoup plus rapide que l'attribution d'une 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
Autres conseils
En général, vous pouvez vous attendre à ce que les n-uplets soient légèrement plus rapides. Cependant, vous devez absolument tester votre cas spécifique (si la différence pouvait avoir une incidence sur les performances de votre programme - souvenez-vous que "l'optimisation prématurée est la racine de tous les maux").
C'est très simple avec Python: timeit est votre ami.
$ 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
et ...
$ 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
Donc, dans ce cas, l'instanciation est presque un ordre de grandeur plus rapide pour le tuple, mais l'accès aux éléments est en réalité un peu plus rapide pour la liste! Donc, si vous créez quelques nuplets et y accédez plusieurs fois, il peut être plus rapide d’utiliser des listes à la place.
Bien sûr, si vous voulez changer un élément, la liste sera certainement plus rapide car vous devrez créer un nouveau tuple entier pour en changer un élément (les n-uplets étant immuables).
Résumé
Les tuples ont tendance à avoir de meilleurs résultats que les listes dans presque toutes les catégories:
1) Les nuplets peuvent être à pli constant .
2) Les tuples peuvent être réutilisés au lieu d'être copiés.
3) Les tuples sont compacts et ne sur-allouent pas.
4) Les tuples référencent directement leurs éléments.
Les tuples peuvent être pliés de manière constante
Des nuées de constantes peuvent être précalculées par l'optimiseur de perforation ou l'optimiseur AST de Python. Les listes, par contre, se construisent à partir de zéro:
>>> 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
Les nuplets n'ont pas besoin d'être copiés
L'exécution de tuple (some_tuple) est renvoyée immédiatement. Les n-uplets étant immuables, il n’est pas nécessaire de les copier:
>>> a = (10, 20, 30)
>>> b = tuple(a)
>>> a is b
True
En revanche, list (some_list) nécessite que toutes les données soient copiées dans une nouvelle liste:
>>> a = [10, 20, 30]
>>> b = list(a)
>>> a is b
False
Les multiplets ne surallouent pas
La taille d'un tuple étant fixe, il peut être stocké de manière plus compacte que les listes qui doivent être surallouées pour que les opérations append () soient efficaces.
Cela donne aux tuples un bel avantage d'espace:
>>> import sys
>>> sys.getsizeof(tuple(iter(range(10))))
128
>>> sys.getsizeof(list(iter(range(10))))
200
Voici le commentaire de Objects / listobject.c qui explique ce que font les listes:
/* 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.
*/
Les tuples font directement référence à leurs éléments
Les références aux objets sont incorporées directement dans un tuple. En revanche, les listes ont une couche supplémentaire d'indirection vers un tableau externe de pointeurs.
Cela donne aux tuples un petit avantage en termes de vitesse pour les recherches indexées et le décompactage:
$ 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
Ici, c'est le plus bas code> (10, 20) est stocké:
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;
Voici comment la liste [10 , 20] est stocké:
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;
Notez que l'objet tuple incorpore directement les deux pointeurs de données, tandis que l'objet liste a une couche d'indirection supplémentaire vers un tableau externe contenant les deux pointeurs de données.
Les tuples, étant immuables, utilisent plus efficacement la mémoire; Listes, par souci d'efficacité, suralloue la mémoire afin de permettre les ajouts sans constantes realloc . Donc, si vous voulez parcourir une séquence constante de valeurs dans votre code (par exemple, pour indiquer la direction vers le haut, le "droit", le "bas", le "gauche": ), les n-uplets sont préférés, puisque ces tuples sont précalculés au moment de la compilation.
Les vitesses d'accès doivent être identiques (elles sont toutes deux stockées sous forme de tableaux contigus dans la mémoire).
Mais alist.append (item) est de loin préférable à atuple + = (item,) lorsque vous traitez avec des données mutables. Rappelez-vous que les n-uplets sont destinés à être traités comme des enregistrements sans noms de champs.
Vous devriez également envisager le module array de la bibliothèque standard si tous les éléments de votre liste ou de votre nuplet sont du même type C. Cela prendra moins de mémoire et peut être plus rapide.
Les nuplets devraient être légèrement plus efficaces et, pour cette raison, plus rapides que les listes, car ils sont immuables.
Voici un autre petit repère, juste pour le plaisir ..
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)
Faisons la moyenne de ceux-ci:
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
Vous pouvez appeler cela presque peu concluant.
Mais, bien sûr, les n-uplets ont pris 101,239% , ou 1,239% > pour effectuer le travail par rapport aux listes.
La principale raison pour laquelle Tuple est très efficace en lecture est son immuable.
Pourquoi les objets immuables sont-ils faciles à lire?
La raison en est que les n-uplets peuvent être stockés dans le cache mémoire, contrairement aux listes. Le programme lit toujours à partir de l’emplacement mémoire des listes car il est modifiable (peut changer à tout moment).
