Pourquoi l'ordre dans les dictionnaires et les ensembles est-il arbitraire ?

Question

Je ne comprends pas comment le bouclage d'un dictionnaire ou d'un ensemble en python se fait par ordre "arbitraire".

Je veux dire, c'est un langage de programmation donc tout dans le langage doit être déterminé à 100%, correct ? Python doit avoir une sorte d'algorithme qui décide quelle partie du dictionnaire ou de l'ensemble est choisie, la première, la deuxième et ainsi de suite.

Qu'est-ce que je rate ?

Answer 1

Note : Cette réponse a été rédigée avant la mise en œuvre de la dict a changé, dans Python 3.6. La plupart des détails d'implémentation de cette réponse s'appliquent toujours, mais l'ordre d'énumération des clés dans le fichier dictionnaires n'est plus déterminé par des valeurs de hachage. L'implémentation de l'ensemble reste inchangée.

L'ordre n'est pas arbitraire, mais dépend de l'historique d'insertion et de suppression du dictionnaire ou de l'ensemble, ainsi que de l'implémentation spécifique de Python. Dans la suite de cette réponse, pour " dictionnaire ", vous pouvez également lire " ensemble " ; les ensembles sont implémentés comme des dictionnaires avec seulement des clés et sans valeurs.

Les clés sont hachées et les valeurs de hachage sont affectées à des emplacements dans une table dynamique (qui peut croître ou décroître en fonction des besoins). Et ce processus de mappage peut conduire à des collisions, ce qui signifie qu'une clé devra être placée dans un suivant sur la base de ce qui existe déjà.

L'énumération du contenu passe en boucle sur les emplacements, et les clés sont donc énumérées dans l'ordre dans lequel elles se trouvent. actuellement résident dans le tableau.

Prenez les clés 'foo' y 'bar' par exemple, et supposons que la taille de la table est de 8 emplacements. En Python 2.7, hash('foo') est -4177197833195190597 , hash('bar') est 327024216814240868 . Modulo 8, cela signifie que ces deux clés sont placées dans les fentes 3 et 4 alors :

>>> hash('foo')
-4177197833195190597
>>> hash('foo') % 8
3
>>> hash('bar')
327024216814240868
>>> hash('bar') % 8
4

Cela informe leur ordre d'inscription :

>>> {'bar': None, 'foo': None}
{'foo': None, 'bar': None}

Tous les emplacements sauf 3 et 4 sont vides, en bouclant sur le tableau, on obtient d'abord l'emplacement 3, puis l'emplacement 4, donc 'foo' est listé avant 'bar' .

bar y baz Cependant, les valeurs de hachage sont séparées par un écart d'exactement 8 et correspondent donc exactement au même emplacement, 4 :

>>> hash('bar')
327024216814240868
>>> hash('baz')
327024216814240876
>>> hash('bar') % 8
4
>>> hash('baz') % 8
4

Leur ordre dépend maintenant de la clé qui a été placée en premier ; la deuxième clé devra être déplacée vers un emplacement suivant :

>>> {'baz': None, 'bar': None}
{'bar': None, 'baz': None}
>>> {'bar': None, 'baz': None}
{'baz': None, 'bar': None}

L'ordre du tableau diffère ici, car l'une ou l'autre des clés a été insérée en premier.

Le nom technique de la structure sous-jacente utilisée par CPython (l'implémentation Python la plus couramment utilisée) est un fichier table de hachage un qui utilise l'adressage ouvert. Si vous êtes curieux, et que vous comprenez suffisamment bien le C, jetez un coup d'oeil à la page Mise en œuvre C pour tous les détails (bien documentés). Vous pouvez également regarder ceci Présentation de Pycon 2010 par Brandon Rhodes sur la façon dont CPython dict ou prenez un exemplaire de Beau Code qui comprend un chapitre sur l'implémentation écrit par Andrew Kuchling.

Notez qu'à partir de Python 3.3, une graine de hachage aléatoire est également utilisée, rendant les collisions de hachage imprévisibles afin d'empêcher certains types de déni de service (où un attaquant rend un serveur Python non réactif en provoquant des collisions de hachage en masse). Cela signifie que l'ordre d'un dictionnaire ou d'un ensemble donné est alors également dépend de la graine de hachage aléatoire pour l'invocation Python actuelle.

D'autres implémentations sont libres d'utiliser une structure différente pour les dictionnaires, tant qu'elles satisfont l'interface Python documentée pour ceux-ci, mais je crois que toutes les implémentations jusqu'à présent utilisent une variation de la table de hachage.

CPython 3.6 introduit un nouveau dict qui maintient l'ordre d'insertion, et qui est plus rapide et plus efficace en mémoire. Plutôt que de conserver une grande table éparse où chaque ligne fait référence à la valeur de hachage stockée, ainsi qu'aux objets clé et valeur, la nouvelle implémentation ajoute un plus petit hachage tableau qui ne fait référence qu'aux indices d'une table "dense" distincte (qui ne contient qu'autant de lignes qu'il y a de paires clé-valeur réelles), et c'est la table dense qui liste les éléments contenus dans l'ordre. Voir le proposition à Python-Dev pour plus de détails . Notez que dans Python 3.6, ceci est considéré comme un détail de la mise en œuvre Python-the-language ne précise pas que les autres implémentations doivent conserver l'ordre. Cela a changé dans Python 3.7, où ce détail a été modifié. élevé pour être un spécification du langage pour qu'une implémentation soit correctement compatible avec Python 3.7 ou une version plus récente, elle doit doit copient ce comportement de préservation de l'ordre. Et pour être explicite : ce changement ne s'applique pas aux ensembles, car les ensembles ont déjà une "petite" structure de hachage.

Python 2.7 et plus récent fournit également une fonction OrderedDict clase une sous-classe de dict qui ajoute une structure de données supplémentaire pour enregistrer l'ordre des clés. Au prix d'une certaine vitesse et d'une mémoire supplémentaire, cette classe se souvient de l'ordre dans lequel vous avez inséré les clés ; l'énumération des clés, des valeurs ou des éléments se fera alors dans cet ordre. Elle utilise une liste doublement liée stockée dans un dictionnaire supplémentaire pour maintenir efficacement l'ordre à jour. Voir le post de Raymond Hettinger exposant l'idée . OrderedDict Les objets ont d'autres avantages, comme le fait d'être re-commandable .

Si vous souhaitiez un ensemble ordonné, vous pouvez installer la oset paquet ; il fonctionne sur Python 2.5 et plus.

Answer 2

Il s'agit plutôt d'une réponse à Python 3.41 Un ensemble avant qu'elle ne soit fermée en tant que doublon.

---

Les autres ont raison : ne vous fiez pas à l'ordre. Ne prétendez même pas qu'il y en a un.

Cela dit, il y a un sur laquelle vous pouvez compter :

list(myset) == list(myset)

C'est-à-dire que l'ordre est stable .

---

Comprendre pourquoi il y a un perception de commander nécessite de comprendre certaines choses :

• Ce Python utilise jeux de hachage ,

• Comment l'ensemble de hachage de CPython est stocké dans la mémoire et

• Comment les numéros sont hachés

Du haut en bas :

A jeu de hachage est une méthode de stockage de données aléatoires avec des temps de consultation très rapides.

Il a une matrice de sauvegarde :

# A C array; items may be NULL,
# a pointer to an object, or a
# special dummy object
_ _ 4 _ _ 2 _ _ 6

Nous ne tiendrons pas compte de l'objet fictif spécial, qui n'existe que pour faciliter la gestion des suppressions, car nous ne retirerons rien de ces ensembles.

Pour obtenir une recherche vraiment rapide, il faut calculer par magie un hachage à partir d'un objet. La seule règle est que deux objets qui sont égaux ont le même hash. (Mais si deux objets ont le même hachage, ils peuvent être inégaux).

Vous faites ensuite l'index en prenant le modulus par la longueur du tableau :

hash(4) % len(storage) = index 2

L'accès aux éléments est ainsi très rapide.

Les hachages ne représentent qu'une grande partie de l'histoire, car hash(n) % len(storage) y hash(m) % len(storage) peuvent aboutir au même nombre. Dans ce cas, plusieurs stratégies différentes peuvent essayer de résoudre le conflit. CPython utilise le "sondage linéaire" 9 fois avant de faire des choses compliquées, ainsi il aura l'air de à gauche de la fente jusqu'à 9 places avant de chercher ailleurs.

Les ensembles de hachage de CPython sont stockés comme ceci :

• Un ensemble de hachage peut être pas plus de 2/3 plein . S'il y a 20 éléments et que le tableau de sauvegarde fait 30 éléments, le tableau de sauvegarde sera redimensionné pour être plus grand. En effet, les collisions sont plus fréquentes avec les petits backing stores, et les collisions ralentissent tout.

• Le backing store se redimensionne par puissances de 4, en commençant par 8, sauf pour les grands ensembles (50k éléments) qui se redimensionnent par puissances de deux : (8, 32, 128, ...).

Ainsi, lorsque vous créez un tableau, le backing store est de longueur 8. Lorsqu'il est rempli à 5 et que vous ajoutez un élément, il contiendra brièvement 6 éléments. 6 > ²·8 ce qui déclenche un redimensionnement, et le backing store quadruple pour atteindre la taille 32.

Enfin, hash(n) juste des retours n pour les chiffres (sauf -1 ce qui est spécial).

---

Alors, regardons le premier :

v_set = {88,11,1,33,21,3,7,55,37,8}

len(v_set) est 10, donc le magasin de sauvegarde est au moins 15(+1) après que tous les éléments aient été ajoutés . La puissance de 2 pertinente est 32. Donc le magasin de sauvegarde est :

__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __

Nous avons

hash(88) % 32 = 24
hash(11) % 32 = 11
hash(1)  % 32 = 1
hash(33) % 32 = 1
hash(21) % 32 = 21
hash(3)  % 32 = 3
hash(7)  % 32 = 7
hash(55) % 32 = 23
hash(37) % 32 = 5
hash(8)  % 32 = 8

donc ces inserts comme :

__  1 __  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __
   33  Can't also be where 1 is;
        either 1 or 33 has to move

On s'attendrait donc à un ordre comme

{[1 or 33], 3, 37, 7, 8, 11, 21, 55, 88}

avec le 1 ou 33 qui n'est pas au début quelque part ailleurs. On utilisera un sondage linéaire, donc on aura soit :

__  1 33  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __

o

__ 33  1  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __

On pourrait s'attendre à ce que le 33 soit celui qui est déplacé parce que le 1 était déjà là, mais en raison du redimensionnement qui se produit lors de la construction du jeu, ce n'est pas vraiment le cas. Chaque fois que le jeu est reconstruit, les éléments déjà ajoutés sont effectivement réorganisés.

Maintenant vous pouvez voir pourquoi

{7,5,11,1,4,13,55,12,2,3,6,20,9,10}

pourrait être en ordre. Il y a 14 éléments, donc le magasin de sauvegarde est au moins 21+1, ce qui signifie 32 :

__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __

1 à 13 hachages dans les 13 premiers emplacements. 20 va dans l'emplacement 20.

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ __ __ 20 __ __ __ __ __ __ __ __ __ __ __

55 va dans la fente hash(55) % 32 qui est de 23 :

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ __ __ 20 __ __ 55 __ __ __ __ __ __ __ __

Si nous choisissons 50 à la place, nous nous attendons à ce que

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ 50 __ 20 __ __ __ __ __ __ __ __ __ __ __

Et voilà :

{1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 20, 50}
#>>> {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 50, 20}

---

pop est implémenté assez simplement à première vue : il parcourt la liste et ouvre le premier.

---

Il s'agit de détails de mise en œuvre.

Answer 3

"Arbitraire" n'est pas la même chose que "non déterminé".

Ce qu'ils disent, c'est qu'il n'y a pas de propriétés utiles de l'ordre d'itération du dictionnaire qui soient "dans l'interface publique". Il existe très certainement de nombreuses propriétés de l'ordre d'itération qui sont entièrement déterminées par le code qui implémente actuellement l'itération des dictionnaires, mais les auteurs ne vous les promettent pas comme quelque chose que vous pouvez utiliser. Cela leur donne plus de liberté pour modifier ces propriétés entre les versions de Python (ou même simplement dans des conditions d'exploitation différentes, ou complètement au hasard lors de l'exécution) sans craindre que votre programme ne se casse.

Ainsi, si vous écrivez un programme qui dépend de aucune propriété du tout de l'ordre du dictionnaire, vous "rompez le contrat" d'utilisation du type dictionnaire, et les développeurs de Python ne promettent pas que cela fonctionnera toujours, même si cela semble fonctionner pour le moment lorsque vous le testez. C'est en fait l'équivalent de se fier au "comportement indéfini" en C.

Answer 4

Les autres réponses à cette question sont excellentes et bien écrites. Le PO demande "comment", ce que j'interprète comme "comment s'en tirent-ils" ou "pourquoi".

La documentation Python dit dictionnaires ne sont pas ordonnées parce que le dictionnaire Python implémente la fonction type de données abstraites tableau associatif . Comme on dit

l'ordre dans lequel les liaisons sont retournées peut être arbitraire

En d'autres termes, un étudiant en informatique ne peut pas supposer qu'un tableau associatif est ordonné. Il en va de même pour les ensembles en mathématiques

l'ordre dans lequel les éléments d'un ensemble sont énumérés n'est pas pertinent

y informatique

un ensemble est un type de données abstrait qui peut stocker certaines valeurs, sans ordre particulier

L'implémentation d'un dictionnaire en utilisant une table de hachage est une détail de la mise en œuvre qui est intéressant dans la mesure où il possède les mêmes propriétés que les tableaux associatifs en ce qui concerne l'ordre.

Answer 5

Utilisation de Python table de hachage pour stocker les dictionnaires, il n'y a donc pas d'ordre dans les dictionnaires ou autres objets itérables qui utilisent une table de hachage.

Mais en ce qui concerne les indices des éléments dans un objet de hachage, python calcule les indices sur la base du code suivant sur hashtable.c :

key_hash = ht->hash_func(key);
index = key_hash & (ht->num_buckets - 1);

Par conséquent, comme la valeur de hachage des entiers est l'entier lui-même * l'indice est basé sur le nombre ( ht->num_buckets - 1 est une constante), l'indice calculé par Bitwise-et entre (ht->num_buckets - 1) et le nombre lui-même * (sauf pour -1 dont le hash est -2) , et pour les autres objets avec leur valeur de hash.

Considérons l'exemple suivant avec set qui utilisent des tables de hachage :

>>> set([0,1919,2000,3,45,33,333,5])
set([0, 33, 3, 5, 45, 333, 2000, 1919])

Pour le nombre 33 nous avons :

33 & (ht->num_buckets - 1) = 1

En fait, c'est.. :

'0b100001' & '0b111'= '0b1' # 1 the index of 33

Note dans ce cas (ht->num_buckets - 1) est 8-1=7 ou 0b111 .

Et pour 1919 :

'0b11101111111' & '0b111' = '0b111' # 7 the index of 1919

Et pour 333 :

'0b101001101' & '0b111' = '0b101' # 5 the index of 333

Pour plus de détails sur la fonction de hachage de python, il est bon de lire les citations suivantes tirées de code source python :

De grandes subtilités en perspective : La plupart des schémas de hachage dépendent de l'existence d'une "bonne" fonction de hachage. fonction de hachage, dans le sens de la simulation du caractère aléatoire. Ce n'est pas le cas de Python : ses fonctions de hachage les plus importantes (pour les chaînes et les ints) sont très régulières dans les cas cas courants :

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

Ce n'est pas forcément mauvais ! Au contraire, dans un tableau de taille 2**i, prendre les bits de poids faible comme index initial de la table est extrêmement rapide, et il n'y a aucune et il n'y a aucune collision pour les dicts indexées par une plage contiguë d'ints. La même chose est approximativement vraie lorsque les clés sont des chaînes de caractères "consécutives". Ainsi, ceci donne un comportement meilleur qu'aléatoire dans les cas courants, et c'est très souhaitable.

Par contre, lorsque des collisions se produisent, la tendance à remplir des tranches contiguës de la table de hachage rend cruciale une bonne stratégie de résolution des collisions. table de hachage rend cruciale une bonne stratégie de résolution des collisions. Prendre uniquement les i derniers bits du code de hachage est également vulnérable : par exemple, considérons la liste [i << 16 for i in range(20000)] comme un ensemble de clés. Puisque les ints sont leurs propres codes de hachage, et que cela tient dans un dict de taille 2**15, les 15 derniers bits de chaque code de hachage sont tous 0 : ils tous correspondent au même index de table.

Mais répondre aux cas inhabituels ne devrait pas ralentir les cas habituels, donc nous prenons juste les derniers bits de toute façon. C'est à la résolution des collisions de faire le reste. Si nous généralement trouver la clé que l'on cherche du premier coup (et, il se trouve que le facteur de charge de la table est maintenu à moins de 2/3, de sorte que les probabilités les chances sont donc largement en notre faveur), il est alors préférable que le calcul de l'indice initial initial soit très bon marché.

---

_{* La fonction de hachage pour la classe <code>int</code> :}

class int:
    def __hash__(self):
        value = self
        if value == -1:
            value = -2
        return value