Existe-t-il une décision de conception Python (PEP) qui empêche l'ajout d'un conteneur trié dans Python ?
( OrderedDict n'est pas un conteneur trié puisqu'il est ordonné par ordre d'insertion).
Réponses
Trop de publicités?
GrantJ
Points
888
Il y a aussi un python conteneurs triés qui implémente les types liste triée, dict, et set. Il est très similaire à blist mais implémenté en pure-Python et dans la plupart des cas plus rapide .
>>> from sortedcontainers import SortedSet
>>> ss = SortedSet([3, 7, 2, 2])
>>> ss
SortedSet([2, 3, 7])Il possède également des fonctionnalités peu communes à d'autres paquets :
>>> from sortedcontainers import SortedDict
>>> sd = SortedDict((num, num) for num in range(100000))
>>> sd.iloc[-5] # Lookup the fifth-to-last key.
99995Avis de non-responsabilité : Je suis l'auteur du module sortedcontainers.
Il s'agit d'une décision de conception consciente de la part de Guido (il était même quelque peu réticent quant à l'ajout du collections ). Son objectif est de préserver "une façon évidente de faire" lorsqu'il s'agit de sélectionner des types de données pour les applications.
Le concept de base est le suivant : si un utilisateur est suffisamment sophistiqué pour se rendre compte que les types intégrés ne sont pas la bonne solution à son problème, il est également capable de trouver une bibliothèque tierce appropriée.
Étant donné que list+sorting, list+heapq et list+bisect couvrent un grand nombre de cas d'utilisation qui, autrement, s'appuieraient sur des structures de données triées de manière inhérente, et que des paquets comme blist existent, il n'y a pas une grande envie d'ajouter plus de complexité dans cet espace à la bibliothèque standard.
D'une certaine manière, cela ressemble au fait qu'il n'y a pas de tableau multidimensionnel dans la bibliothèque standard, cette tâche étant confiée aux gens de NumPy.
Adrian
Points
419
Il y a aussi le poil à gratter qui contient un ensemble trié type de données :
sortedset(iterable=(), key=None)
>>> from blist import sortedset
>>> my_set = sortedset([3,7,2,2])
sortedset([2, 3, 7]
abbot
Points
8093
Hay un heapq dans la bibliothèque standard, il n'est pas exactement trié, mais en quelque sorte. Il existe également un poil à gratter mais il ne fait pas partie de la bibliothèque standard.
- Réponses précédentes
- Plus de réponses
1 votes
Comme collections.OrderedDict ?
1 votes
C'est simplement plus rapide. O(1) pour hashmap contre O(log n) pour ensemble ordonné.
21 votes
@utdmr : OrderedDict est trié par ordre d'insertion - pas par une clé arbitraire, comme un conteneur trié.
0 votes
@NeilG donc vous voulez dire que c'est en fait non trié, car "l'ordre d'insertion", me semble-t-il, est le seul ordre selon lequel les éléments peuvent se retrouver dans un conteneur.
2 votes
@Hi-Angel Non, ce n'est pas ce que conteneur trié signifie. Par exemple
0 votes
@NeilG Je ne suis pas sûr de ce que vous vouliez dire. Le post auquel vous faites référence explique tangentiellement qu'un conteneur trié est un conteneur qui trie les éléments lors de l'insertion. Ce que je veux dire, c'est que si vous insérez un élément et que vous ne faites pas le tri, vous vous retrouvez avec un "ordre d'insertion" dans le conteneur. Et comme je ne connais pas d'autre façon pour les éléments de se retrouver dans un conteneur, c'est une sorte d'"ordre naturel". Il n'est pas nécessaire de trier le conteneur pour que les éléments se retrouvent dans cet ordre.
1 votes
"Un conteneur trié est un conteneur qui trie les éléments lors de l'insertion". Pas exactement : Je dirais qu'un conteneur trié est un conteneur dont l'interface dispose d'une itération et d'une recherche triées (selon une clé arbitraire) efficaces. Votre incompréhension provient de votre définition inhabituelle.
0 votes
Il semble que sortedcontainers soit maintenant installé par défaut depuis Python 3.7.5 Vous pouvez l'utiliser directement dans coderpad.io et leetcode, sans installation. from sortedcontainers import SortedList sl = SortedList(['e', 'a', 'c', 'd', 'b']) print(sl)