¿Python tiene un conjunto ordenado?

477

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

Casebash
fuente
18
¿Qué hay de lo contrario, una bolsa de cosas? (desordenado y no único)
wim
19
@wim collections.Counteres la bolsa de Python.
flornquake
1
¿Qué pasa si algo se agrega dos veces? ¿Cuál debería ser la posición?
McKay
2
@McKay - si siguiera el comportamiento de las colecciones
OrderDict

Respuestas:

206

Hay una receta de conjunto ordenado (posible nuevo enlace ) para esto al 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 la misma que 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 .unionno coincide con la del conjunto, pero como incluye __or__algo similar se puede agregar fácilmente:

@staticmethod
def union(*sets):
    union = OrderedSet()
    union.union(*sets)
    return union

def union(self, *sets):
    for set in sets:
        self |= set
Casebash
fuente
66
Seleccioné mi propia respuesta porque la referencia de la documentación lo acerca a una respuesta oficial
Casebash
49
La interfaz no es exactamente el mismo que el objeto conjunto normal, muchos métodos esenciales faltan tales como update, union, intersection.
xApple
55
Para su información, noté que una versión ligeramente modificada de la receta citada en esta respuesta se ha agregado a PyPi como "conjunto ordenado"
Geoffrey Hing
77
Estoy bastante seguro de que no puedes tener dos métodos llamados unionen la misma clase. El último "ganará" y el primero no existirá en tiempo de ejecución. Esto se debe a que OrderedSet.union(sin parens) tiene que referirse a un solo objeto.
Kevin
3
También hay un paquete "ordenado" que se basa en la misma receta pero implementado en Cython: pypi.python.org/pypi/orderedset .
mbdevpl
149

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 en un diccionario ordenado (por ejemplo, asignándolos 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 unos pocos métodos deben definirse o anularse: collections.OrderedDicty collections.MutableSethaga 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 = __sub__ 
    difference_update = __isub__
    intersection = __and__
    intersection_update = __iand__
    issubset = __le__
    issuperset = __ge__
    symmetric_difference = __xor__
    symmetric_difference_update = __ixor__
    union = __or__
Stephan202
fuente
1
@Casebash: sí, uno puede querer definir una clase OrderedSet, que subclases OrderedDicty abc.Sety luego definir __len__, __iter__y __contains__.
Stephan202
1
@ Stephan202: Lamentablemente, el ABC de recogida viven en collections, pero por lo demás una buena sugerencia
u0b34a0f6ae
44
Esto es cierto, pero como resultado tiene mucho espacio desperdiciado, lo que conduce a un rendimiento subóptimo.
Daniel Kats
3
Una adicion; collections.OrderedDict también está disponible en python 2.7.
Nurbldoff
2
Hacer OrderedSet([1,2,3])plantea un error de tipo. ¿Cómo funciona el constructor? Falta el ejemplo de uso.
xApple
90

La respuesta es no, pero puede usar collections.OrderedDictdesde 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), el estándar dictestá garantizado para preservar el orden y es más rendimiento inferior OrderedDict. (Sin embargo, para la compatibilidad con versiones anteriores y especialmente la legibilidad, es posible que desee continuar usando OrderedDict).

Aquí hay un ejemplo de cómo usarlo dictcomo conjunto ordenado para filtrar elementos duplicados mientras se preserva el orden, emulando así un conjunto ordenado. Use el dictmétodo de clase fromkeys()para crear un dict, luego simplemente solicite el keys()reverso.

>>> keywords = ['foo', 'bar', 'bar', 'foo', 'baz', 'foo']

>>> list(dict.fromkeys(keywords))
['foo', 'bar', 'baz']
jrc
fuente
44
Quizás valga la pena mencionar que esto también funciona (más rápido) con vainilla dict.fromkeys(). Pero en ese caso, el orden de las claves solo se conserva en las implementaciones de CPython 3.6+, por lo que OrderedDictes una solución más portátil cuando el orden es importante.
jez
1
no funcionará si los valores no son una cadena
Anwar Hossain
44
@AnwarHossain keys = (1,2,3,1,2,1) list(OrderedDict.fromkeys(keys).keys())-> [1, 2, 3], python-3.7. Funciona.
raratiru
1
¿Podemos inferir que Set in Python 3.7+ conserva también el orden?
user474491
2
@ user474491 A diferencia dict, seten Python 3.7+ desafortunadamente no conserva el orden.
cz
39

Puedo hacer algo mejor que un orderedSet: Bolton tiene un puro en Python, con capacidad para 3 2 / IndexedSetTipo que no sólo es un conjunto ordenado, pero también es compatible con la indexación (al igual que con las listas).

Simplemente pip install boltons(o cópielo setutils.pyen su base de código), importe el IndexedSety:

>>> 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 retenido en orden. Divulgación completa: escribí el IndexedSet, pero eso también significa que puedes molestarme si hay algún problema . :)

Mahmoud Hashemi
fuente
39

Implementaciones en PyPI

Mientras que otros han señalado que no hay una implementación integrada de un conjunto de preservación del 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 .

Hay los paquetes:

Algunas de estas implementaciones se basan en la receta publicada por Raymond Hettinger en ActiveState, que también se menciona en otras respuestas aquí.

Algunas diferencias

  • conjunto ordenado (versión 1.1)
    • ventaja: O (1) para búsquedas por índice (p my_set[5]. ej. )
  • 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).

Daniel K
fuente
2
Un nuevo contendiente es collections_extended.setlist . Sin set.unionembargo, funciones como no funcionan en él, a pesar de que hereda collections.abc.Set.
Timdiels
3
OrderedSetahora es compatibleremove
warvariuc
17

Si está utilizando el conjunto ordenado para mantener un orden ordenado, considere usar una implementación de conjunto ordenado de PyPI. El módulo sortedcontainers proporciona un SortedSet solo para este propósito. Algunos beneficios: Python puro, implementaciones rápidas como C, 100% de cobertura de prueba unitaria, horas de prueba de esfuerzo

Instalar desde PyPI es fácil con pip:

pip install sortedcontainers

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

Una vez instalado, simplemente puede:

from sortedcontainers import SortedSet
help(SortedSet)

El módulo sortedcontainers 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, existe alternativamente un tipo de datos SortedList que se puede usar para implementar eficientemente una bolsa.

GrantJ
fuente
Tenga en cuenta que la SortedSetclase requiere que los miembros sean comparables y que se puedan compartir.
gsnedders
44
@gsnedders Los incorporados sety frozensettambién requieren elementos para ser hashaable. La restricción comparable es la adición para SortedSet, pero también es una restricción obvia.
Gotgenes
2
Como su nombre indica, esto no mantiene el orden. No es nada más que ordenado (set ([secuencia])) lo que hace mejor?
ldmtwo
@ldmtwo No estoy seguro de a qué se refiere, pero para ser claros, SortedSet como parte de Sorted Containers mantiene el orden ordenado.
GrantJ
2
@GrantJ: es la diferencia entre si mantiene el orden de inserción o el orden de clasificación . La mayoría de las otras respuestas están relacionadas con el orden de inserción. Creo que ya estás al tanto de esto en base a tu primera oración, pero probablemente es lo que dice ldmtwo.
Justin
9

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

Ejemplos del artículo:

indA = pd.Index([1, 3, 5, 7, 9])
indB = pd.Index([2, 3, 5, 7, 11])

indA & indB  # intersection
indA | indB  # union
indA - indB  # difference
indA ^ indB  # symmetric difference
Berislav Lopac
fuente
¿Puedes incluir un ejemplo en esta respuesta? Los enlaces tienden a romperse después de un tiempo.
Alechan
1
para la diferencia entre conjuntos, en realidad necesita usar indA.difference(indB), el signo menos realiza la resta estándar
gg349
7

Un poco tarde para el juego, pero he escrito una clase setlistcomo parte de collections-extendedeso, implementa completamente ambos SequenceySet

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

Michael Lenzen
fuente
7

No hay OrderedSeten la biblioteca oficial. Hago una hoja de referencia 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']
}
Cálculo
fuente
3

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

RichardB
fuente
2

Como mencionan otras respuestas, en cuanto a python 3.7+, el dict está ordenado por definición. En lugar de subclasificar OrderedDictpodemos subclasificar abc.collections.MutableSeto typing.MutableSetusar las claves del dict para almacenar nuestros valores.

class OrderedSet(typing.MutableSet[T]):
    """A set that preserves insertion order by internally using a dict."""

    def __init__(self, iterable: t.Iterator[T]):
        self._d = dict.fromkeys(iterable)

    def add(self, x: T) -> None:
        self._d[x] = None

    def discard(self, x: T) -> None:
        self._d.pop(x)

    def __contains__(self, x: object) -> bool:
        return self._d.__contains__(x)

    def __len__(self) -> int:
        return self._d.__len__()

    def __iter__(self) -> t.Iterator[T]:
        return self._d.__iter__()

Entonces solo:

x = OrderedSet([1, 2, -1, "bar"])
x.add(0)
assert list(x) == [1, 2, -1, "bar", 0]

Puse este código en una pequeña biblioteca , para que cualquiera pueda usarlo pip install.

bustawin
fuente
-4

Para muchos propósitos, basta con llamar a sorted. 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 generará 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 usar OrderedDict de colecciones con un valor arbitrario como Ninguno.

hwrd
fuente
43
El propósito de OrderedSet es poder obtener los elementos en el orden en que se agregaron al conjunto. Su ejemplo podría llamarse SortedSet ...
Mantenimiento periódico
-4

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

Loïc N.
fuente
El principal problema con este enfoque es que agregar ejecuciones en O (n). Lo que significa que se vuelve más lento con grandes listas. Los conjuntos integrados de Python son muy buenos para acelerar la adición de elementos. Pero para casos de uso simples, ¡ciertamente funciona!
Draconis el