¿Python tiene un set ordenado?

Python tiene un diccionario ordenado . ¿Qué pasa con un conjunto ordenado?

Hay una receta de un conjunto ordenado (posible nuevo enlace ) para esto, a la que se hace referencia en la documentación de Python 2 . Esto se ejecuta en Py2.6 o posterior y 3.0 o posterior sin ninguna modificación. La interfaz es casi exactamente igual a un conjunto normal, excepto que la inicialización debe hacerse con una lista.

 OrderedSet([1, 2, 3]) 

Este es un MutableSet, por lo que la firma para .union no coincide con la de set, pero como incluye __or__ se puede agregar fácilmente algo similar:

 @staticmethod def union(*sets): union = OrderedSet() union.union(*sets) return union def union(self, *sets): for set in sets: self |= set 

Un conjunto ordenado es funcionalmente un caso especial de un diccionario ordenado.

Las claves de un diccionario son únicas. Por lo tanto, si uno ignora los valores de un diccionario ordenado (p. Ej., Asignándoles None ), entonces uno tiene esencialmente un conjunto ordenado.

A partir de Python 3.1 hay collections.OrderedDict . El siguiente es un ejemplo de implementación de un OrderedSet. (Tenga en cuenta que solo es necesario definir o anular algunos métodos: collections.OrderedDict y collections.MutableSet hace el trabajo pesado.)

 import collections class OrderedSet(collections.OrderedDict, collections.MutableSet): def update(self, *args, **kwargs): if kwargs: raise TypeError("update() takes no keyword arguments") for s in args: for e in s: self.add(e) def add(self, elem): self[elem] = None def discard(self, elem): self.pop(elem, None) def __le__(self, other): return all(e in other for e in self) def __lt__(self, other): return self <= other and self != other def __ge__(self, other): return all(e in self for e in other) def __gt__(self, other): return self >= other and self != other def __repr__(self): return 'OrderedSet([%s])' % (', '.join(map(repr, self.keys()))) def __str__(self): return '{%s}' % (', '.join(map(repr, self.keys()))) difference = property(lambda self: self.__sub__) difference_update = property(lambda self: self.__isub__) intersection = property(lambda self: self.__and__) intersection_update = property(lambda self: self.__iand__) issubset = property(lambda self: self.__le__) issuperset = property(lambda self: self.__ge__) symmetric_difference = property(lambda self: self.__xor__) symmetric_difference_update = property(lambda self: self.__ixor__) union = property(lambda self: self.__or__) 

Implementaciones en PyPI

Mientras que otros han señalado que no hay una implementación incorporada de un conjunto de conservación de orden de inserción en Python (todavía), siento que a esta pregunta le falta una respuesta que indique qué se puede encontrar en PyPI .

Hasta donde sé, actualmente hay:

  • conjunto ordenado
  • oset

Ambas implementaciones se basan en la receta publicada por Raymond Hettinger en ActiveState, que también se menciona en otras respuestas aquí. He comprobado ambos e identificado los siguientes

diferencias criticas:

  • conjunto ordenado (versión 1.1)
    • ventaja: O (1) para búsquedas por índice (por ejemplo, my_set[5] )
    • desventaja: remove(item) no implementado
  • oset (versión 0.1.3)
    • ventaja: O (1) para remove(item)
    • desventaja: aparentemente O (n) para búsquedas por índice

Ambas implementaciones tienen O (1) para add(item) y __contains__(item) ( item in my_set ).

Desafortunadamente, ninguna de las implementaciones tiene operaciones de conjuntos basadas en set1.union(set2) como set1.union(set2) -> Tiene que usar el formulario basado en operadores como set1 | set2 set1 | set2 en set1 | set2 lugar. Consulte la documentación de Python sobre Set Objects para obtener una lista completa de los métodos de operación de set y sus equivalentes basados ​​en operadores.

Primero fui con el conjunto ordenado hasta que usé remove(item) por primera vez, lo que bloqueó mi script con un NotImplementedError . Como nunca he usado la búsqueda por índice hasta ahora, mientras tanto cambié a oset.

Si conoce otras implementaciones en PyPI, avíseme en los comentarios.

Puedo hacerte uno mejor que un OrderedSet: boltons tiene un tipo exclusivo de Python, compatible con IndexedSet que no solo es un conjunto ordenado, sino que también admite indexación (como en las listas).

Simplemente pip install boltons (o copie setutils.py en su base de código), importe el IndexedSet y:

 >>> from boltons.setutils import IndexedSet >>> x = IndexedSet(list(range(4)) + list(range(8))) >>> x IndexedSet([0, 1, 2, 3, 4, 5, 6, 7]) >>> x - set(range(2)) IndexedSet([2, 3, 4, 5, 6, 7]) >>> x[-1] 7 >>> fcr = IndexedSet('freecreditreport.com') >>> ''.join(fcr[:fcr.index('.')]) 'frecditpo' 

Todo es único y se conserva en orden. Revelación completa: escribí el IndexedSet , pero eso también significa que me puede molestar si hay algún problema . 🙂

La respuesta es no, pero puede usar collections.OrderedDict OrderedDict de la biblioteca estándar de Python con solo claves (y valores como None ) para el mismo propósito.

Actualización : a partir de Python 3.7 (y CPython 3.6), se garantiza que el dict estándar conserva el orden y es más OrderedDict que OrderedDict . (Sin embargo, para la portabilidad y la legibilidad, es posible que desee continuar usando OrderedDict ).

Este es un ejemplo de cómo usar dict como un conjunto ordenado para filtrar elementos duplicados mientras se conserva el orden, emulando así un conjunto ordenado. Use el método de clase dict fromkeys() para crear un dict, luego simplemente pida las keys() nuevamente.

 >>> keywords = ['foo', 'bar', 'bar', 'foo', 'baz', 'foo'] >>> list(dict.fromkeys(keywords).keys()) ['foo', 'bar', 'baz'] 

Si está utilizando el conjunto ordenado para mantener un orden ordenado, considere usar una implementación del conjunto ordenado de PyPI. El módulo sortedcontainers proporciona un SortedSet para este propósito. Algunos beneficios: Pure-Python, implementaciones rápidas como C, 100% de cobertura de pruebas unitarias, horas de pruebas de estrés.

Instalar desde PyPI es fácil con pip:

 pip install sortedcontainers 

Tenga en cuenta que si no puede pip install , simplemente extraiga los archivos sortedlist.py y sortedset.py del repository de código abierto .

Una vez instalado, puedes simplemente:

 from sortedcontainers import SortedSet help(SortedSet) 

El módulo de contenedores ordenados también mantiene una comparación de rendimiento con varias implementaciones alternativas.

Para el comentario que preguntó sobre el tipo de datos de la bolsa de Python, hay alternativamente un tipo de datos de lista ordenada que se puede usar para implementar una bolsa de manera eficiente.

En caso de que ya esté utilizando pandas en su código, su objeto de Index comporta como un conjunto ordenado, como se muestra en este artículo .

Un poco tarde para el juego, pero he escrito una setlist clase como parte de collections-extended que implementa completamente la Sequence y el Set

 >>> from collections_extended import setlist >>> sl = setlist('abracadabra') >>> sl setlist(('a', 'b', 'r', 'c', 'd')) >>> sl[3] 'c' >>> sl[-1] 'd' >>> 'r' in sl # testing for inclusion is fast True >>> sl.index('d') # so is finding the index of an element 4 >>> sl.insert(1, 'd') # inserting an element already in raises a ValueError ValueError >>> sl.index('d') 4 

GitHub: https://github.com/mlenzen/collections-extended

Documentación: http://collections-extended.lenzm.net/en/latest/

PyPI: https://pypi.python.org/pypi/collections-extended

No hay OrderedSet en la biblioteca oficial. Hago una hoja de trucos exhaustiva de toda la estructura de datos para su referencia.

 DataStructure = { 'Collections': { 'Map': [ ('dict', 'OrderDict', 'defaultdict'), ('chainmap', 'types.MappingProxyType') ], 'Set': [('set', 'frozenset'), {'multiset': 'collection.Counter'}] }, 'Sequence': { 'Basic': ['list', 'tuple', 'iterator'] }, 'Algorithm': { 'Priority': ['heapq', 'queue.PriorityQueue'], 'Queue': ['queue.Queue', 'multiprocessing.Queue'], 'Stack': ['collection.deque', 'queue.LifeQueue'] }, 'text_sequence': ['str', 'byte', 'bytearray'] } 

Para muchos propósitos, basta con llamar ordenado será suficiente. Por ejemplo

 >>> s = set([0, 1, 2, 99, 4, 40, 3, 20, 24, 100, 60]) >>> sorted(s) [0, 1, 2, 3, 4, 20, 24, 40, 60, 99, 100] 

Si va a utilizar esto repetidamente, habrá una sobrecarga al llamar a la función ordenada, por lo que es posible que desee guardar la lista resultante, siempre que haya terminado de cambiar el conjunto. Si necesita mantener elementos únicos y ordenados, estoy de acuerdo con la sugerencia de utilizar OrderedDict de colecciones con un valor arbitrario como Ninguno.

El paquete ParallelRegression proporciona una clase de conjunto ordenada setList () que está más completa en cuanto al método que las opciones basadas en la receta de ActiveState. Admite todos los métodos disponibles para listas y la mayoría, si no todos, los métodos disponibles para conjuntos.

Así que también tenía una pequeña lista donde claramente tenía la posibilidad de introducir valores no únicos.

Busqué la existencia de una lista única de algún tipo, pero luego me di cuenta de que probar la existencia del elemento antes de agregarlo funciona bien.

 if(not new_element in my_list): my_list.append(new_element) 

No sé si hay advertencias a este enfoque simple, pero resuelve mi problema.

Hay cuatro tipos de pedidos que uno podría querer, creo:

  1. Ordenado por llave
  2. Ordenado por valor (aunque no he oído hablar de nadie, pida éste)
  3. Ordenado por tiempo de modificación
  4. Ordenado por tiempo adicional

Creo que las colecciones.OrderedDict te pone # 4. O puede eliminar una clave y volver a agregarla, para # 3.

Para el # 1, probablemente deberías registrarte en un árbol rojo-negro o treap:

Los árboles rojo-negro tienen una baja variabilidad en los tiempos de operación (por lo que podrían ser mejores para las aplicaciones interactivas), pero no son tan rápidos como las ttwigs en promedio (lo que podría ser mejor para el procesamiento por lotes) promedio, pero cuando se reorganizan puede tomar un tiempo relativamente largo).

Ambos son estructuras de datos establecidas con implementaciones en muchos idiomas.