data - python set

Python equivalente a java.util.SortedSet?

Question

¿Alguien sabe si Python tiene un equivalente a la interfaz SortedSet de Java?

Aquí está lo que estoy buscando: digamos que tengo un objeto de tipo foo , y sé cómo comparar dos objetos de tipo foo para ver si foo1 es "mayor que" o "menor que" foo2 . Quiero una forma de almacenar muchos objetos del tipo foo en una lista L , de modo que cada vez que recorra la lista L , ordene los objetos, de acuerdo con el método de comparación que defino.

Editar:

Supongo que puedo usar un diccionario o una lista y sort() cada vez que lo modifique, pero ¿es esta la mejor manera?

Answer 1

¿Tienes la posibilidad de usar Jython? Solo lo menciono porque usar TreeMap, TreeSet, etc. es trivial. Además, si viene de un entorno Java y quiere dirigirse en una dirección Pythonic, Jython es maravilloso para facilitar la transición. Aunque reconozco que el uso de TreeSet en este caso no sería parte de tal "transición".

Para los superusuarios de Jython, tengo una pregunta: el paquete blist no se puede importar porque usa un archivo C que se debe importar. ¿Pero habría alguna ventaja de usar blist en lugar de TreeSet? ¿Podemos generalmente asumir que la JVM usa algoritmos que son esencialmente tan buenos como los de CPython?

Answer 2

Al igual que blist.sortedlist, el módulo sortedcontainers proporciona una lista ordenada, un conjunto ordenado y un tipo de datos ordenados ordenados. Utiliza un árbol B modificado en la implementación subyacente y es más rápido que blist en la mayoría de los casos.

El módulo sortedcontainers es puro-Python, por lo que la instalación es fácil:

pip install sortedcontainers

Entonces, por ejemplo:

from sortedcontainers import SortedList, SortedDict, SortedSet
help(SortedList)

El módulo de contenedores ordenados tiene pruebas de cobertura del 100% y horas de estrés. Hay una comparación de rendimiento bastante completa que enumera la mayoría de las opciones que consideraría para esto.

Answer 3

Echa un vistazo a BTrees . Parece que necesitas uno de ellos. Según tengo entendido, necesita una estructura que admita la inserción relativamente barata del elemento en la estructura de almacenamiento y la operación de clasificación barata (o incluso la falta de ella). BTrees ofrece eso.

Tengo experiencia con ZODB.BTrees, y se escalan a miles y millones de elementos.

Answer 4

Puede usar insort del módulo insort para insertar nuevos elementos de manera eficiente en una lista ya ordenada:

from bisect import insort

items = [1,5,7,9]
insort(items, 3)
insort(items, 10)

print items # -> [1, 3, 5, 7, 9, 10]

Tenga en cuenta que esto no corresponde directamente a SortedSet , porque utiliza una lista. Si inserta el mismo elemento más de una vez, tendrá duplicados en la lista.

Answer 5

Si está buscando una implementación de un tipo de contenedor eficiente para Python implementado usando algo como un árbol de búsqueda equilibrado (un árbol Rojo-Negro, por ejemplo), entonces no es parte de la biblioteca estándar.

Sin embargo, pude encontrar esto:

http://www.brpreiss.com/books/opus7/

El código fuente está disponible aquí:

http://www.brpreiss.com/books/opus7/public/Opus7-1.0.tar.gz

No sé cómo se licencia el código fuente, y no lo he usado yo mismo, pero sería un buen lugar para comenzar a buscar si no está interesado en utilizar sus propias clases de contenedor.

Hay PyAVL que es un módulo C que implementa un árbol AVL.

Además, este hilo puede ser útil para usted. Contiene muchas sugerencias sobre cómo usar el módulo bisect para mejorar el diccionario de Python existente para hacer lo que está pidiendo.

Por supuesto, usar insort () de esa manera sería bastante costoso para la inserción y eliminación, así que considérelo cuidadosamente para su aplicación. Implementar una estructura de datos apropiada probablemente sería un mejor enfoque.

En cualquier caso, para comprender si debe mantener la estructura de datos ordenada u ordenada cuando se realiza una iteración, debe saber si desea insertar mucho o iterar mucho. Mantener la estructura de datos ordenada tiene sentido si modifica su contenido con poca frecuencia pero lo repite mucho. A la inversa, si inserta y elimina miembros todo el tiempo pero repite la recopilación con relativa frecuencia, la clasificación de las claves antes de la iteración será más rápida. No hay un enfoque correcto.

Answer 6

Si solo necesita las claves y ningún valor asociado, Python ofrece conjuntos:

s = set(a_list)

for k in sorted(s):
    print k

Sin embargo, ordenará el conjunto cada vez que haga esto. Si eso es una sobrecarga excesiva, es posible que desee consultar HeapQueues . Puede que no sean tan elegantes y "Pythonic" pero tal vez se ajusten a sus necesidades.

Answer 7

Use blist.sortedlist del paquete blist .

from blist import sortedlist

z = sortedlist([2, 3, 5, 7, 11])
z.add(6)
z.add(3)
z.add(10)

print z

Esto dará como resultado:

sortedlist([2, 3, 3, 5, 6, 7, 10, 11])

El objeto resultante se puede utilizar como una lista de python.

>>> len(z)
8
>>> [2 * x for x in z]
[4, 6, 6, 10, 12, 14, 20, 22]