font - subplot python title

¿Python tiene un set ordenado?

Question

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

Answer 1

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:

• ordered-set
• 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) -> set1.union(set2) 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.

Answer 2

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__)

Answer 3

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 para este enfoque simple, pero resuelve mi problema.

Answer 4

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.

Answer 5

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 .

Answer 6

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 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:

• http://pypi.python.org/pypi/bintrees/0.3.0
• http://pypi.python.org/pypi/rbtree/
• http://stromberg.dnsalias.org/~dstromberg/treap/

Los árboles rojo-negro tienen una baja variabilidad en los tiempos de operación (por lo que podrían ser mejores para aplicaciones interactivas), pero no son tan rápidos como 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.

Answer 7

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 modificaciones. 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

Answer 8

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'']
}

Answer 9

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 usar esto repetidamente, se incurrirá en gastos generales 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.

Answer 10

Puedo hacerte uno mejor que un OrderedSet: boltons tiene un tipo de IndexedSet compatible puro con Python, 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 . :)

Answer 11

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 repositorio 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 SortedList que se puede usar para implementar una bolsa de manera eficiente.

Answer 12

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

Answer 13

>>> a = {3, 4, 2, 6, 1, 7}
>>> type(a)
<class ''set''>
>>> sorted(a, reverse=True)
[7, 6, 4, 3, 2, 1]
>>> sorted(a)
[1, 2, 3, 4, 6, 7]