containers (2/2)

plusieurs types pratiques et efficaces sont fournis de base, et notamment

liste, tuple (vus précédemment)
dictionnaire, ensemble: ce notebook

problèmes avec les séquences¶

de deux ordres principalement

(1) les recherches sont lentes¶

a = list(range(30000000))
'x' in a      # c’est long !

False

(2) on ne peut indexer que par un entier¶

a[3]          # on peut utiliser un indice entier

3

a = []
# on ne peut pas indexer avec un nom ou autre chose qu'un entier
try:
    a['alice'] = 10
except TypeError as e:
    print("OOPS", e)

OOPS list indices must be integers or slices, not str

récapitulons¶

une séquence est une liste ordonnée d’éléments
indexés par des entiers
- les recherches sont longues O(n)
- impossible d’avoir un index autre qu’entier
- comment faire, par exemple, un annuaire ?
on voudrait
- une insertion, effacement et recherche en O(1)
- une indexation par clef quelconque

la solution : les tables de hash¶

une table de hash T indexe des valeurs par des clefs
- T[clef] = valeur
- insertion, effacement, recherche en O(1)
- chaque clef est unique (une seule valeur pour une clé)

le principe¶

la fonction de hash¶

la fonction de hash f() choisie de façon à ce que
- f(key, size) retourne toujours la même valeur
- key ne doit pas pouvoir changer au cours du temps
- et donc en particulier être immutable
minimise le risque de collision
- f(key1, size) == f(key2, size)
une bonne façon de minimiser les collisions
est de garantir une distribution uniforme

table de hash et Python¶

l’ensemble set est une table de hash qui utilise
- comme clef un objet immutable
- et qui n’associe pas la clef à une valeur
cela matérialise donc la notion d’ensemble mathématique
le dictionnaire dict est une table de hash qui utilise
- comme clef un objet immutable
- et comme valeur n’importe quel objet
il fournit donc une association clé → valeur

le `set`¶

collection non ordonnée(♤) d’objets uniques et immutables
utile pour tester l’appartenance
- optimisé, beaucoup + rapide que list
et éliminer les entrées doubles (dedup) d’une liste
les sets autorisent les opérations sur des ensembles
- union (|), intersection (&), différence (-), etc.

création¶

# ATTENTION : les dictionnaires étaient là avant les ensembles !
# du coup {} n'est pas un ensemble, mais un dict !

set()          # ensemble vide

set()

# ou sinon, on peut comme toujours
# utiliser le type comme une
# usine à objets

L1 = [1, 2, 3, 1, 1, 6, 4]
S1 = set(L1)
S1

{1, 2, 3, 4, 6}

opérations sur `set`¶

S1

{1, 2, 3, 4, 6}

L2 = [3, 4, 1]
S2 = set(L2)
S2

{1, 3, 4}

4 in S2

True

S1 - S2            # différence

{2, 6}

S1 | S2            # union

{1, 2, 3, 4, 6}

S1 & S2            # intersection

{1, 3, 4}

# toujours vrai

(S1 & S2) | (S1 - S2) | (S2 - S1) == (S1 | S2)

True

le `set`: méthodes¶

les plus utiles sont add() et .remove() (et là encore il y en a toute un paquet...)

# ensemble littéral
S3 = {1, 2, 3, 4}
S3

{1, 2, 3, 4}

# ajout d'un élément

S3.add('spam')
S3

{1, 2, 3, 4, 'spam'}

# pas de duplication
# et pas d'ordre particulier
S3.update([10, 11, 10, 11])
S3

{1, 10, 11, 2, 3, 4, 'spam'}

S3.remove(11)
S3

{1, 10, 2, 3, 4, 'spam'}

le `set` est mutable¶

un set est un objet mutable
le frozenset est équivalent mais non mutable(♤)
par exemple pour servir de clé dans un hash

fs = frozenset([1, 2, 3, 4])

# frozenset pas mutable
try:
    fs.add(5)
except AttributeError as e:
    print("OOPS", e)

OOPS 'frozenset' object has no attribute 'add'

éléments acceptables¶

on a le droit d’y mettre tout ce qui est non-mutable
pour que la fonction de hachage retourne toujours la même chose

S = set()
S.add(1)
S.add("abc")
# je peux y ajouter un tuple !
S.add((1, 2))
S

{(1, 2), 1, 'abc'}

# mais pas une liste !
try:
    S.add([1, 2])
except TypeError as e:
    print("OOPS", e)

OOPS unhashable type: 'list'

exercice de pensée

Question: à votre avis, peut-on ajouter dans un ensemble un tuple de 2 listes ?

S.add( ([1, 2], [3, 4]) )

réponse

en fait non! ce tuple est immutable, mais on peut tout de même changer ses éléments car ce sont des listes !

rapide test de performance¶

pour la recherche d’un élément, le set est beaucoup plus rapide

x = list(range(100000))

%timeit -n 300 "c" in x

1.71 ms ± 1.05 ms per loop (mean ± std. dev. of 7 runs, 300 loops each)

x = set(range(100000))

%timeit -n 300 "c" in x

18.3 ns ± 0.754 ns per loop (mean ± std. dev. of 7 runs, 300 loops each)

le set est beaucoup plus rapide¶

et cela même si la liste est très petite

x = list(range(2))

%timeit -n 300 "c" in x

62.6 ns ± 1.83 ns per loop (mean ± std. dev. of 7 runs, 300 loops each)

x = set(range(2))

%timeit -n 300 "c" in x

19.1 ns ± 1.07 ns per loop (mean ± std. dev. of 7 runs, 300 loops each)

le meilleur cas pour la liste¶

en fait pour obtenir des performances comparables

il faut que l’élément cherché soit le premier de la liste
donc, toujours utiliser les sets pour les tests d’appartenance

x = list(range(2))

%timeit -n 300 0 in x

26.7 ns ± 0.878 ns per loop (mean ± std. dev. of 7 runs, 300 loops each)

x = set(range(2))

%timeit -n 300 0 in x

24.4 ns ± 0.909 ns per loop (mean ± std. dev. of 7 runs, 300 loops each)

le dictionnaire¶

généralisation d’une table de hash
collection ordonnée (depuis la 3.7)
d’associations clé → valeur
on accède aux objets à l’aide d’une clef
(et non d’un indice comme pour une liste)
une clef peut être n’importe quel objet immutable
chaîne, nombre, tuple d’objets immutables...
c’est une structure de données très puissante
le dictionnaire est un type mutable

création¶

# ATTENTION : les dictionnaires étaient là avant les ensembles !
# du coup {} n'est pas un ensemble, mais un dict !

D = {}
D

{}

# un dictionnaire créé de manière littérale

{ 'douze' : 12, 1: 'un', 'liste' : [1, 2, 3] }

{'douze': 12, 1: 'un', 'liste': [1, 2, 3]}

# une autre façon, quand les clés sont des chaînes

dict( a = 'A', b = 'B')

{'a': 'A', 'b': 'B'}

# ou aussi, plus rare, mais à partir d'une liste de couples...
# juste pour montrer qu'il y a souvent plein de façons de faire...

dict( [ ('a', 'A'), ('b', 'B') ] )

{'a': 'A', 'b': 'B'}

manipulations usuelles¶

len(D) retourne le nombre de clefs dans D
D[clef] retourne la valeur pour la clef
D[clef] = x change la valeur pour la clef
del D[clef] supprime la clef et la valeur
clef in D teste l’existence de clef dans D
clef not in D teste la non existence
D.copy() shallow copy de D

D = {'alice': 35, 'bob' : 9, 'charlie': 6}
D

{'alice': 35, 'bob': 9, 'charlie': 6}

# combien d'entrées

len(D)

3

D['alice']

35

# appartenance = est-ce une clé ?
'bob' in D

True

D['jim'] = 32
D

{'alice': 35, 'bob': 9, 'charlie': 6, 'jim': 32}

# on n'avait pas encore vu cet opérateur..

del D['jim']
D

{'alice': 35, 'bob': 9, 'charlie': 6}

`D.get()`¶

notez bien que D[clef] lance une exception si la clé n’est pas présente
une alternative - sans exception - est d’utiliser la méthode get()

D.get(cle) retourne la valeur associée à la clé si elle est présente, None sinon
D.get(clef, un_truc) retourne un_truc quand la clé n’est pas présente

# la clé 'marc' n'est pas présente

# plutôt que cette vilaine circonlocution...

try:
    x = D['marc']
except KeyError as e:
    x = "?"

x

'?'

# c'est quand même plus lisible comme ça:

D.get('marc', '?')

'?'

itération sur un dictionnaire¶

D.items() retourne une vue sur les (clef, valeur) de D
D.keys() retourne une vue sur les clefs de D
D.values() retourne une vue sur les valeurs de D

# l'idiome pour itérer sur
# un dictionnaire

for k, v in D.items():
    print(f"{k=} {v=}")

k='alice' v=35
k='bob' v=9
k='charlie' v=6

itérer sur le dictionnaire ?

on peut aussi itérer directement sur le dictionnaire, qui est équivalent à itérer sur d.keys()

for k in D:
    # c'est légal, on itère sur les clés
    print(k)

c’est à rapprocher d’ailleurs du comportement de l’opérateur in sur le dictionnaire, voir plus haut

qu’est-ce qu’une vue ?¶

c’est un objet qui donne une vue dynamique sur un dictionnaire D
i.e. qui “suit” les changements futurs
par oppposition à: on calculerait les propriétés de D à cet instant

clefs = D.keys()

clefs

dict_keys(['alice', 'bob', 'charlie'])

# ici clefs est une vue
del D['bob']

clefs

dict_keys(['alice', 'charlie'])

méthodes sur les dictionnaires¶

ici à nouveau, il y a plein d’autres méthodes très utiles, à découvrir ici

création automatique de valeurs (avancé)¶

utile pour alléger votre code
si vous savez que vos valeurs seront toujours, par exemple, une liste
collections.defaultdict est une sous-classe de dict
qui ne lève pas d’exception en cas de défaut de la clé
mais dans ce cas va créer, toujours par exemple, une liste vide
ce qui évite de devoir tester la présence de la clé

from collections import defaultdict

# ici je décide que les valeurs sont des listes
dd = defaultdict(list)

# pas d'exception alors que la clé 0 est absente
# au contraire on appelle list() pour l'initialiser
dd[0].append(1)
dd[0].append(2)
dd[0]

[1, 2]

problèmes avec les séquences¶

(1) les recherches sont lentes¶

(2) on ne peut indexer que par un entier¶

récapitulons¶

la solution : les tables de hash¶

le principe¶

la fonction de hash¶

table de hash et Python¶

le set¶

création¶

opérations sur set¶

le set: méthodes¶

le set est mutable¶

éléments acceptables¶

rapide test de performance¶

le set est beaucoup plus rapide¶

le meilleur cas pour la liste¶

le dictionnaire¶

création¶

manipulations usuelles¶

D.get()¶

itération sur un dictionnaire¶

qu’est-ce qu’une vue ?¶

méthodes sur les dictionnaires¶

création automatique de valeurs (avancé)¶

le `set`¶

opérations sur `set`¶

le `set`: méthodes¶

le `set` est mutable¶

`D.get()`¶