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

470

Les dictionnaires sont classés en Python 3.6 (sous l'implémentation de CPython au moins) contrairement aux incarnations précédentes. Cela semble être un changement substantiel, mais ce n'est qu'un court paragraphe dans la documentation . Il est décrit comme un détail d'implémentation CPython plutôt que comme une fonctionnalité de langage, mais implique également que cela pourrait devenir standard à l'avenir.

Comment la nouvelle implémentation du dictionnaire fonctionne-t-elle mieux 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» mise au point par PyPy . L'utilisation de la mémoire du nouveau dict () est inférieure de 20% à 25% par rapport à Python 3.5. PEP 468 (Préserver l'ordre des ** kwargs dans une fonction.) Est implémenté par ceci. L'aspect préservant 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 dict dans la langue pour quelques versions avant de changer la spécification de langue pour rendre obligatoire la sémantique préservant l'ordre pour toutes les implémentations Python actuelles et futures; cela permet également de préserver la compatibilité descendante avec les anciennes versions du langage où l'ordre d'itération aléatoire est toujours en vigueur, par exemple Python 3.5). (Contribué par INADA Naoki enproblème 27350 . Idée initialement suggérée par Raymond Hettinger .)

Mise à jour de décembre 2017: la dictconservation de l'ordre d'insertion est garantie pour Python 3.7

Chris_Rands
la source
2
Voir ce fil sur la liste de diffusion Python-Dev: mail.python.org/pipermail/python-dev/2016-September/146327.html si vous ne l'avez pas vu; il s'agit essentiellement d'une discussion sur ces sujets.
mgc
1
Si les kwargs sont maintenant censés être commandés (ce qui est une bonne idée) et que les kwargs sont dict, pas OrderedDict, alors je suppose que l'on pourrait supposer que les clés dict resteront ordonnées dans la future version de Python, malgré la documentation contraire.
Dmitriy Sintsov
4
@DmitriySintsov Non, ne faites pas cette supposition. Ce problème a été soulevé lors de la rédaction du PEP qui définit la fonction de conservation de l'ordre **kwargset, à ce titre, le libellé utilisé est diplomatique: **kwargsdans une fonction, la signature est désormais garantie d'être un mappage préservant l'ordre d'insertion . Ils ont utilisé le terme mappage afin de ne forcer aucune autre implémentation à ordonner (et à utiliser un dict en OrderedDictinterne) et comme un moyen de signaler que cela n'est pas censé dépendre du fait que le dictn'est pas ordonné.
Dimitris Fasarakis Hilliard
7
Une bonne explication vidéo de Raymond Hettinger
Alex
1
@wazoox, l'ordre et la complexité de la table de hachage n'ont pas changé. Le changement réduit la table de hachage en gaspillant moins d'espace, et l'espace enregistré est (généralement?) Plus que le tableau auxiliaire prend. Plus rapide, plus petit, commandé - vous pouvez choisir les 3.
John La Rooy

Réponses:

513

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

Ils sont ordonnés par insertion [1] . Depuis Python 3.6, pour l'implémentation CPython de Python, les dictionnaires se souviennent de 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 OrderedDictsi vous souhaitez un ordre d'insertion garanti dans d'autres implémentations de Python (et d'autres comportements ordonnés [1] ).

À partir de Python 3.7 , ce n'est plus un détail d'implémentation et devient plutôt une fonctionnalité de langage. À partir d'un message python-dev de GvR :

Faire en sorte. "Dict conserve l'ordre d'insertion" est la décision. Merci!

Cela signifie simplement que vous pouvez en dépendre . D'autres implémentations de Python doivent également offrir un dictionnaire d'insertion ordonné si elles souhaitent être une implémentation conforme de Python 3.7.


Comment l' 3.6implémentation du dictionnaire Python fonctionne-t-elle mieux [2] que l'ancienne tout en préservant l'ordre des éléments?

Essentiellement, en conservant deux tableaux .

  • Le premier tableau,, dk_entriescontient les entrées ( de typePyDictKeyEntry ) pour le dictionnaire dans l'ordre où elles ont été insérées. La préservation de l'ordre est obtenue en étant un tableau d'ajout uniquement où de nouveaux éléments sont toujours insérés à la fin (ordre d'insertion).

  • Le second, dk_indicescontient les indices du dk_entriestableau (c'est-à-dire les valeurs qui indiquent la position de l'entrée correspondante dans dk_entries). Ce tableau fait office de table de hachage. Lorsqu'une clé est hachée, elle conduit à l'un des index stockés dans dk_indiceset l'entrée correspondante est extraite par indexation dk_entries. Étant donné que seuls les index sont conservés, le type de ce tableau dépend de la taille globale du dictionnaire (allant du type int8_t( 1octet) à int32_t/ int64_t( 4/ 8octets) sur les versions 32/ 64bit)

Dans l'implémentation précédente, un tableau clairsemé de type PyDictKeyEntryet de taille dk_sizedevait être alloué; malheureusement, cela a également entraîné beaucoup d'espace vide car ce tableau n'était pas autorisé à être plus que 2/3 * dk_sizeplein pour des raisons de performances . (et l'espace vide avait encore de laPyDictKeyEntry taille!).

Ce n'est pas le cas maintenant car seules les entrées requises sont stockées (celles qui ont été insérées) et un tableau clairsemé de type intX_t( Xselon la taille du dict) 2/3 * dk_sizeest plein. L'espace vide est passé de type PyDictKeyEntryà intX_t.

Donc, évidemment, la création d'un tableau de type PyDictKeyEntryclairsemé demande beaucoup plus de mémoire qu'un tableau clairsemé pour stocker ints.

Vous pouvez voir la conversation complète sur Python-Dev concernant cette fonctionnalité si vous êtes intéressé, c'est une bonne lecture.


Dans la proposition originale faite par Raymond Hettinger , on peut voir une visualisation des structures de données utilisées qui saisit l'essentiel de l'idée.

Par exemple, le dictionnaire:

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

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

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

Au lieu de cela, les données doivent ê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 le voir visuellement maintenant, dans la proposition d'origine, beaucoup d'espace est essentiellement vide pour réduire les collisions et accélérer les recherches. Avec la nouvelle approche, vous réduisez la mémoire requise en déplaçant la rareté là où elle est vraiment nécessaire, dans les index.


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


[2]: Les nouvelles implémentations de dictionnaire fonctionnent mieux en termes de mémoire en étant conçues de manière plus compacte; c'est le principal avantage ici. En termes de vitesse, la différence n'est pas si drastique, il y a des endroits où le nouveau dict peut introduire de légères régressions ( recherches de touches, par exemple ) tandis que dans d'autres (itération et redimensionnement viennent à l'esprit) un boost de performance devrait être présent.

Dans l'ensemble, les performances du dictionnaire, en particulier dans des situations réelles, s'améliorent en raison de la compacité introduite.

Dimitris Fasarakis Hilliard
la source
15
Alors, que se passe-t-il lorsqu'un élément est supprimé? la entriesliste est-elle redimensionnée? ou un espace vide est-il conservé? ou est-il compressé de temps en temps?
njzk2
18
@ njzk2 Lorsqu'un élément est supprimé, l'index correspondant est remplacé par DKIX_DUMMYune valeur de -2et l'entrée dans le entrytableau est remplacée parNULL , lorsque l'insertion est effectuée, les nouvelles valeurs sont ajoutées au tableau des entrées, n'ont pas encore pu discerner, mais à peu près sûr lorsque les indices se remplissent au-delà du 2/3seuil de redimensionnement est effectué. Cela peut entraîner une diminution au lieu de croître si de nombreuses DUMMYentrées existent.
Dimitris Fasarakis Hilliard
3
@Chris_Rands Non, la seule régression réelle que j'ai vue est sur le tracker dans un message de Victor . En dehors de cette référence, je n'ai vu aucun autre problème / message indiquant une différence de vitesse sérieuse dans les charges de travail réelles. Il y a des endroits où le nouveau dict peut introduire de légères régressions (recherches de touches, par exemple) tandis que dans d'autres (itération et redimensionnement viennent à l'esprit) une amélioration des performances serait présente.
Dimitris Fasarakis Hilliard
3
Correction sur la partie de redimensionnement : les dictionnaires ne redimensionnent pas lorsque vous supprimez des éléments, ils recalculent lorsque vous réinsérez. Donc, si un dict est créé avec d = {i:i for i in range(100)}et que vous .popinsérez tous les éléments, la taille ne changera pas. Lorsque vous y ajoutez à nouveau, d[1] = 1la taille appropriée est calculée et le dict redimensionne.
Dimitris Fasarakis Hilliard
6
@Chris_Rands Je suis sûr que ça reste. La chose est, et la raison pour laquelle je l' ai changé ma réponse pour supprimer des déclarations générales sur les « dictétant commandé », dicts ne sont pas ordonnés dans le sens OrderedDictsont s. Le problème notable est l'égalité. dicts ont un ordre insensible ==, OrderedDicts ont un ordre sensible. Le dumping OrderedDictet le changement dictspour avoir maintenant des comparaisons sensibles à l'ordre pourraient entraîner de nombreuses ruptures dans l'ancien code. Je suppose que la seule chose qui pourrait changer à propos de OrderedDicts est sa mise en œuvre.
Dimitris Fasarakis Hilliard
67

Ci-dessous répond à la première question d'origine:

Dois-je utiliser dictou OrderedDicten Python 3.6?

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

L'aspect de maintien de l'ordre de cette nouvelle implémentation est considéré comme un détail d'implémentation et ne doit pas être invoqué

dictn'est pas explicitement censé être une collection ordonnée, donc si vous voulez rester cohérent et ne pas compter sur un effet secondaire de la nouvelle implémentation, vous devez vous en tenir OrderedDict.

Rendez votre code pérenne :)

Il y a un débat là- dessus .

EDIT: Python 3.7 gardera cela comme une fonctionnalité voir

Maresh
la source
1
Il semble que s'ils ne voulaient pas que ce soit une véritable fonctionnalité mais uniquement un détail d'implémentation, ils ne devraient même pas le mettre dans la documentation.
xji
3
Je ne suis pas sûr de votre mise en garde; comme la garantie ne s'applique qu'à Python 3.7, je suppose que les conseils pour Python 3.6 sont inchangés, c'est-à-dire que les dicts sont commandés en CPython mais ne comptent pas dessus
Chris_Rands
25

Mise à jour: Guido van Rossum a annoncé sur la liste de diffusion qu'à partir de Python 3.7, dicttoutes les implémentations Python doivent conserver l'ordre d'insertion.

fjsj
la source
2
Maintenant que la commande des clés est la norme officielle, quel est l'objectif du OrderedDict? Ou est-ce désormais redondant?
Jonny Waffles
2
Je suppose que OrderedDict ne sera pas redondant car il a la move_to_endméthode et son égalité est sensible à l'ordre: docs.python.org/3/library/… . Voir la note sur la réponse de Jim Fasarakis Hilliard.
fjsj
@JonnyWaffles voir la réponse de Jim et ce Q&A stackoverflow.com/questions/50872498/…
Chris_Rands
3
Si vous voulez que votre code fonctionne de la même manière sur 2.7 et 3.6 / 3.7 +, vous devez utiliser OrderedDict
boatcoder le
3
Il est probable qu'il y aura bientôt un "UnorderedDict" pour les gens qui aiment tracasser leurs pronostics pour des raisons de sécurité; p
ZF007
9

Je voulais ajouter à la discussion ci-dessus mais je n'ai pas la réputation de commenter.

Python 3.8 n'est pas encore complètement sorti, mais il inclura même la reversed()fonction sur les dictionnaires (en supprimant une autre différence de OrderedDict.

Dict et dictviews sont désormais itérables dans l'ordre d'insertion inversé à l'aide de reverse (). (Contribué par Rémi Lapeyre dans bpo-33462.) Voir les nouveautés de python 3.8

Je ne vois aucune mention de l'opérateur d'égalité ou d'autres fonctionnalités de OrderedDictdonc ils ne sont toujours pas entièrement identiques.

rkengler
la source