Implémentation de dictionnaire en Python

Bonjour à tous, le 30 avril, le cours Algorithms for Developers débutera à OTUS, et c'est exactement ce à quoi la publication du matériel d'aujourd'hui est dédiée. Commençons.



Dans cet article, vous apprendrez comment les dictionnaires sont implémentés en Python.
Les dictionnaires sont indexés à l'aide de clés et peuvent être considérés comme des tableaux associés. Ajoutons 3 paires clé / valeur au dictionnaire:

>>> d = {'a': 1, 'b': 2} >>> d['c'] = 3 >>> d {'a': 1, 'b': 2, 'c': 3} 

Les valeurs sont accessibles comme suit:

 >>> d['a'] 1 >>> d['b'] 2 >>> d['c'] 3 >>> d['d'] Traceback (most recent call last): File "<stdin>", line 1, in <module> KeyError: 'd' 

La clé “d” n'existe pas, donc une erreur KeyError se produira.

Tables de hachage

Les dictionnaires en Python sont implémentés à l'aide de tables de hachage. Ce sont des tableaux dont les indices sont calculés à l'aide de fonctions de hachage. Le but de la fonction de hachage est de répartir uniformément les clés dans le tableau. Une bonne fonction de hachage minimise le nombre de collisions, c'est-à-dire la probabilité que différentes clés aient un hachage. Il n'y a pas de telles fonctions de hachage en Python. Ses fonctions de hachage les plus importantes (pour les chaînes et les valeurs entières) produisent des valeurs similaires dans les cas généraux:

 >>> map(hash, (0, 1, 2, 3)) [0, 1, 2, 3] >>> map(hash, ("namea", "nameb", "namec", "named")) [-1658398457, -1658398460, -1658398459, -1658398462] 

Nous supposerons que jusqu'à la fin de cet article, nous utiliserons des chaînes comme clés. La fonction de hachage en Python pour les chaînes est définie comme suit:

 arguments: string object returns: hash function string_hash: if hash cached: return it set len to string's length initialize var p pointing to 1st char of string object set x to value pointed by p left shifted by 7 bits while len >= 0: set var x to (1000003 * x) xor value pointed by p increment pointer p set x to x xor length of string object cache x as the hash so we don't need to calculate it again return x as the hash 

Si vous exécutez le hash('a') en Python, il 12416037344 string_hash() et renverra 12416037344 . Ici, nous utilisons la machine 64 bits par défaut.

Si un tableau de taille utilisé pour stocker les paires valeur / clé, un masque sera utilisé pour calculer l'indice de la cellule de la cellule dans le tableau, qui est calculé comme -1 . Cette approche permet de calculer rapidement les indices des cellules. La probabilité de trouver une cellule vide est assez élevée en raison du mécanisme de redimensionnement, qui est décrit ci-dessous. Cela signifie qu'un calcul simple a du sens dans la plupart des cas. La taille du tableau est 8, l'index pour 'a' sera: hash('a') & 7 = 0 . L'indice pour 'b' est 2, l'indice pour 'c' est 3, l'indice pour 'z' est 3, tout comme pour 'b' , et c'est là que nous obtenons une collision.



Comme nous pouvons le voir, une fonction de hachage en Python fait son travail de manière de qualité lorsque les clés sont séquentielles, ce qui est bien, car vous devez souvent travailler avec de telles données. Cependant, dès que nous ajoutons la touche 'z' , une collision se produit car elle n'est pas cohérente avec les précédentes.

Nous pourrions utiliser une liste chaînée pour stocker des paires, ayant le même hachage, mais cela augmenterait le temps de recherche et ne serait pas égal à O (1) en moyenne. La section suivante décrit la méthode de résolution de collision utilisée pour les dictionnaires en Python.

Adressage ouvert

L'adressage ouvert est une technique de résolution de collision qui utilise le sondage. Dans le cas de 'z' , l'index de la cellule 3 est déjà utilisé dans le tableau, nous devons donc rechercher un autre index qui n'a pas encore été utilisé. L'opération d'ajout d'une paire clé / valeur prend en moyenne O (1), ainsi que l'opération de recherche.

Pour rechercher des cellules libres, une séquence de sondage quadratique est utilisée. Il est implémenté comme suit:

 j = (5*j) + 1 + perturb; perturb >>= PERTURB_SHIFT; use j % 2**i as the next table index; 

La récursivité à (5 * j) +1 augmente rapidement les grandes différences de bits qui n'ont pas affecté l'index d'origine. La variable "perturb" dans ce cas reprend les autres bits du code de hachage.

Regardons par curiosité ce qui se passe si nous avons un exemple de séquence avec un tableau de taille 32 et j = 3.

3 -> 11 -> 19 -> 29 -> 5 -> 6 -> 16 -> 31 -> 28 -> 13 -> 2 ...

Vous pouvez en savoir plus sur cette séquence de sondage en vous référant au code source dictobject.c . Une explication détaillée du mécanisme de sondage se trouve en haut du fichier.



Regardons le code source Python avec cet exemple.

Structures de dictionnaire C

La structure C suivante est utilisée pour stocker l'entrée dans le dictionnaire: paire clé / valeur. Le hachage, la clé et la valeur sont stockés. PyObject est la classe de base pour les objets en Python.

 typedef struct { Py_ssize_t me_hash; PyObject *me_key; PyObject *me_value; } PyDictEntry; 

La structure suivante est un dictionnaire. ma_fill est le nombre total de cellules utilisées et inactives. Une cellule est considérée comme inactive lorsqu'une paire de clés est supprimée. ma_used est le nombre de cellules utilisées (actives). ma_mask est égal à la taille du tableau -1 et est utilisé pour calculer l'indice de cellule. ma_table est un tableau et ma_smalltable est le tableau d'origine de taille 8.

 typedef struct _dictobject PyDictObject; struct _dictobject { PyObject_HEAD Py_ssize_t ma_fill; Py_ssize_t ma_used; Py_ssize_t ma_mask; PyDictEntry *ma_table; PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash); PyDictEntry ma_smalltable[PyDict_MINSIZE]; }; 

Initialisation du vocabulaire

Lorsque vous venez de créer un dictionnaire, la fonction PyDict_New() est PyDict_New() . J'ai supprimé quelques lignes et converti le code C en pseudo-code pour me concentrer sur les concepts clés.

PyDict_New() :

• Renvoie un objet dictionnaire;
• Alloue un nouvel objet dictionnaire;
• Efface la table du dictionnaire;
• Définit le nombre de cellules de dictionnaire utilisées et de cellules inutilisées ( ma_fill ) sur 0;
• Définit le nombre de cellules actives ( ma_used ) à 0;
• Définit le masque de dictionnaire ( ma_value ) sur une valeur égale à la taille du dictionnaire - 1 = 7;
• Définit la fonction de recherche de dictionnaire lookdict_string ;
• Renvoie l'objet de dictionnaire alloué.

Ajouter un élément

Lorsqu'une nouvelle paire clé / valeur est ajoutée, PyDict_SetItem() appelée. Cette fonction accepte un pointeur vers un objet dictionnaire et une paire clé / valeur en entrée. Il vérifie si la clé est une chaîne et évalue le hachage ou réutilise le cache s'il en existe un. insertdict() est appelé pour ajouter une nouvelle paire clé / valeur et la taille du dictionnaire change si le nombre de cellules utilisées et inutilisées est supérieur aux 2/3 de la taille du tableau.

Pourquoi exactement 2/3? Cela est nécessaire pour garantir que la séquence de sonde puisse trouver des cellules libres assez rapidement. Plus tard, nous considérerons la fonction de redimensionnement.

 arguments: dictionary, key, value returns: 0 if OK or -1 function PyDict_SetItem: if key's hash cached: use hash else: calculate hash call insertdict with dictionary object, key, hash and value if key/value pair added successfully and capacity over 2/3: call dictresize to resize dictionary's table 

inserdict() utilise la fonction de recherche lookdict_string() pour trouver une cellule libre. La même fonction est utilisée pour rechercher une clé.

lookdict_string() calcule l'index de cellule en utilisant des valeurs de hachage et de masque. Si elle ne peut pas trouver la clé par la valeur de la cellule index = hash & mask (slot index = hash & mask), elle commence à sonder en utilisant le cycle décrit ci-dessus jusqu'à ce qu'elle trouve une cellule libre. À la première tentative de vérification, si la clé est null , elle renvoie une cellule inutilisée si elle a été trouvée lors de la première recherche. Cela garantit la priorité pour la réutilisation des cellules précédemment supprimées.
Nous voulons ajouter les paires clé / valeur suivantes: {'a': 1, 'b': 2′, 'z': 26, 'y': 25, 'c': 5, 'x': 24} . Voici ce qui va se passer:

La structure du dictionnaire est allouée avec une taille de table de 8.

• PyDict_SetItem: key = 'a', value = 1
  
  • hash = hash ('a') = 12416037344
  • insertdict
    
    • lookdict_string
      
      • index des emplacements = hachage et masque = 12416037344 et 7 = 0
      • l'emplacement 0 n'est pas utilisé, renvoyez cette cellule
    • initialisation de l'entrée à l'index 0 avec clé, valeur et hachage
    • ma_used = 1, ma_fill = 1
• PyDict_SetItem: key = 'b', value = 2
  
  • hachage = hachage («b») = 12544037731
  • insertdict
    
    • lookdict_string
      
      • index des emplacements = hachage et masque = 12544037731 et 7 = 3
      • l'emplacement 3 n'est pas utilisé, renvoyez cette cellule
    • initialisation de l'entrée à l'index 3 avec clé, valeur et hachage
    • ma_used = 2, ma_fill = 2
      
• PyDict_SetItem: key = 'z', value = 26
  
  • hachage = hachage («z») = 15616046971
  • insertdict
    
    • lookdict_string
      
      • index des emplacements = hachage et masque = 15616046971 et 7 = 3
      • l'emplacement 3 est utilisé, essayez une autre cellule: 5 est libre
        
      
      initialisation de l'entrée à l'index 5 avec clé, valeur et hachage
      ma_used = 3, ma_fill = 3
      
• PyDict_SetItem: key = 'y', value = 25
  
  • hachage = hachage («y») = 15488046584
  • insertdict
    
    • lookdict_string
      
      • index de l'emplacement = hachage et masque = 15488046584 et 7 = 0
      • l'emplacement 0 est utilisé, essayez une autre cellule: 1 est libre
    • initialisation de l'entrée à l'index 1 avec clé, valeur et hachage
    • ma_used = 4, ma_fill = 4

PyDict_SetItem: key = 'c', value = 3

• hachage = hachage («c») = 12672038114
• insertdict
  
  • lookdict_string
    
    • index de l'emplacement = hachage et masque = 12672038114 et 7 = 2
    • l'emplacement 2 n'est pas utilisé, renvoyez cette cellule
  • initialisation de l'entrée à l'index 2 avec clé, valeur et hachage
  • ma_used = 5, ma_fill = 5

PyDict_SetItem: key = 'x', value = 24

• hachage = hachage ('x') = 15360046201
• insertdict
  
  • lookdict_string
    
    • index des emplacements = hachage et masque = 15360046201 & 7 = 1
    • l'emplacement 1 est utilisé, essayez une autre cellule: 7 est libre
  • initialisation de l'entrée à l'index 7 avec clé, valeur et hachage
  • ma_used = 6, ma_fill = 6

Voici ce que nous obtenons:



Maintenant, 6 cellules sur 8 sont utilisées, plus des 2/3 de la capacité de la baie sont occupés. dictresize() est appelé pour allouer un tableau plus grand. Cette fonction copie également les enregistrements de l'ancienne table vers la nouvelle.

dictresize () est appelé avec minused = 24 dans notre cas, où 4 * ma_used . 2 * ma_used utilisé lorsque le nombre de cellules utilisées est très important (plus de 50 000). Pourquoi 4 fois plus de cellules? Cela réduit le nombre d'étapes pour implémenter le redimensionnement et augmente la parcimonie.

La nouvelle taille du tableau doit être supérieure à 24, elle est calculée en décalant la taille actuelle de 1 bit vers la gauche jusqu'à ce que la taille du tableau devienne supérieure à 24. Par conséquent, ce sera 32, par exemple 8 -> 16 -> 32.

Voici ce qui arrive à notre table lors du redimensionnement: une nouvelle table de taille 32 est mise en évidence. Les anciennes entrées de table sont insérées dans la nouvelle table en utilisant la nouvelle valeur de masque de 31. Le résultat est le suivant:



Supprimer des éléments

PyDict_DelItem() est appelé pour supprimer des enregistrements. Le hachage est calculé pour la clé d'enregistrement, puis la fonction de recherche est appelée pour renvoyer l'enregistrement. Maintenant, la cellule est vide.

Nous voulons supprimer la clé c de notre dictionnaire. En conséquence, nous obtenons le tableau suivant:



Notez que l'opération de suppression d'un élément ne modifie pas la taille du tableau si le nombre de cellules utilisées est bien inférieur à leur nombre total. Cependant, lorsqu'une paire clé / valeur est ajoutée, la nécessité de redimensionner dépend du nombre de cellules utilisées et inactives, de sorte que l'opération d'ajout peut également réduire le tableau.

Cette publication a pris fin, et nous attendons traditionnellement vos commentaires et invitons tout le monde à une leçon ouverte , qui se tiendra le 18 avril.