conteneurs triés python
v2.1.0 JOSS
Sorted Containers est une bibliothèque de collections triées sous licence Apache2, écrite en Python pur et rapide en tant qu'extensions C.
La bibliothèque standard de Python est idéale jusqu'à ce que vous ayez besoin d'un type de collections triées. Beaucoup attesteront que vous pouvez aller très loin sans cela, mais dès que vous avez vraiment besoin d'une liste triée, d'un dict trié ou d'un ensemble trié, vous êtes confronté à une douzaine d'implémentations différentes, la plupart utilisant des extensions C sans une documentation et une analyse comparative approfondies.
En Python, nous pouvons faire mieux. Et nous pouvons le faire en Python pur !
> >> from sortedcontainers import SortedList
> >> sl = SortedList ([ 'e' , 'a' , 'c' , 'd' , 'b' ])
> >> sl
SortedList ([ 'a' , 'b' , 'c' , 'd' , 'e' ])
> >> sl *= 10_000_000
> >> sl . count ( 'c' )
10000000
> >> sl [ - 3 :]
[ 'e' , 'e' , 'e' ]
> >> from sortedcontainers import SortedDict
> >> sd = SortedDict ({ 'c' : - 3 , 'a' : 1 , 'b' : 2 })
> >> sd
SortedDict ({ 'a' : 1 , 'b' : 2 , 'c' : - 3 })
> >> sd . popitem ( index = - 1 )
( 'c' , - 3 )
> >> from sortedcontainers import SortedSet
> >> ss = SortedSet ( 'abracadabra' )
> >> ss
SortedSet ([ 'a' , 'b' , 'c' , 'd' , 'r' ])
> >> ss . bisect_left ( 'c' )
2Toutes les opérations présentées ci-dessus s'exécutent plus rapidement que le temps linéaire. La démo ci-dessus nécessite également près d'un gigaoctet de mémoire pour s'exécuter. Lorsque la liste triée est multipliée par dix millions, elle stocke dix millions de références à chacun de « a » à « e ». Chaque référence nécessite huit octets dans le conteneur trié. C'est assez difficile à battre car c'est le coût d'un pointeur vers chaque objet. C'est également 66 % de surcharge en moins qu'une implémentation d'arbre binaire typique (par exemple Red-Black Tree, AVL-Tree, AA-Tree, Splay-Tree, Treap, etc.) pour laquelle chaque nœud doit également stocker deux pointeurs vers des nœuds enfants.
Les conteneurs triés suppriment tout le travail des collections triées Python, ce qui facilite votre déploiement et votre utilisation de Python. Il n'est pas nécessaire d'installer un compilateur C ou de pré-construire et distribuer des extensions personnalisées. La performance est une fonctionnalité et les tests ont une couverture à 100 % avec des tests unitaires et des heures de stress.
Alex Martelli , membre de la Python Software Foundation
"Bonne chose ! ... J'aime l'idée de mise en œuvre simple et efficace consistant à diviser les conteneurs triés en "fragments" plus petits pour éviter les coûts d'insertion O(N)."
Jeff Knupp , auteur de Writing Idiomatic Python et Python Trainer
"Cette dernière partie, "rapide comme les extensions C", était difficile à croire. J'aurais besoin d'une sorte de comparaison des performances pour être convaincu que cela est vrai. L'auteur l'inclut dans la documentation. C'est le cas."
Kevin Samuel , Formateur Python et Django
Je suis assez étonné, non seulement par la qualité du code (il est incroyablement lisible et contient plus de commentaires que de code, wow), mais par la quantité réelle de travail que vous consacrez à des choses qui ne sont pas du code : documentation, analyse comparative, explications d'implémentation. Même le journal git est propre et les tests unitaires s'exécutent immédiatement sur Python 2 et 3.
Mark Summerfield , un court plaidoyer pour les collections triées par Python
La bibliothèque standard "piles incluses" de Python semble avoir une batterie manquante. Et l’argument selon lequel « nous n’en avons jamais eu auparavant » s’est émoussé. Il est temps que Python propose une gamme complète de classes de collection prêtes à l'emploi, y compris les classes triées.
Sorted Containers est utilisé dans des projets open source populaires tels que : Zipline, une bibliothèque de trading algorithmique de Quantopian ; Angr, une plateforme d'analyse binaire de l'UC Santa Barbara ; Trio, une bibliothèque d'E/S asynchrones ; et Dask Distributed, une bibliothèque de calcul distribuée prise en charge par Continuum Analytics.
L'installation de conteneurs triés est simple avec pip :
$ pip installer les conteneurs triés
Vous pouvez accéder à la documentation dans l'interpréteur avec la fonction d'aide intégrée de Python. L'aide fonctionne sur les modules, classes et méthodes dans les conteneurs triés.
> >> import sortedcontainers
> >> help ( sortedcontainers )
> >> from sortedcontainers import SortedDict
> >> help ( SortedDict )
> >> help ( SortedDict . popitem )La documentation complète sur les conteneurs triés est disponible sur http://www.grantjenks.com/docs/sortedcontainers/
Le guide de l'utilisateur fournit une introduction aux conteneurs triés ainsi que des comparaisons et des analyses approfondies des performances.
Le guide de la communauté fournit des informations sur le développement de Sorted Containers ainsi que des détails sur le support, la mise en œuvre et l'historique.
La documentation de l'API fournit des informations sur les fonctions, classes et modules spécifiques du package Sorted Containers.
Copyright 2014-2024 Grant Jenks
Sous licence Apache, version 2.0 (la « Licence » ); vous ne pouvez pas utiliser ce fichier sauf en conformité avec la licence. Vous pouvez obtenir une copie de la licence à
http://www.apache.org/licenses/LICENSE-2.0
Sauf disposition contraire de la loi applicable ou accord écrit, le logiciel distribué sous la licence est distribué « EN L'ÉTAT », SANS GARANTIE OU CONDITION D'AUCUNE SORTE, expresse ou implicite. Consultez la licence pour connaître la langue spécifique régissant les autorisations et les limitations en vertu de la licence.
