1A.1 - Liste, tuple, ensemble, dictionnaire, liste chaînée, coût des opérations#
Links: notebook
, html, python
, slides, GitHub
Exemples de containers, list, tuple, set, dict.
from jyquickhelper import add_notebook_menu
add_notebook_menu()
Python propose différents containers pour stocker des éléments. Voici les plus courants :
list : tableau d’éléments indexés de 0 à 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 à 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.
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.6768032881764787e-07
deque 1000000 éléments, temps par éléments : 1.3930898200138983e-07
insertion au début
deque 1000000 éléments, temps par éléments : 1.2026622409235594e-07
list 1000000 éléments, temps par éléments : 2.2802558892816237e-08
passage 1
insertion en fin
list 1000000 éléments, temps par éléments : 1.5078710092361442e-07
deque 1000000 éléments, temps par éléments : 1.210950632710861e-07
insertion au début
deque 1000000 éléments, temps par éléments : 1.2431481508550512e-07
list 1000000 éléments, temps par éléments : 2.6522458657794125e-08
passage 2
insertion en fin
list 1000000 éléments, temps par éléments : 1.4364004201874892e-07
deque 1000000 éléments, temps par éléments : 1.3574118094175568e-07
insertion au début
deque 1000000 éléments, temps par éléments : 1.3737357535858763e-07
list 1000000 éléments, temps par éléments : 2.607208846534781e-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.
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 : 1.1804175089708608e-05
tuple 100000 fois, temps par éléments : 1.2459357053093508e-05
set 100000 fois, temps par éléments : 8.682663236478483e-08
frozenset 100000 fois, temps par éléments : 9.215601297539955e-08
passage 1
list 100000 fois, temps par éléments : 1.1412313516123058e-05
tuple 100000 fois, temps par éléments : 1.1940795282648774e-05
set 100000 fois, temps par éléments : 8.101922725166411e-08
frozenset 100000 fois, temps par éléments : 8.893231054526218e-08
passage 2
list 100000 fois, temps par éléments : 1.1539950008908635e-05
tuple 100000 fois, temps par éléments : 1.1629893677079037e-05
set 100000 fois, temps par éléments : 8.061231383216239e-08
frozenset 100000 fois, temps par éléments : 9.595650530114242e-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.