Pourquoi les ensembles et dictionnaires Python ne sont-ils pas classés par défaut?

Le fait nest pas que la surcharge est particulièrement importante, plus quelle est là pas du tout .

Les fonctionnalités linguistiques doivent toujours trouver un équilibre entre la rentabilité. Les dictionnaires sont absolument fondamentaux pour la programmation Python, il serait donc très mauvais pour eux d’être encore un peu plus lents qu’ils ne devraient l’être juste pour préserver l’ordre d’insertion, alors que la plupart du temps vous n’avez pas besoin d’être ordonné. ignorer lordre dinsertion en échange dun accès un peu plus rapide, et laisser la structure de données préservant lordre pour les classes spéciales. Sil y avait une autre structure de données qui pouvait faire tout ce quun dict peut, et que dict était une ride moins utilisée du langage, les choses peut paraître différent.

Commentaires

• Mon contre-argument à cela serait: utiliser un type de données dict non ordonné plus efficace pour les dictionnaires internes (comme ici ‘ s deque pour optimiser les performances dans certains autres contextes) mais laissez le type de données dict principal de lutilisateur conserver lordre.
• Aussi, ai-je raison de comprendre que limplémentation CPython de la version 3.6 préserve en fait lordre dinsertion pour dicts?

Vous avez raison de dire que les articles sont stockés en interne avec une certaine commande, mais cette commande interne est déterminé par le code de hachage de la clé, ce qui permet une récupération aussi rapide. Donc, si un ensemble / dict doit être ordonné, il devra maintenir une structure de données interne séparée (par exemple une liste ordonnée de clés) pour cela.

Cela augmenterait bien sûr la taille. Mais peut-être pire, cela affectera les performances. Par exemple, la suppression dun élément dun ensemble est une opération O (1), mais si elle doit également supprimer la clé dune liste ordonnée interne, elle deviendrait O (n). Un tel coût serait désastreux pour certaines applications. Étant donné quil est assez rare que vous ayez besoin dun ensemble ordonné, un tel compromis nen vaut pas la peine pour les types set / dict standard.

Votre prémisse est incorrecte. Depuis Python 3.6, les dict se souviennent de leur ordre dinsertion . Il sagissait dun détail de mise en œuvre et a été promu à la fonctionnalité de langage complet dans la version 3.7. En 3.6, pour le cas spécifique de **kwargs, la préservation de lordre est spécifiquement garantie.

Commentaires

• Oui, je nen étais ‘ pas au courant lorsque jai posé la question, car ‘ nest pas encore une fonctionnalité de langage, juste une implémentation détail dans une mise en œuvre. Mais il semble quau moins les dictionnaires deviendront ordonnés à long terme et, espérons-le, également définis.
• @oulenz ‘ nest plus un détail dimplémentation, il ‘ requis à partir de Python 3.7

Un ordonné set nest possible que lorsque les éléments à stocker ont un ordre (cest-à-dire une méthode de comparaison) en premier lieu – mais ce nest pas toujours une donnée.

Limplémentation par défaut de set / map dans la plupart des environnements de nos jours est basé sur une table de hachage à redimensionnement automatique, qui présente les avantages suivants:

• plus rapide
• utilise moins de mémoire
• ne nécessite pas les éléments pour fournir un ordre

Les ensembles doivent quand même être stockés en interne avec un certain ordre

Mais cet ordre interne na pas nécessairement de sens et ne reste pas le même. En effet, une propriété des hashtables qui confond parfois les développeurs inexpérimentés est que lordre ditération, qui est basé sur lordre interne, peut changer complètement lorsque des éléments sont ajoutés (cest-à-dire lorsquun redimensionnement est déclenché) ou entre différents sexécute.

Commentaires

• Je ne ‘ pas compris votre première remarque. Nous n ‘ n avons pas besoin de méthode de comparaison, le classement pourrait simplement être hérité, par exemple à partir dune liste ou dune chaîne littérale {3, 5, 4}.
• @oulenz: si vous ‘ ne vous souciez pas de la commande sans signification et variant avec le temps, alors chaque ensemble est ordonné, car il y aura une sorte dordre ditération. Mais  » ensemble ordonné  » implique que lordre est sémantique pour les éléments, ce qui nest pas toujours possible. ‘ Je ne comprends pas vraiment pourquoi vous voulez que tous les ensembles soient commandés.
•  » Ensemble ordonné  » nimplique pas que lordre est sémantique, mais quil y a un ordre. Bien sûr, je me soucie quune fois cet ordre établi, il soit conservé, à moins que son contenu ne soit modifié.
• Désolé, je nétais ‘ pas conscient de lexistence dune implication pour certaines personnes. Javais simplement à lesprit un ensemble ordonné linéairement à partir des mathématiques. en.wikipedia.org/wiki/Total_order
• @jameslarge la relation de commande ne ‘ t doit être inconnu de moi. Si je dérive un ensemble ordonné dune liste, je sais exactement quel est son ordre. Si je veux assurer un certain ordre, je peux trier lensemble. Mais si vous navez ‘ pas besoin de la commande, vous pouvez simplement lignorer.

Lidée générale derrière un ensemble ou un dictionnaire est que vous prévoyez deffectuer de nombreuses opérations de recherche. Il est optimisé pour lesdites opérations de recherche en utilisant un hachage qui permet la recherche O (1) dans la plupart des cas.

Lordre se fait à laide de tableaux ou de listes liées et en fait, en effectuant des opérations où lordre est important, ils sont optimisés pour cela comme lajout dune valeur à la fin ou au début.

De par la nature de ces deux structures de données, aucune nest optimisée pour les deux. Cela ne veut pas dire que ce nest pas possible, mais cela implique à la fois les structures de données si vous voulez à la fois loptimisation des opérations de recherche et de commande.

Vous avez donc ce compromis entre:

loptimisation des opérations de recherche < => les opérations basées sur les commandes < => utilisation de la mémoire

Le consensus général est quen tant que programmeur, vous voulez généralement optimiser pour lun ou lautre mais pas les deux, et certainement personne ne préconise de doubler votre utilisation de la mémoire lorsque vous avez seulement besoin pour optimiser lun des deux.

Cela dit, il existe des implémentations avec les deux, ou du moins en Java, en particulier LinkedHashMap est à la fois un tableau et un hachage- dictionnaire basé. Parfois, vous aurez besoin des deux, mais il est conseillé dutiliser ArrayList si vous navez besoin que dune liste et un HashMap si vous navez besoin que dun dictionnaire .

Commentaires

• Hein? Un Java LinkedHashMap nest pas  » à la fois un tableau et un dictionnaire basé sur le hachage « . Il ‘ est essentiellement un HashMap (cest-à-dire utilise un tableau en interne) superposé à une liste liée pour permettre litération dans lordre dinsertion.
• Les structures de données linéaires ne sont pas ‘ t les seules structures de données ordonnées; Les arbres binaires peuvent également être ordonnés (tels que les arbres rouge-noir et AVL). Une autre opération qui peut être impliquée dans le compromis est linsertion (les tableaux sont assez efficaces en termes de recherche, ditération et dutilisation de la mémoire, mais les plus lents en matière dinsertion).