J'ai été surpris de découvrir récemment que même si les dict sont garantis pour préserver l'ordre d'insertion dans Python 3.7+, les ensembles ne sont pas:
>>> d = {'a': 1, 'b': 2, 'c': 3}
>>> d
{'a': 1, 'b': 2, 'c': 3}
>>> d['d'] = 4
>>> d
{'a': 1, 'b': 2, 'c': 3, 'd': 4}>>> s = {'a', 'b', 'c'}
>>> s
{'b', 'a', 'c'}
>>> s.add('d')
>>> s
{'d', 'b', 'a', 'c'}Quelle est la justification de cette différence? Les mêmes améliorations d'efficacité qui ont conduit l'équipe Python à changer l'implémentation de dict ne s'appliquent-elles pas également aux ensembles?
Je ne suis pas à la recherche de pointeurs vers des implémentations d'ensembles ordonnés ou de façons d'utiliser des dict comme remplaçants pour des ensembles. Je me demande simplement pourquoi l'équipe Python n'a pas fait en sorte que les ensembles intégrés préservent l'ordre en même temps qu'ils le faisaient pour les dict.
dictetsetdepuis 2.7.Réponses:
Les ensembles et les dict sont optimisés pour différents cas d'utilisation. L'utilisation principale d'un ensemble est le test d'appartenance rapide, qui est indépendant de l'ordre.Pour les dictés, le coût de la recherche est l'opération la plus critique et la clé est plus susceptible d'être présente. Avec les ensembles, la présence ou l'absence d'un élément n'est pas connue à l'avance et l'implémentation de l'ensemble doit donc être optimisée pour le cas trouvé et non trouvé. En outre, certaines optimisations pour les opérations d'ensemble courantes telles que l'union et l'intersection rendent difficile la conservation de l'ordre des ensembles sans dégrader les performances.
Bien que les deux structures de données soient basées sur le hachage, il est faux de penser que les ensembles sont simplement implémentés comme des dict avec des valeurs nulles. Même avant l'implémentation compacte de dict dans CPython 3.6, les implémentations set et dict différaient déjà considérablement, avec peu de réutilisation de code. Par exemple, les dict utilisent le sondage aléatoire, mais les ensembles utilisent une combinaison de sondage linéaire et d'adressage ouvert, pour améliorer la localisation du cache. La sonde linéaire initiale ( 9 étapes par défaut dans CPython) vérifiera une série de paires clé / hachage adjacentes, améliorant les performances en réduisant le coût de la gestion des collisions de hachage - l'accès mémoire consécutif est moins cher que les sondes dispersées.
dictobject.c- maître , v3.5.9setobject.c- maître , v3.5.9Il serait possible en théorie de changer l'implémentation d'ensemble de CPython pour qu'elle soit similaire à la dictée compacte, mais dans la pratique, il y a des inconvénients, et des développeurs principaux notables étaient opposés à faire un tel changement.
- Guido van Rossum
- Raymond Hettinger
Une discussion détaillée sur l'opportunité de compacter les ensembles pour 3.7, et des réponses sur les raisons pour lesquelles il a été décidé de ne pas le faire, peuvent être trouvées dans les listes de diffusion python-dev.
En résumé, les points principaux sont que les modèles d'utilisation sont différents (les ordres de commande d'insertion tels que ** kwargs sont utiles , moins pour les ensembles), les économies d'espace pour les ensembles de compactage sont moins importantes (car il n'y a que des clés et un tableau de hachage pour densifier, par opposition aux clés, hachages et valeurs), et l'optimisation de sondage linéaire susmentionnée dans les ensembles est incompatible avec une implémentation compacte.
Je reproduis ci-dessous le billet de Raymond qui couvre les points les plus importants.
De [Python-Dev] Python 3.6 dict devient compact et obtient une version privée; et les mots clés sont commandés , septembre 2016.
la source
Discussions
Votre question est pertinente et a déjà été longuement discutée sur les développeurs python il n'y a pas longtemps. R. Hettinger a partagé une liste de justifications dans ce fil . L'état de la question semble illimité maintenant, peu de temps après cette réponse détaillée de T. Peters.
En bref, la mise en œuvre de dict modernes qui préserve l'ordre d'insertion est unique et n'est pas considérée comme appropriée avec les ensembles. En particulier, les dict sont utilisés partout pour exécuter Python (par exemple
__dict__dans les espaces de noms des objets). Une motivation majeure derrière le dict moderne était de réduire la taille, ce qui rend Python plus efficace en mémoire dans son ensemble. En revanche, les ensembles sont moins répandus que les dits dans le noyau de Python et dissuadent ainsi une telle refactorisation. Voir aussi le discours de R. Hettinger sur la mise en œuvre du dict moderne.Points de vue
La nature non ordonnée des ensembles en Python est parallèle au comportement des ensembles mathématiques . L'ordre n'est pas garanti.
Si un ordre quelconque était introduit dans les ensembles en Python, ce comportement respecterait une structure mathématique complètement distincte, à savoir un ensemble ordonné (ou Oset). Les osets jouent un rôle distinct en mathématiques, en particulier en combinatoire. Une application pratique des Osets est observée dans le changement de cloches .
Le fait d'avoir des ensembles non ordonnés est compatible avec une structure de données très générique et omniprésente qui détache la plupart des mathématiques modernes, c'est-à-dire la théorie des ensembles . Je soumets, les ensembles non ordonnés en Python sont bons à avoir.
Voir également les articles connexes qui développent ce sujet:
la source