7. Dictionnaires et ensembles

Après les séquences, nous abordons ici deux autres structures de données fondamentales en Python, les dictionnaires (dict) et les ensembles (set). Elles ont en commun de reposer sur des tables de hachage conduisant à des performances algorithmiques en \(\Theta(1)\) pour les opérations de recherche, d’insertion et de suppression. Au détriment d’une occupation mémoire plus importante que pour les séquences.

7.1. Les objets « hashables »

Seuls les objets immutables sont « hashables » car leur valeur de hachage est constante tout au long de la durée de vie. Une valeur de hachage différente pour chaque objet différent est retournée par la fonction hash():

>>> hash("a string")
-7948514637191243730
>>> hash("another string")
-722956108645606665
>>> hash("one more")
7230730472324293320

la fonction hash() est un wrapper autour de la méthode __hash__() de l’objet concerné. Cette méthode doit être redéfinie lorsqu’on écrit sa propre classe:

>>> "a string".__hash__()
-7948514637191243730
>>> "another string".__hash__()
-722956108645606665
>>> "one more".__hash__()
7230730472324293320

Lorsque l’objet est mutable, tenter d’obtenir sa valeur de hachage lève une exception:

>>> hash([1, 2, 3])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

Pour les containers, non seulement le container lui même doit être immutable, mais également l’ensemble des objets qu’il contient, sinon une exception est levée:

>>> t1 = (1, 2, 3)
>>> hash(t1)
2528502973977326415

>>> t2 = (1, 2, [1, 2, 3])
>>> hash(t2)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

Le set est un cas particulier de container. Dans sa version classique, il est mutable et ne peut donc pas être utilisé comme clé de hachage:

>>> hash(set([1, 2, 3]))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'set'

Mais il dispose également d’une version « frozen » imutable (frozenset), ce qui le rend éligible:

>>> hash(frozenset([1, 2, 3]))
-7699079583225461316

7.2. Les dictionnaires

Le dictionnaire est une structure fondamentale dans laquelle l’interpréteur Python stocke par exemple son environnement. Par exemple:

>>> type(__builtins__.__dict__)
<class 'dict'>
>>> len(__builtins__.__dict__)
153
>>> __builtins__.__dict__['__doc__']
"Built-in functions, exceptions, and other objects.\n\nNoteworthy: None is the `nil' object; Ellipsis represents `...' in slices."

Explorons quelques notions relatives aux dictionnaires.

7.2.1. Les dictcomp

Comme pour les listes et les générateurs, Python dispose d’une syntaxe concise et lisible pour créer des dictionnaires. Le principe est de produire une paire clé-valeur à partir de séquences:

>>> d = { chr(c):c for c in range(91,97) }
>>> d
{'[': 91, '\\': 92, ']': 93, '^': 94, '_': 95, '`': 96}

Comme pour les listcomp on peut insérer un prédicat simple:

>>> d = { chr(c):c for c in range(32,127) if not chr(c).isalnum() }
>>> d
{' ': 32, '!': 33, '"': 34, '#': 35, '$': 36, '%': 37, '&': 38, "'": 39, '(': 40, ')': 41, '*': 42, '+': 43, ',': 44, '-': 45, '.': 46, '/': 47, ':': 58, ';': 59, '<': 60, '=': 61, '>': 62, '?': 63, '@': 64, '[': 91, '\\': 92, ']': 93, '^': 94, '_': 95, '`': 96, '{': 123, '|': 124, '}': 125, '~': 126}

Exercice

Construire un dictionnaire d’un million d’éléments avec une boucle classique puis avec un dictcomp. Comparer les temps d’exécution. Conclusions ?

7.2.2. Taille en mémoire

Pour la gestion des collisions, l’utilisation d’une table de hachage pour implémenter le dictionnaire est plus gourmande en mémoire que la list. Une liste de 1 million d’éléments occupe environ 9 Mb:

>>> import sys
>>> l = [i for i in range(int(1e6))]
>>> print('size of list : ', sys.getsizeof(l))
size of list : 8697464

Pour une taille équivalente, le dictionnaire nécessite environ 5 fois plus de mémoire (42 Mb):

>>> d = { str(i):i for i in range(int(1e6))}
>>> print('size of dict : ', sys.getsizeof(d))
size of dict :  41943144

C’est le prix à payer pour conserver un temps d’accès aux éléments en \(\Theta(1)\).

7.2.3. Clés et valeurs

Les méthodes dict.keys() et dict.values() retournent respectivement les clés et les valeurs du dictionnaire sous forme de vue dynamique et non pas de structure de donnée statique (une liste par exemple):

>>> d = { 'ENGIE':14.580, 'BNP PARIBAS':63.64, 'CARREFOUR':16.695, 'DANONE':70.17 }

>>> k = d.keys()
>>> type(k)
<class 'dict_keys'>
>>> k
dict_keys(['ENGIE', 'BNP PARIBAS', 'CARREFOUR', 'DANONE'])

>>> v = d.values()
>>> type(v)
<class 'dict_values'>
>>> v
dict_values([14.58, 63.64, 16.695, 70.17])

Une fois créées, ces vues sont une représentation dynamiques des clés et des valeurs du dictionnaire. Si on retire un élément du dictionnaire:

>>> d.pop('ENGIE')
14.58

Les vues dynamiques déjà créées reflètent les modifications intervenues sur le dictionnaire:

>>> k
dict_keys(['BNP PARIBAS', 'CARREFOUR', 'DANONE'])
>>> v
dict_values([63.64, 16.695, 70.17])

7.2.4. Performances

L’utilisation d’une table de hachage dans les dictionnaires a pour conséquence que le test d’appartenance est indépendant de la taille, contrairement à ce qui se passe pour une séquence, pour laquelle la totalité de la collection doit être parcourue dans le cas où l’élément testé n’est pas présent.

import timeit

# 1e6 paires clé:valeur dans un dictionnaire
d = { i:str(i) for i in range(1000000) }

setup = 'from __main__ import d' # setup for timeit measurement

# 'in' test

stmt = '{} in d'

for i in [9, 99, 999, 9999, 99999, 999999, 9999999]:
    s = stmt.format(i)
    b = eval(s)
    res = timeit.timeit(s, number=10, setup=setup)
    print('{:>12} : {:>5s} : {:>6.2f} µs'.format(s, str(b), res/1e-6))

D’autre part, le temps de recherche est du même ordre de grandeur, que la clé recherchée soit présente ou pas:

      9 in d :  True :   0.96 µs
     99 in d :  True :   0.96 µs
    999 in d :  True :   0.96 µs
   9999 in d :  True :   1.28 µs
  99999 in d :  True :   1.28 µs
 999999 in d :  True :   1.28 µs
9999999 in d : False :   0.96 µs

Il en est de même pour les accés en lecture.

import timeit

# 1e6 paires clé:valeur dans un dictionnaire
d = { i:str(i) for i in range(1000000) }

setup = 'from __main__ import d' # setup for timeit measurement

# 'get' test

stmt = 'd.get({}, -1)'

for i in [9, 99, 999, 9999, 99999, 999999, 9999999]:
    s = stmt.format(i)
    b = eval(s)
    res = timeit.timeit(s, number=10, setup=setup)
    print('{:>20} : {:>6} : {:>6.2f} µs'.format(s, b, res/1e-6))

Les temps d’accès sont supérieurs à une simple recherche de clé, parce qu’il y a une opération en plus (la récupération de la valeur):

      d.get(9, -1) :      9 :   1.60 µs
     d.get(99, -1) :     99 :   1.60 µs
    d.get(999, -1) :    999 :   1.92 µs
   d.get(9999, -1) :   9999 :   1.60 µs
  d.get(99999, -1) :  99999 :   1.92 µs
 d.get(999999, -1) : 999999 :   1.92 µs
d.get(9999999, -1) :     -1 :   1.60 µs

popitem() est un peu plus rapide car l’élément retourné n’est pas choisi

import timeit

# 1e6 paires clé:valeur dans un dictionnaire
d = { i:str(i) for i in range(1000000) }

setup = 'from __main__ import d' # setup for timeit measurement

# 'popitem()' test

stmt = 'd.popitem()'

for i in range(5):
    b = eval(stmt)
    res = timeit.timeit(stmt, number=10, setup=setup)
    print('{:>20} : ({},{}) : {:>6.2f} µs'.format(stmt, *b, res/1e-6))

Les temps sont donc inférieurs à ceux rencontrés pour get():

d.popitem() : (999999,999999) :   1.28 µs
d.popitem() : (999988,999988) :   1.28 µs
d.popitem() : (999977,999977) :   1.28 µs
d.popitem() : (999966,999966) :   1.28 µs
d.popitem() : (999955,999955) :   1.28 µs

7.2.5. Gérer l’absence de clé

Tenter d’accéder sans précaution à une clé de dictionnaire non existante, lève une exception:

>>> d = { 'ENGIE':14.580, 'BNP PARIBAS':63.64, 'CARREFOUR':16.695, 'DANONE':70.17 }
>>> d['LVMH']
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'LVMH'

On peut traiter ce cas particulier de plusieurs façons.

Une première façon pythonique de le faire est d’encapsuler la tentative d’accès dans un bloc try - except:

>>> try:
...     d['LVMH']
... except:
...     print('Key is missing')
...
Key is missing

Mais plutôt que de l’interrompre avec une exception, on peut souhaiter continuer le traitement, auquel cas on peut utiliser une valeur par défaut retournée par la méthode dict.get(). Cette valeur par défaut est le second argument s’il est présent, None sinon:

>>> print(d.get('LVMH', 'NA'))
'NA'
>>> print(d.get('LVMH'))
None

Mais si dict.get() permet de fournir une valeur et de ne pas interrompre le traitement, la structure du dictionnaire n’est pas modifiée:

>>> k
dict_keys(['BNP PARIBAS', 'CARREFOUR', 'DANONE'])
>>> v
dict_values([63.64, 16.695, 70.17])

Si le dictionnaire doit être mis à jour, il faudrait une instruction d’affectation supplémentaire, ce qui est coûteux. La méthode setdefault() est une réponse intéressante à ce problème puisqu’elle retourne la clé si elle est présente, ou l’initialise sinon:

>>> d.setdefault('LVMH', 249.75)
249.75

et le dictionnaire est bien modifié:

>>> d.keys()
dict_keys(['BNP PARIBAS', 'CARREFOUR', 'DANONE', 'LVMH'])
>>> d.values()
dict_values([63.64, 16.695, 70.17, 249.75])

7.2.6. defaultdict: une alternative

Une autre façon de gérer l’absence de clé dans un dictionnaire est d’utiliser le defaultdict qui permet de créer des valeurs à la volée lorsqu’on tente d’y accéder et qu’elles n’existent pas.

L’idée est de fournir à la construction une factory utilisée pour produire une valeur par défaut lorsqu’on passe une clé non existante à la méthode __getitem__() (appelée chaque fois que l’on tente d’accéder à un élément du dictionnaire avec la syntaxe d[key] ).

defaultdict fait partie du module collections:

>>> from collections import defaultdict

Ici la factory est le constructeur de la classe list:

>>> dd = defaultdict(list)

A la création, le dictionnaire est bien entendu vide:

>>> dd
defaultdict(<class 'list'>, {})

>>> k = dd.keys()
>>> k
dict_keys([])
>>> v = dd.values()
>>> v
dict_values([])

Tenter d’accéder à une clé non existante ne lève pas d’exception mais crée une liste vide comme valeur:

>>> dd['a']
[]

Le dictionnaire est bien modifié:

>>> dd
defaultdict(<class 'list'>, {'a': []})

La factory retourne une référence vers la valeur créée, qui peut alors être utilisée directement:

>>> dd['b'].append(2)
>>> dd
defaultdict(<class 'list'>, {'a': [], 'b': [2]})

Par contre, la factory n’est appelée que lorsqu’on cherche à accéder à l’élément du dictionnaire avec la syntaxe dd[key] qui appelle la méthode __getitem__(). Les autres méthodes d’accès ne déclenchent pas l’exécution de la factory.

>>> dd.get('c')
>>> dd
defaultdict(<class 'list'>, {'a': [], 'b': [2]})

7.2.7. Un defaultdict multi dimensionnel

Pour organiser des données multidimensionnelles, on peut utiliser des dictionnaires de dictionnaires, des dictionnaires de dictionnaires de dictionnaires, etc… C’est la notion de dictionnaire multidimensionnel.

Une fonction récursive est utilisée :

# Utility function to create multi dim dictionary
def multi_dict(K, type):
    if K == 1:
        return defaultdict(type)
    else:
        return defaultdict(lambda: multi_dict(K-1, type))

Son utilisation est directe, et l’utilisation d’un defaultdict autorise à ne prendre aucune précaution sur l’existence des clés:

>>> d = multi_dict(3, int)
>>> d[sexe][age][dpt] = 17 # donnée fantaisiste

7.2.8. Un dictionnaire “user defined”

Il peut arriver que les classes concrètes fournies par Python ne conviennent pas parfaitement à l’usage qu’on souhaite. Il est alors possible d’utiliser les Abstract Base Class (ABC) pour développer ses propres implémentations. Ces ABC fournissent un certain nombre de méthodes abstraites qu’il faut alors redéfinir dans la classe concrète qui en hérite.

On trouvera des informations complémentaires sur les objets Python dans la section Emulating container types.

La première étape est d’hériter de la collection UserDict et de redéfinir les méthodes abstraites __getitem__() (lecture), __setitem__() (écriture), __delitem__() (suppression), __iter__() (itération)et __len__() (taille).

Observer attentivement la redéfinition des méthodes ci dessous:

# transformed_dict.py

import collections

class TransformedDict(collections.UserDict):
    """A dictionary that applies an arbitrary key-altering
    function before accessing the keys"""

    # Constructeur
    def __init__(self, *args, **kwargs):
        self.store = dict() # un dictionnaire est utilisé pour le stockage interne
        self.update(dict(*args, **kwargs))  # alimenté par les paramètres du constructeur

    # look up with transformed key
    def __getitem__(self, key):
        return self.store[key]

    # storage with transformed key
    def __setitem__(self, key, value):
        self.store[key] = value

    # delete internal dict entry
    def __delitem__(self, key):
        del self.store[key]

    # return an iterator over the internal dict
    def __iter__(self):
        return iter(self.store)

    # return len() of internal dict
    def __len__(self):
        return len(self.store)

Vérifions maintenant que les méthodes redéfinies fonctionnent correctement et confèrent à notre TransformedDict toutes les propriétés d’un dictionnaire classique.

On commence par importer TransformedDict:

>>> from transformed_dict import TransformedDict

Le constructeur fonctionne:

>>> d = TransformedDict( { i:ord(i) for i in 'abcdef' } )
>>> type(d)
<class 'transformed_dict.TransformedDict'>

La redéfinition de __getitem__() fait que l’accesseur [ ] fonctionne également:

>>> d['a'] # __getitem__()
97
>>> len(d) # __len__()
6

La redéfinition de __setitem__() permet d’utiliser également la syntaxe [ ] en écriture:

>>> d['g'] = 103 # __setitem__()
>>> len(d)
7

La redéfinition de __delitem__() rend opérationnelle la fonction del():

>>> del d['a'] # __delitem__()
>>> d['a']
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "C:\Users\User\Documents\ESIEE\AdvancedPython\transformed_dict.py", line 16, in __getitem__
    return self.store[key]
KeyError: 'a'

La redéfinition de __len__() rend opérationnelle la fonction len():

>>> len(d)
6

La redéfinition de __iter__() dote notre TransformedDict d’un itérateur:

>>> i = iter(d) # __iter__()
>>> i
<dict_keyiterator object at 0x00000130A6BA8408>
>>> i.__next__()
'e'
>>> i.__next__()
'f'

Les méthodes de base ayant été redéfinies, par héritage, les méthodes pop(), popitem(), clear(), update(), et setdefault() sont également disponibles:

>>> d.pop('b')
98
>>> len(d)
5
>>> d.popitem()
('e', 101)
>>> len(d)
4
>>> d.update( { i:ord(i) for i in 'abc' } )
>>> len(d)
6
>>> c = 'a'
>>> d.setdefault(c, ord(c))
97
>>> len(d)
6
>>> c = 'h'
>>> d.setdefault(c, ord(c))
104
>>> len(d)
7

Il en est de même pour les méthodes __contains__(), keys(), items(), values(), get(), __eq__(), and __ne__():

>>> 'a' in d
True
>>> 'z' in d
False
>>> d.keys()
KeysView(<transformed_dict.TransformedDict object at 0x00000000022F9A58>)
>>> d.items()
ItemsView(<transformed_dict.TransformedDict object at 0x00000000022F9A58>)
>>> d.values()
ValuesView(<transformed_dict.TransformedDict object at 0x00000000022F9A58>)
>>> d.get('a', -1)
97
>>> d.get('z', -1)
-1
>>> dd = d
>>> dd == d
True
>>> dd != d
False

A cette étape le dictionnaire est presque fonctionnel, mais son affichage n’est pas encore opérationnel:

>>> d
<transformed_dict.TransformedDict object at 0x00000000022F9A58>

Il faut redéfinir la méthode __repr__() (et éventuellement __str__()). Lire Difference between __str__ and __repr__ in Python pour comprendre la différence entre les deux.

def __repr__(self):
        return '{}({})'.format(self.__class__.__name__, repr(self.store))

Maintenant l’affichage du dictionnaire produit une chaîne de caractères informative, qui peut éventuellement être réutilisée pour la construction d’un autre objet:

>>> d
TransformedDict({'b': 98, 'a': 97, 'h': 104, 'f': 102, 'e': 101, 'd': 100, 'c': 99})

La représentation textuelle fournie par la méthode __repr__() permettre de (re)créer l’objet:

>>> a = eval(repr(d))
>>> a
TransformedDict({'b': 98, 'a': 97, 'h': 104, 'f': 102, 'e': 101, 'd': 100, 'c': 99})

A cette étape, nous avons donc ré implémenté un dictionnaire parfaitement fonctionnel. Cependant, il n’apporte aucune valeur ajoutée par rapport au dict de base. C’est l’objectif de l’exercice qui suit.

Exercice

Modifier la classe TransformedDict pour implémenter un dictionnaire dont les clés sont insensibles à la casse. Pour cela, il faut utiliser le dictionnaire interne pour le stockage et transformer les clés avant insertion dans ce dictionnaire. La transformation utilisée ici sera la mise en minuscules de la clé. Cela devra conduire au comportement suivant:

>>> d['ABC'] = 1
>>> d['ABC']
1
>>> d['abc']
1
>>> d['AbC']
1

7.2.9. Le Counter

Le Counter est une classe fille de dict qui possède des méthodes optimisées pour le comptage. Son constructeur accepte une séquence ou un dictionnaire.

Exercice

Compter les occurrences de chacun des caractères présents dans le texte de Victor Hugo, Notre Dame de Paris. En extraire les 10 plus fréquents et les 10 moins fréquents. Avec les structures de données traditionnelles. Puis avec le Counter. Vous mesurerez les performances algorithmiques des 2 solutions avec la fonction perf_counter().

L’oeuvre est lue puis stockée dans une chaîne de caractères avec le code suivant:

with open('NotreDameDeParis.txt', encoding='utf8', mode='r') as f:
    s = f.read()

7.3. Les ensembles (set)

Les ensembles (set) sont des structures de données qui reposent sur le même principe que les clés des dictionnaires (table de hachage). En conséquence, chaque élément qu’ils contiennent doit être hashable et est unique par construction. Les set ne sont pas des séquences et ne supportent donc pas les opérations de slicing. Ils fournissent par contre de puissantes opérations ensemblistes que l’on peut mettre à profit pour la recherche.

On considère le problème suivant : on dispose d’un premier ensemble E de n nombres rééls uniques et d’un second ensemble V de k ( \(k << n\) ) nombre réels uniques. On s’assurera par construction de l’ensemble V que \(k/2\) valeurs sont incluses dans E et que \(k/2\) valeurs ne le sont pas. On se propose de compter le nombre d’éléments de V contenus dans E et de mesurer les performances de cette opération lorsque E et V sont implémentés avec différentes structures de données. On s’intéressera ici aux containers list, array et set. Pour fixer les idées on prendra n = \(10^6\) et k = \(10^3\).

Exercice

Ecrire le code permettant de comparer les performances de l’opération de comptage pour les 3 structures de données ci dessus et en tirer les conclusions. Par construction de chacune, vous devez pouvoir inférer la hiérarchie entre elles avant d’écrire le code.