contenedores ordenados en Python
v2.1.0 JOSS
Sorted Containers es una biblioteca de colecciones ordenadas con licencia Apache2, escrita en Python puro y rápida como extensiones C.
La biblioteca estándar de Python es excelente hasta que necesites un tipo de colecciones ordenadas. Muchos darán fe de que puedes llegar muy lejos sin uno, pero en el momento en que realmente necesitas una lista ordenada, un dictado ordenado o un conjunto ordenado, te enfrentas a una docena de implementaciones diferentes, la mayoría usando extensiones C sin gran documentación ni evaluación comparativa.
En Python, podemos hacerlo mejor. ¡Y podemos hacerlo en Python puro!
> >> 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' )
2Todas las operaciones que se muestran arriba se ejecutan en un tiempo más rápido que el lineal. La demostración anterior también requiere casi un gigabyte de memoria para ejecutarse. Cuando la lista ordenada se multiplica por diez millones, almacena diez millones de referencias a cada una de "a" hasta "e". Cada referencia requiere ocho bytes en el contenedor ordenado. Eso es bastante difícil de superar ya que es el costo de un puntero a cada objeto. También supone un 66% menos de gastos generales que una implementación típica de árbol binario (por ejemplo, árbol rojo-negro, árbol AVL, árbol AA, árbol Splay, Treap, etc.) para el cual cada nodo también debe almacenar dos punteros a nodos secundarios.
Sorted Containers elimina todo el trabajo de las colecciones ordenadas de Python, lo que facilita la implementación y el uso de Python. No es necesario instalar un compilador de C ni crear previamente y distribuir extensiones personalizadas. El rendimiento es una característica y las pruebas tienen una cobertura del 100% con pruebas unitarias y horas de estrés.
Alex Martelli , miembro de la Python Software Foundation
"¡Qué bueno!... Me gusta la idea de implementación simple y efectiva de dividir los contenedores ordenados en "fragmentos" más pequeños para evitar los costos de inserción O(N).
Jeff Knupp , autor de Writing Idiomatic Python y Python Trainer
"Esa última parte, "rápida como extensiones C", era difícil de creer. Necesitaría algún tipo de comparación de rendimiento para estar convencido de que esto es cierto. El autor incluye esto en los documentos. Lo es".
Kevin Samuel , entrenador de Python y Django
Estoy bastante sorprendido, no sólo por la calidad del código (es increíblemente legible y tiene más comentarios que código, guau), sino también por la cantidad real de trabajo que dedicas a cosas que no son código: documentación, evaluación comparativa, explicaciones de implementación. Incluso el registro de git está limpio y las pruebas unitarias se ejecutan de forma inmediata en Python 2 y 3.
Mark Summerfield , un breve alegato a favor de las colecciones ordenadas de Python
A la biblioteca estándar "baterías incluidas" de Python parece que le falta una batería. Y el argumento de que "nunca lo tuvimos antes" se ha desgastado. Es hora de que Python ofrezca una gama completa de clases de colección listas para usar, incluidas las ordenadas.
Sorted Containers se utiliza en proyectos populares de código abierto como: Zipline, una biblioteca de comercio algorítmico de Quantopian; Angr, una plataforma de análisis binario de UC Santa Barbara; Trio, una biblioteca de E/S asíncronas; y Dask Distributed, una biblioteca de computación distribuida respaldada por Continuum Analytics.
Instalar contenedores clasificados es simple con pip:
$ pip instalar contenedores ordenados
Puede acceder a la documentación en el intérprete con la función de ayuda incorporada de Python. La ayuda funciona con módulos, clases y métodos en Sorted Containers.
> >> import sortedcontainers
> >> help ( sortedcontainers )
> >> from sortedcontainers import SortedDict
> >> help ( SortedDict )
> >> help ( SortedDict . popitem )La documentación completa para contenedores clasificados está disponible en http://www.grantjenks.com/docs/sortedcontainers/
La guía del usuario proporciona una introducción a los contenedores clasificados y extensas comparaciones y análisis de rendimiento.
La guía de la comunidad proporciona información sobre el desarrollo de Sorted Containers junto con detalles de soporte, implementación y historial.
La documentación de la API proporciona información sobre funciones, clases y módulos específicos en el paquete Sorted Containers.
Copyright 2014-2024 Grant Jenks
Licenciado bajo la Licencia Apache, Versión 2.0 (la "Licencia"); no puede utilizar este archivo excepto de conformidad con la Licencia. Puede obtener una copia de la Licencia en
http://www.apache.org/licenses/LICENSE-2.0
A menos que lo exija la ley aplicable o se acuerde por escrito, el software distribuido bajo la Licencia se distribuye "TAL CUAL", SIN GARANTÍAS NI CONDICIONES DE NINGÚN TIPO, ya sean expresas o implícitas. Consulte la Licencia para conocer el idioma específico que rige los permisos y limitaciones de la Licencia.
