containers (2/2)

Licence CC BY-NC-ND, Thierry Parmentelat & Arnaud Legout

from IPython.display import HTML
HTML(filename="_static/style.html")

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#

_images/hash.svg

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.

l’ensemble est non ordonné

(♤) depuis la 3.7 le dictionnaire est une structure ordonnée (il “retient” l’ordre des ajouts)
toutefois cela ne s’applique pas à l’ensemble, ce qui peut créer une légère confusion

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'

frozenset et set

(♤) du coup on peut dire, en quelque sorte, que le frozenset est au set ce que le tuple est à la list

é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.66 ms ± 3.89 μs per loop (mean ± std. dev. of 7 runs, 300 loops each)

x = set(range(100000))

%timeit -n 300 "c" in x

27.3 ns ± 2.63 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

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

x = set(range(2))

%timeit -n 300 "c" in x

17.2 ns ± 1.01 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

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

x = set(range(2))

%timeit -n 300 0 in x

18.5 ns ± 1.06 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

{}

autre moyen ?

voyez-vous un autre moyen de créer un dictionnaire vide ?

réponse

oui vous pouvez deviner que dict() renvoie aussi un dictionnaire vide

# 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]
Dans cette section: