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

Je ne comprends pas comment la boucle sur un dictionnaire ou un ensemble en python est effectuée par ordre `` arbitraire ''.

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

Qu'est-ce que je rate?

Remarque: Cette réponse a été écrite avant le dictchangement d'implémentation du type, en Python 3.6. La plupart des détails d'implémentation de cette réponse s'appliquent toujours, mais l'ordre de liste des clés dans les dictionnaires n'est plus déterminé par les valeurs de hachage. L'implémentation définie 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 Python spécifique. Pour le reste de cette réponse, pour «dictionnaire», vous pouvez également lire «set»; les ensembles sont implémentés sous forme de dictionnaires avec juste des clés et aucune valeur.

Les clés sont hachées et les valeurs de hachage sont attribuées aux emplacements dans une table dynamique (elle peut augmenter ou diminuer en fonction des besoins). Et ce processus de mappage peut entraîner des collisions, ce qui signifie qu'une clé devra être insérée dans un emplacement suivant en fonction de ce qui existe déjà.

La liste du contenu boucle sur les emplacements, et les clés sont donc répertoriées dans l'ordre dans lequel elles résident actuellement dans le tableau.

Prenons les clés 'foo'et 'bar', par exemple, et supposons que la taille de la table est de 8 emplacements. Dans Python 2.7, hash('foo')est -4177197833195190597, hash('bar')est 327024216814240868. Modulo 8, cela signifie que ces deux clés sont insérées dans les slots 3 et 4 puis:

>>> 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 boucle sur le tableau répertorie d'abord l'emplacement 3, puis l'emplacement 4, il 'foo'est donc répertorié avant 'bar'.

baret baz, cependant, ont des valeurs de hachage qui sont exactement 8 la carte à part et donc à la même emplacement exact, 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é inséré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 des tables diffère ici, car l'une ou l'autre clé 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 une table de hachage , qui utilise l'adressage ouvert. Si vous êtes curieux et que vous comprenez suffisamment bien C, jetez un œil à l' implémentation C pour tous les détails (bien documentés). Vous pouvez également regarder cette présentation Pycon 2010 de Brandon Rhodes sur le fonctionnement de CPython dict, ou prendre une copie de Beautiful 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 pour empêcher certains types de déni de service (où un attaquant rend un serveur Python insensible en provoquant des collisions de hachage de masse). Cela signifie que l'ordre d'un dictionnaire ou d'un ensemble donné dépend également de la graine de hachage aléatoire pour l'appel Python actuel.

D'autres implémentations sont libres d'utiliser une structure différente pour les dictionnaires, à condition qu'ils satisfassent l'interface Python documentée pour eux, mais je crois que toutes les implémentations jusqu'à présent utilisent une variante de la table de hachage.

CPython 3.6 introduit une nouvelle dict implémentation qui maintient l'ordre d'insertion, et est plus rapide et plus efficace en mémoire pour démarrer. Plutôt que de conserver une grande table éparse où chaque ligne fait référence à la valeur de hachage stockée et aux objets clé et valeur, la nouvelle implémentation ajoute un tableau de hachage plus petit qui ne fait référence qu'aux index dans une table `` dense '' séparée (une qui ne contient que le plus de lignes car il existe des paires clé-valeur réelles), et c'est la table dense qui répertorie les éléments contenus dans l'ordre. Voir la proposition à Python-Dev pour plus de détails . Notez que dans Python 3.6, cela est considéré comme un détail d'implémentation, Python-the-language ne spécifie pas que les autres implémentations doivent conserver l'ordre. Cela a changé dans Python 3.7, où ce détail a été élevé au rang de spécification de langage ; pour que toute implémentation soit correctement compatible avec Python 3.7 ou plus récent, elle doit copier 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 OrderedDictclasse , une sous-classe de dictqui ajoute une structure de données supplémentaire pour enregistrer l'ordre des clés. Au prix d'un peu de vitesse et de mémoire supplémentaire, cette classe se souvient dans quel ordre vous avez inséré les clés; lister les clés, les valeurs ou les éléments le fera ensuite dans cet ordre. Il utilise une liste à double lien stockée dans un dictionnaire supplémentaire pour maintenir la commande à jour efficacement. Voir l' article de Raymond Hettinger décrivant l'idée . OrderedDictles objets présentent d'autres avantages, comme le fait d'être réorganisables .

Si vous vouliez un ensemble ordonné, vous pouvez installer le osetpackage ; cela fonctionne sur Python 2.5 et plus.

C'est plus une réponse à Python 3.41 Un ensemble avant qu'il ne soit fermé en tant que doublon.

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

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

list(myset) == list(myset)

Autrement dit, l'ordre est stable .

Comprendre pourquoi il y a un ordre perçu nécessite de comprendre certaines choses:

• Que Python utilise des ensembles de hachage ,

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

• Comment les nombres sont hachés

Du haut:

Un ensemble de hachage est une méthode de stockage de données aléatoires avec des temps de recherche très rapides.

Il a un réseau de support:

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

Nous ignorerons l'objet factice spécial, qui n'existe que pour faciliter la gestion des suppressions, car nous ne supprimerons pas de ces ensembles.

Afin d'avoir une recherche très rapide, vous faites de la magie pour calculer un hachage à partir d'un objet. La seule règle est que deux objets égaux ont le même hachage. (Mais si deux objets ont le même hachage, ils peuvent être inégaux.)

Vous faites ensuite en index en prenant le module par la longueur du tableau:

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

Cela rend l'accès aux éléments très rapide.

Les hachages ne sont que l'essentiel de l'histoire, car hash(n) % len(storage)et hash(m) % len(storage)peuvent aboutir au même nombre. Dans ce cas, plusieurs stratégies différentes peuvent tenter de résoudre le conflit. CPython utilise le «sondage linéaire» 9 fois avant de faire des choses compliquées, il regardera donc à gauche de l'emplacement jusqu'à 9 endroits avant de chercher ailleurs.

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

• Un ensemble de hachage ne peut pas être rempli à plus des 2/3 . S'il y a 20 éléments et que le tableau de sauvegarde a une longueur de 30 éléments, le magasin de sauvegarde sera redimensionné pour être plus grand. En effet, vous obtenez plus souvent des collisions avec de petits magasins de support, et les collisions ralentissent tout.

• Le magasin de support se redimensionne par puissances de 4, à partir de 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 magasin de stockage a une longueur de 8. Lorsqu'il est plein à 5 et que vous ajoutez un élément, il contiendra brièvement 6 éléments. 6 > ²⁄₃·8Cela déclenche donc un redimensionnement et le magasin de support quadruple à la taille 32.

Enfin, hash(n)retourne juste npour les nombres (sauf -1ce qui est spécial).

Alors, regardons le premier:

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

len(v_set)est égal à 10, donc le magasin auxiliaire est au moins 15 (+1) après que tous les éléments ont été ajoutés . La puissance pertinente de 2 est 32. Ainsi, le magasin de support 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 ceux-ci insèrent 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

Nous nous attendrions donc à une commande comme

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

avec le 1 ou 33 qui n'est pas au départ ailleurs. Cela utilisera un sondage linéaire, donc nous aurons soit:

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

ou

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

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

Maintenant tu peux 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 support est au moins 21 + 1, ce qui signifie 32:

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

1 à 13 hachage 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) % 32qui est 23:

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

Si nous choisissions 50 à la place, nous nous attendrions à

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

Et voici:

{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é tout simplement par l'apparence des choses: il parcourt la liste et fait apparaître le premier.

Ce sont tous les détails de mise en œuvre.

«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 sont "dans l'interface publique". Il y a presque 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 du dictionnaire, 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 différentes conditions de fonctionnement, ou complètement au hasard au moment de l'exécution) sans craindre que votre programme ne s'arrête.

Ainsi, si vous écrivez un programme qui dépend de n'importe quelle propriété de l'ordre du dictionnaire, alors vous "rompez le contrat" ​​d'utilisation du type de dictionnaire, et les développeurs Python ne promettent pas que cela fonctionnera toujours, même si cela semble fonctionner pour l'instant quand vous le testez. C'est fondamentalement l'équivalent de s'appuyer sur un "comportement indéfini" en C.

Les autres réponses à cette question sont excellentes et bien rédigées. Le PO demande «comment» ce que j'interprète comme «comment s'en sortent-ils» ou «pourquoi».

La documentation Python indique que les dictionnaires ne sont pas classés car le dictionnaire Python implémente le tableau associatif de type de données abstrait . Comme ils disent

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

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

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

et informatique

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

L'implémentation d'un dictionnaire à l'aide d'une table de hachage est un détail d'implémentation qui est intéressant en ce qu'il a les mêmes propriétés que les tableaux associatifs en ce qui concerne l'ordre.

Python utilise une 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 d'éléments dans un objet de hachage, python calcule les indices en fonction du code suivant danshashtable.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'index est basé sur le nombre ( ht->num_buckets - 1est une constante) donc l'indice calculé par Bitwise-and between (ht->num_buckets - 1)et le nombre lui-même ^* (attendez-vous à -1 pour lequel il est haché est -2 ) et pour les autres objets avec leur valeur de hachage.

considérez l'exemple suivant avec setcette table de hachage:

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

Pour le nombre, 33nous avons:

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

C'est en fait:

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

Notez dans ce cas (ht->num_buckets - 1)est 8-1=7ou 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 python, il est bon de lire les citations suivantes du code source python :

Principales subtilités à venir: La plupart des schémas de hachage dépendent de la présence d'une «bonne» fonction de hachage, dans le sens de la simulation du caractère aléatoire. Python ne le fait pas: ses fonctions de hachage les plus importantes (pour les chaînes et les entiers) sont très régulières dans les 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 une table de taille 2 ** i, prendre les bits de poids faible i comme index de table initial est extrêmement rapide, et il n'y a pas du tout de collisions pour les dicts indexés par une plage contiguë d'entiers. La même chose est approximativement vraie lorsque les clés sont des chaînes "consécutives". Donc, cela donne un comportement meilleur que aléatoire dans les cas courants, et c'est très souhaitable.

OTOH, 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 de collision. Prendre uniquement les i derniers bits du code de hachage est également vulnérable: par exemple, considérez 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 sont tous mappés au même index de table.

Mais traiter des cas inhabituels ne devrait pas ralentir les cas habituels, nous prenons donc les derniers i bits de toute façon. C'est à la résolution des collisions de faire le reste. Si nous trouvons généralement la clé que nous recherchons du premier coup (et, il s'avère que nous le faisons généralement - le facteur de charge de la table est maintenu sous 2/3, donc les chances sont solidement en notre faveur), alors il Il est plus judicieux de garder le calcul initial de l'indice bon marché.

_{* La fonction de hachage pour la classe int:}

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

À partir de Python 3.7 (et déjà dans CPython 3.6 ), les éléments du dictionnaire restent dans l'ordre dans lequel ils ont été insérés .