Liste, tuple, ensemble, dictionnaire, liste chaînée, coût des opérations

Exemples de containers, list, tuple, set, dict.

Python propose différents containers pour stocker des éléments. Voici les plus courants :

  • list : tableau d’éléments indexés de 0 à n exclu auquel on peut ajouter ou retirer des éléments

  • dict : tableau d’éléments indexés par des types immuables auquel on peut ajouter ou retirer des éléments

  • tuple : tableau d’éléments indexés de 0 à n exclu qu’on ne peut pas modifier

  • set : tableau d’éléments uniques non indexés

  • frozenset : set immuables (non modifiable)

  • deque : presque équivalent à une listes, la différent vient de l’implémentation, les mêmes opérations n’auront pas les mêmes coûts (deque = liste chaînée)

D’autres containers sont disponibles via le module collections. Tous proposent de stocker un nombre variables d’éléments. Deux aspects difféèrent :

  • la façon de désigner un élément de l’ensemble

  • le coût de certaines opérations, il faut choisir qui minisera le coût des opérations pour votre programme

Insertion avec list et deque

On veut comparer les coûts d’insertion en début et fin de liste pour un grand nombre d’éléments.

[1]:

import time, collections

N = 1000000

for p in range(0, 3):
    print("passage ", p)
    print("  insertion en fin")

    li = list()
    a = time.perf_counter()
    for i in range(0, N):
        li.append(i)
    b = time.perf_counter()
    print("    list", N, "éléments, temps par éléments :", (b - a) / N)

    li = collections.deque()
    a = time.perf_counter()
    for i in range(0, N):
        li.append(i)
    b = time.perf_counter()
    print("    deque", N, "éléments, temps par éléments :", (b - a) / N)

    print("  insertion au début")
    li = collections.deque()
    a = time.perf_counter()
    for i in range(0, N):
        li.appendleft(i)
    b = time.perf_counter()
    print("    deque", N, "éléments, temps par éléments :", (b - a) / N)

    N2 = N // 100
    li = list()
    a = time.perf_counter()
    for i in range(0, N2):
        li.insert(0, i)
    b = time.perf_counter()
    print("    list", N, "éléments, temps par éléments :", (b - a) / N)

passage  0
  insertion en fin
    list 1000000 éléments, temps par éléments : 1.2462739999955374e-07
    deque 1000000 éléments, temps par éléments : 1.0353370000029826e-07
  insertion au début
    deque 1000000 éléments, temps par éléments : 9.81406999999308e-08
    list 1000000 éléments, temps par éléments : 1.796050000029936e-08
passage  1
  insertion en fin
    list 1000000 éléments, temps par éléments : 9.953019999920797e-08
    deque 1000000 éléments, temps par éléments : 8.313129999987723e-08
  insertion au début
    deque 1000000 éléments, temps par éléments : 7.568269999956101e-08
    list 1000000 éléments, temps par éléments : 1.580999999987398e-08
passage  2
  insertion en fin
    list 1000000 éléments, temps par éléments : 8.447889999933977e-08
    deque 1000000 éléments, temps par éléments : 8.401670000057492e-08
  insertion au début
    deque 1000000 éléments, temps par éléments : 7.71205999999438e-08
    list 1000000 éléments, temps par éléments : 1.6167699999641626e-08

On voit que l’insertion au début du tableau est beaucoup plus coûteuse pour une liste que pour un deque.

Un élément dans un ensemble

Faut-il écrire i in [0,1] ou i in (0,1) ou … Essayons.

[2]:

import time, collections

N = 100000
lens = list(range(0, 1000))
tens = tuple(lens)
sens = set(lens)
fens = frozenset(lens)

for p in range(0, 3):
    print("passage", p)
    a = time.perf_counter()
    s = 0
    for i in range(0, N):
        if i in lens:
            s += 1
    b = time.perf_counter()
    print("  list", N, "fois, temps par éléments :", (b - a) / N)

    a = time.perf_counter()
    s = 0
    for i in range(0, N):
        if i in tens:
            s += 1
    b = time.perf_counter()
    print("  tuple", N, "fois, temps par éléments :", (b - a) / N)

    a = time.perf_counter()
    s = 0
    for i in range(0, N):
        if i in sens:
            s += 1
    b = time.perf_counter()
    print("  set", N, "fois, temps par éléments :", (b - a) / N)

    a = time.perf_counter()
    s = 0
    for i in range(0, N):
        if i in fens:
            s += 1
    b = time.perf_counter()
    print("  frozenset", N, "fois, temps par éléments :", (b - a) / N)

passage 0
  list 100000 fois, temps par éléments : 5.977897000002485e-06
  tuple 100000 fois, temps par éléments : 6.178353999994215e-06
  set 100000 fois, temps par éléments : 6.823300000178278e-08
  frozenset 100000 fois, temps par éléments : 7.471699999769044e-08
passage 1
  list 100000 fois, temps par éléments : 5.712876000006872e-06
  tuple 100000 fois, temps par éléments : 5.798504000003959e-06
  set 100000 fois, temps par éléments : 8.035500000005414e-08
  frozenset 100000 fois, temps par éléments : 8.195899999918766e-08
passage 2
  list 100000 fois, temps par éléments : 5.84480600000461e-06
  tuple 100000 fois, temps par éléments : 5.923587000006591e-06
  set 100000 fois, temps par éléments : 7.347799999479321e-08
  frozenset 100000 fois, temps par éléments : 6.471000000601634e-08

Il apparaît que les ensemble set ou frozenset sont beaucoup plus rapides. Plus l’ensemble est grand, plus cette différence est importante.

[ ]:

Notebook on github