Les tuples sont-ils plus efficaces que les listes en Python?

Existe-t-il une différence de performances entre les tuples et les listes en ce qui concerne l'instanciation et la récupération d'éléments?

Le dismodule désassemble le code d'octet d'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

En général, vous pouvez vous attendre à ce que les tuples soient légèrement plus rapides. Cependant, vous devez absolument tester votre cas spécifique (si la différence peut avoir un impact sur les performances de votre programme - n'oubliez pas que "l'optimisation prématurée est la racine de tout mal").

Python rend cela très facile: 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 fait un peu plus rapide pour la liste! Donc, si vous créez quelques tuples et y accédez plusieurs fois, il peut être plus rapide d'utiliser des listes à la place.

Bien sûr, si vous souhaitez modifier un élément, la liste sera certainement plus rapide car vous devrez créer un tout nouveau tuple pour en modifier un élément (car les tuples sont immuables).

Résumé

Les tuples ont tendance à mieux performer que les listes dans presque toutes les catégories:

1) Les tuples peuvent être pliés en permanence .

2) Les tuples peuvent être réutilisés au lieu d'être copiés.

3) Les tuples sont compacts et n'allouent pas trop.

4) Les tuples font directement référence à leurs éléments.

Les tuples peuvent être pliés en permanence

Des tuples de constantes peuvent être précalculés par l'optimiseur de judas de Python ou l'optimiseur AST. Les listes, en revanche, 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 tuples n'ont pas besoin d'être copiés

La course tuple(some_tuple)revient immédiatement. Les tuples étant immuables, ils ne doivent pas être copiés:

>>> 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 tuples ne surallouent pas

Étant donné que la taille d'un tuple est fixe, il peut être stocké de manière plus compacte que les listes qui doivent être surallouées pour rendre les opérations append () 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 d' 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 se réfèrent directement à leurs éléments

Les références aux objets sont incorporées directement dans un objet 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 de vitesse pour les recherches indexées et le déballage:

$ 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

Voici comment le tuple (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ée:

    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 possède une couche supplémentaire d'indirection vers un tableau externe contenant les deux pointeurs de données.

Les tuples, étant immuables, sont plus efficaces en mémoire; répertorie, pour plus d'efficacité, la surutilisation de la mémoire afin de permettre des ajouts sans constante reallocs. Donc, si vous voulez parcourir une séquence constante de valeurs dans votre code (par exemple for direction in 'up', 'right', 'down', 'left':), les tuples sont préférés, car ces tuples sont pré-calculés au moment de la compilation.

Les vitesses d'accès doivent être les mêmes (elles sont toutes deux stockées en tant que tableaux contigus dans la mémoire).

Mais, alist.append(item)est de loin préférable atuple+= (item,)lorsque vous traitez des données mutables. N'oubliez pas que les tuples sont destinés à être traités comme des enregistrements sans nom de champ.

Vous devriez également considérer le arraymodule dans la bibliothèque standard si tous les éléments de votre liste ou tuple sont du même type C. Cela prendra moins de mémoire et peut être plus rapide.

Voici une autre petite référence, 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 ces derniers:

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 l'appeler presque non concluant.

Mais bien sûr, les tuples ont pris 101.239%du temps, ou 1.239%du temps supplémentaire pour faire le travail par rapport aux listes.

Les tuples devraient être légèrement plus efficaces et à cause de cela, plus rapides, que les listes car ils sont immuables.

La principale raison pour laquelle Tuple est très efficace en lecture est qu'il est immuable.

Pourquoi les objets immuables sont-ils faciles à lire?

La raison est que les tuples peuvent être stockés dans le cache mémoire, contrairement aux listes. Le programme lit toujours à partir de l'emplacement de la mémoire des listes car il est modifiable (peut changer à tout moment).