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 dict
conservation de l'ordre d'insertion est garantie pour Python 3.7
la source
**kwargs
et, à ce titre, le libellé utilisé est diplomatique:**kwargs
dans 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 enOrderedDict
interne) et comme un moyen de signaler que cela n'est pas censé dépendre du fait que ledict
n'est pas ordonné.Réponses:
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
OrderedDict
si 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 :
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.
Essentiellement, en conservant deux tableaux .
Le premier tableau,,
dk_entries
contient 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_indices
contient les indices dudk_entries
tableau (c'est-à-dire les valeurs qui indiquent la position de l'entrée correspondante dansdk_entries
). Ce tableau fait office de table de hachage. Lorsqu'une clé est hachée, elle conduit à l'un des index stockés dansdk_indices
et l'entrée correspondante est extraite par indexationdk_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 typeint8_t
(1
octet) àint32_t
/int64_t
(4
/8
octets) sur les versions32
/64
bit)Dans l'implémentation précédente, un tableau clairsemé de type
PyDictKeyEntry
et de tailledk_size
devait être alloué; malheureusement, cela a également entraîné beaucoup d'espace vide car ce tableau n'était pas autorisé à être plus que2/3 * dk_size
plein 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
(X
selon la taille du dict)2/3 * dk_size
est plein. L'espace vide est passé de typePyDictKeyEntry
àintX_t
.Donc, évidemment, la création d'un tableau de type
PyDictKeyEntry
clairsemé demande beaucoup plus de mémoire qu'un tableau clairsemé pour stockerint
s.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.
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'
dict
objet ne fournit pas . OrderedDicts sont réversibles, fournissent des méthodes sensibles à l'ordre et, principalement, fournissent des tests d'égalité sensibles à l'ordre (==
,!=
).dict
s 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.
la source
entries
liste est-elle redimensionnée? ou un espace vide est-il conservé? ou est-il compressé de temps en temps?DKIX_DUMMY
une valeur de-2
et l'entrée dans leentry
tableau 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à du2/3
seuil de redimensionnement est effectué. Cela peut entraîner une diminution au lieu de croître si de nombreusesDUMMY
entrées existent.d = {i:i for i in range(100)}
et que vous.pop
insérez tous les éléments, la taille ne changera pas. Lorsque vous y ajoutez à nouveau,d[1] = 1
la taille appropriée est calculée et le dict redimensionne.dict
étant commandé »,dict
s ne sont pas ordonnés dans le sensOrderedDict
sont s. Le problème notable est l'égalité.dict
s ont un ordre insensible==
,OrderedDict
s ont un ordre sensible. Le dumpingOrderedDict
et le changementdicts
pour 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 deOrderedDict
s est sa mise en œuvre.Ci-dessous répond à la première question d'origine:
Je pense que cette phrase de la documentation est en fait suffisante pour répondre à votre question
dict
n'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 tenirOrderedDict
.Rendez votre code pérenne :)
Il y a un débat là- dessus .
EDIT: Python 3.7 gardera cela comme une fonctionnalité voir
la source
Mise à jour: Guido van Rossum a annoncé sur la liste de diffusion qu'à partir de Python 3.7,
dict
toutes les implémentations Python doivent conserver l'ordre d'insertion.la source
move_to_end
méthode et son égalité est sensible à l'ordre: docs.python.org/3/library/… . Voir la note sur la réponse de Jim Fasarakis Hilliard.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 deOrderedDict
.Je ne vois aucune mention de l'opérateur d'égalité ou d'autres fonctionnalités de
OrderedDict
donc ils ne sont toujours pas entièrement identiques.la source