Dictionnaires et algorithmes appliqués

1. Définition

Un dictionnaire est une collection non ordonnée de relations entre clés et valeurs. La sémantique de Python 3.x rapproche la notation des ensembles de celle des dictionnaires, et il y a effectivement des ressemblances entre les deux collections.

À commencer par le fait qu’une clé d’un dictionnaire doit être hashable.

Voyons la liste des méthodes d’un dictionnaire :

>>> dir(dict) 
['__class__', '__contains__', '__delattr__', '__delitem__', '__doc__', 
'__eq__', '__format__', '__ge__', '__getattribute__', '__getitem__', 
'__gt__', '__hash__', '__init__', '__iter__', '__le__', '__len__', 
'__lt__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', 
'__setattr__', '__setitem__', '__sizeof__', '__str__', '__subclasshook__', 
'clear', 'copy', 'fromkeys', 'get', 'items', 'keys', 'pop', 'popitem', 
'setdefault', 'update', 'values'] 

Les méthodes d’une liste qu’un dictionnaire ne possède pas sont :

>>> sorted(set(dir(list))-set(dir(dict))) 
['__add__', '__iadd__', '__imul__', '__mul__', '__reversed__', '__rmul__', 
'append', 'count', 'extend', 'index', 'insert', 'remove', 'reverse', 'sort'] 

En effet, le dictionnaire n’implémente pas d’opérateurs autres que de comparaison. Il n’a pas de notion d’indices mais possède...

1. Récupérer une valeur d’un dictionnaire

Il est assez simple de savoir si une clé est présente dans un dictionnaire :

>>> 1 in d.keys() 
True 
>>> 5 in d.keys() 
False 

Conformément à ce qui a été exposé dans la présentation du dictionnaire, la notion d’indice n’existe pas et il faut travailler avec les clés. Par conséquent, il n’y a pas de notion de tranches :

>>> d = {1: 1, 2: '2'} 
>>> d[1] 
1 
>>> d[1]=3 
>>> d[1:2] 
Traceback (most recent call last): 
File "<stdin>", line 1, in <module> 
TypeError: unhashable type 
>>> del d[1] 
>>> d 
{2: '2'} 

Dans le cas où une clé n’existe pas lorsque l’on tente d’y accéder par l’utilisation de l’opérateur crochet, une exception est levée :

>>> d[5] 
Traceback (most recent call last): 
File "<stdin>", line 1, in <module> 
KeyError: 5 

Dans le cas où l’on ne souhaite pas lever d’exceptions, il existe alors une méthode get qui renvoie None si la clé n’existe pas :

>>> d.get(5) 

Il est également possible de demander une valeur par défaut à la place de None.

>>> d.get(5, 'non') 
'non' 

Attention, le fait de récupérer la valeur par défaut (ou None si non précisé) par l’utilisation de get ne permet pas de déduire la non-existence de la clé, puisque cette valeur par défaut peut également être la valeur associée à la clé.

Le dictionnaire est donc un type essentiel qui est un agrégateur...

1. Rajouter une relation d’ordre

Python 3.x et Python 2.7 disposent d’un dictionnaire muni d’une relation d’ordre. Ceci permet de parcourir les éléments dans un ordre déterminé.

>>> from collections import OrderedDict 
>>> d = OrderedDict() 
>>> d 
OrderedDict() 
>>> d[1]='1' 
>>> d[4]='4' 
>>> d[3]='3' 
>>> d[2]='2' 
>>> d 
OrderedDict([(1, '1'), (4, '4'), (3, '3'), (2, '2')]) 

On voit clairement que l’ordre dans lequel sont présentés les tuples clés valeurs est l’ordre dans lequel ils ont été insérés.

À titre d’exercice d’algorithmique, il peut être utile de se construire un objet permettant de gérer notre propre relation d’ordre. Dans notre cas, nous voulons que les clés restent tout le temps classées :

class orderedDict(dict): 
   def items(self): 
          return sorted(super().items())  
  
def keys(self): 
          return sorted(super().keys()) 
   def values(self): 
          return [self[k] for k in sorted(super().keys())] 
 
   def popitem(self): 
      try: 
         key = list(self.keys())[-1] 
      except IndexError: 
         raise KeyError('dictionary is empty') 
      value = self[key] ...