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