Les dictionnaires sont-ils ordonnés dans Python 3.6+ ?

Question

Les dictionnaires sont ordonnés dans Python 3.6 (du moins dans l'implémentation CPython) contrairement aux incarnations précédentes. Cela semble être un changement substantiel, mais il ne s'agit que d'un court paragraphe dans le document documentation . Il est décrit comme un détail d'implémentation de CPython plutôt que comme une fonctionnalité du langage, mais il implique également que cela pourrait devenir un standard à l'avenir.

En quoi la nouvelle implémentation du dictionnaire est-elle plus performante que l'ancienne tout en préservant l'ordre des éléments ?

Voici le texte de la documentation :

dict() utilise désormais une représentation "compacte". dont PyPy est le pionnier . L'utilisation de la mémoire du nouveau dict() est de 20 à 25 % inférieure à celle de Python 3.5. PEP 468 (Préserver l'ordre des **kwargs dans une fonction.) est implémenté par ceci. L'aspect de préservation de l'ordre de cette nouvelle implémentation est considéré comme un détail d'implémentation et ne doit pas être invoqué (cela peut changer à l'avenir, mais il est souhaitable d'avoir cette nouvelle implémentation de dict dans le langage pour quelques versions avant de changer la spécification du langage pour rendre obligatoire la sémantique de préservation de l'ordre pour toutes les implémentations actuelles et futures de Python ; cela permet également de préserver la compatibilité ascendante avec les anciennes versions du langage où l'ordre d'itération aléatoire est toujours en vigueur, par exemple Python 3.5). (Proposé par INADA Naoki dans numéro 27350 . Idée initialement suggéré par Raymond Hettinger .)

Mise à jour de décembre 2017 : dict L'ordre d'insertion de la retenue est garanti pour Python 3.7

Answer 1

Les dictionnaires sont-ils ordonnés dans Python 3.6+ ?

Ils sont insertion commandée [1] . À partir de Python 3.6, pour l'implémentation CPython de Python, les dictionnaires mémoriser l'ordre des éléments insérés . Ceci est considéré comme un détail d'implémentation dans Python 3.6. ; vous devez utiliser OrderedDict si vous voulez un ordre d'insertion, c'est garanti à travers d'autres implémentations de Python (et d'autres comportements ordonnés [1] ).

À partir de Python 3.7 Dans le cas d'un système de gestion de l'information, il ne s'agit plus d'un détail de mise en œuvre, mais d'une caractéristique du langage. Extrait d'un message de GvR sur python-dev :

Faites-le. "Dict conserve l'ordre d'insertion" est la règle. Merci !

Cela signifie simplement que vous pouvez compter sur elle . Les autres implémentations de Python doivent également proposer un dictionnaire à insertion ordonnée si elles souhaitent être une implémentation conforme de Python 3.7.

---

Comment le programme Python 3.6 La mise en œuvre du dictionnaire donne de meilleurs résultats [2] que l'ancien tout en préservant l'ordre des éléments ?

Essentiellement, en garder deux tableaux .

• Le premier tableau, dk_entries contient les entrées ( de type PyDictKeyEntry ) pour le dictionnaire dans l'ordre où ils ont été insérés. La préservation de l'ordre est assurée par le fait qu'il s'agit d'un tableau à ajouter uniquement où les nouveaux éléments sont toujours insérés à la fin (ordre d'insertion).

• La seconde, dk_indices contient les indices pour les dk_entries (c'est-à-dire des valeurs qui indiquent la position de l'entrée correspondante dans le tableau des dk_entries ). Ce tableau fait office de table de hachage. Lorsqu'une clé est hachée, elle conduit à l'un des indices stockés dans dk_indices et l'entrée correspondante est récupérée en indexant dk_entries . Puisque seuls les indices sont conservés, le type de ce tableau dépend de la taille globale du dictionnaire (allant du type int8_t ( 1 octet) à int32_t / int64_t ( 4 / 8 octets) sur 32 / 64 les constructions de bits)

Dans l'implémentation précédente, un tableau clairsemé de type PyDictKeyEntry et la taille dk_size a dû être allouée ; malheureusement, cela a également donné lieu à beaucoup d'espace vide puisque ce tableau ne devait pas dépasser 2/3 * dk_size complet pour des raisons de performance . (et l'espace vide toujours avait PyDictKeyEntry taille !).

Ce n'est pas le cas aujourd'hui puisque seule la requis sont stockées (celles qui ont été insérées) et un tableau clairsemé de type intX_t ( X selon la taille des dictées) 2/3 * dk_size s plein est conservé. L'espace vide est passé du type PyDictKeyEntry a intX_t .

Donc, évidemment, la création d'un tableau clairsemé de type PyDictKeyEntry est beaucoup plus gourmand en mémoire qu'un tableau clairsemé pour stocker int s.

Vous pouvez voir l'intégralité de la conversation sur Python-Dev concernant cette fonctionnalité si cela vous intéresse, c'est une bonne lecture.

---

Dans la proposition originale faite par Raymond Hettinger Dans le cadre de l'étude de l'OCDE, on peut voir une visualisation des structures de données utilisées, ce qui permet de saisir l'essentiel de l'idée.

Par exemple, le dictionnaire :

d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'}

est actuellement stocké sous la forme [keyhash, key, value] :

entries = [['--', '--', '--'],
           [-8522787127447073495, 'barry', 'green'],
           ['--', '--', '--'],
           ['--', '--', '--'],
           ['--', '--', '--'],
           [-9092791511155847987, 'timmy', 'red'],
           ['--', '--', '--'],
           [-6480567542315338377, 'guido', 'blue']]

Au lieu de cela, les données devraient être organisées comme suit :

indices =  [None, 1, None, None, None, 0, None, 2]
entries =  [[-9092791511155847987, 'timmy', 'red'],
            [-8522787127447073495, 'barry', 'green'],
            [-6480567542315338377, 'guido', 'blue']]

Comme vous pouvez maintenant le constater visuellement, dans la proposition originale, une grande partie de l'espace est essentiellement vide pour réduire les collisions et rendre les recherches plus rapides. Avec la nouvelle approche, vous réduisez la mémoire requise en déplaçant l'espacement là où il est vraiment nécessaire, dans les indices.

---

_{[1] : Je dis "insertion ordonnée" et non "ordonnée" car, avec l'existence d'OrderedDict, "ordonné" suggère un comportement supplémentaire que l'objet dict ne fournit pas. Les OrderedDicts sont réversibles, fournissent des méthodes sensibles à l'ordre et, principalement, fournissent un test d'égalité sensible à l'ordre (==, !=). Les dicts n'offrent actuellement aucun de ces comportements/méthodes.}

_{[2] : Les nouvelles implémentations de dictionnaires sont plus performantes en termes de mémoire car elles sont conçues de manière plus compacte ; c'est le principal avantage ici. En ce qui concerne la vitesse, la différence n'est pas si radicale, il y a des endroits où le nouveau dictionnaire pourrait introduire de légères régressions ([recherche de clés, par exemple][10]) alors que dans d'autres (l'itération et le redimensionnement viennent à l'esprit) une augmentation des performances devrait être présente. Dans l'ensemble, les performances du dictionnaire, notamment en situation réelle, s'améliorent grâce à la compacité introduite.}

Answer 2

Vous trouverez ci-dessous la réponse à la première question originale :

Dois-je utiliser dict o OrderedDict dans Python 3.6 ?

Je pense que cette phrase de la documentation est suffisante pour répondre à votre question

L'aspect de préservation de l'ordre de cette nouvelle mise en œuvre est considéré comme un détail de mise en œuvre et ne doit pas être pris en compte.

dict n'est pas explicitement destiné à être une collection ordonnée, donc si vous voulez rester cohérent et ne pas dépendre d'un effet secondaire de la nouvelle implémentation, vous devriez vous en tenir à OrderedDict .

Faites en sorte que votre code soit à l'épreuve du temps :)

Il y a un débat à ce sujet aquí .

EDIT : Python 3.7 conservera cette fonctionnalité. voir

Answer 3

Mise à jour : Guido van Rossum annoncé sur la liste de diffusion qu'à partir de Python 3.7 dict dans toutes les implémentations de Python doivent préserver l'ordre d'insertion.

Answer 4

Je voulais ajouter quelque chose à la discussion ci-dessus, mais je n'ai pas la réputation nécessaire pour commenter.

Python 3.8 inclut le reversed() sur les dictionnaires (ce qui supprime une autre différence avec OrderedDict .

Dict et dictviews sont maintenant itérables dans l'ordre d'insertion inversé en utilisant reversed(). (Contribution de Rémi Lapeyre dans bpo-33462). Voir les nouveautés de python 3.8

Je ne vois pas de mention de l'opérateur d'égalité ou d'autres caractéristiques de la fonction OrderedDict donc ils ne sont pas encore tout à fait les mêmes.

Answer 5

Pour répondre pleinement à cette question en 2020, permettez-moi de citer plusieurs déclarations de Documents officiels de Python :

Modifié dans la version 3.7 : L'ordre du dictionnaire est garanti comme étant l'ordre d'insertion. Ce comportement était un détail d'implémentation de CPython depuis la version 3.6.

Modifié dans la version 3.7 : L'ordre du dictionnaire est garanti comme étant l'ordre d'insertion.

Modifié dans la version 3.8 : Les dictionnaires sont maintenant réversibles.

Les dictionnaires et les vues de dictionnaires sont réversibles.

A déclaration concernant OrderedDict vs Dict :

Les dictionnaires ordonnés sont identiques aux dictionnaires ordinaires, mais ils possèdent des capacités supplémentaires liées aux opérations d'ordonnancement. Ils sont devenus moins importants depuis que la classe intégrée dict a acquis la capacité de se souvenir de l'ordre d'insertion (ce nouveau comportement est devenu garanti dans Python 3.7).