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.
[ ]: