O Python tem um conjunto ordenado?

Python tem um dicionário ordenado . Que tal um conjunto encomendado?

Existe uma receita de conjunto ordenado (possível novo link ) para isso, que é referida na documentação do Python 2 . Isso é executado no Py2.6 ou posterior e 3.0 ou posterior sem nenhuma modificação. A interface é quase exatamente igual a um conjunto normal, exceto que a inicialização deve ser feita com uma lista.

OrderedSet([1, 2, 3])

Como é um MutableSet, a assinatura para .unionnão corresponde à do conjunto, mas como inclui __or__algo semelhante, pode ser facilmente adicionada:

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

def union(self, *sets):
    for set in sets:
        self |= set

Um conjunto ordenado é funcionalmente um caso especial de um dicionário ordenado.

As chaves de um dicionário são únicas. Assim, se alguém desconsidera os valores em um dicionário ordenado (por exemplo, atribuindo-os None), então um possui essencialmente um conjunto ordenado.

A partir do Python 3.1, existe collections.OrderedDict. A seguir, é apresentado um exemplo de implementação de um OrderedSet. (Observe que apenas alguns métodos precisam ser definidos ou substituídos: collections.OrderedDicte collections.MutableSetfaça o trabalho 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__

A resposta é não, mas você pode usar collections.OrderedDictda biblioteca padrão do Python apenas com chaves (e valores como None) para o mesmo objetivo.

Atualização : A partir do Python 3.7 (e CPython 3.6), o padrão dicté garantido para preservar a ordem e tem mais desempenho do que OrderedDict. (Para compatibilidade com versões anteriores e, especialmente, legibilidade, no entanto, convém continuar usando OrderedDict.)

Aqui está um exemplo de como usar dictcomo um conjunto ordenado para filtrar itens duplicados enquanto preserva a ordem, emulando um conjunto ordenado. Use o dictmétodo de classe fromkeys()para criar um ditado e, em seguida, simplesmente peça as keys()costas.

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

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

Eu posso fazer melhor do que um OrderedSet: Bolton tem um puro-Python, 03/02 compatível IndexedSettipo que não é apenas um conjunto ordenado, mas também suporta indexação (como com listas).

Simplesmente pip install boltons(ou copie setutils.pypara a sua base de código), importe o IndexedSete:

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

Tudo é único e mantido em ordem. Divulgação completa: eu escrevi o IndexedSet, mas isso também significa que você pode me incomodar se houver algum problema . :)

Implementações no PyPI

Enquanto outros apontaram que ainda não existe uma implementação embutida de um conjunto de preservação de ordem de inserção no Python, sinto que essa pergunta está faltando uma resposta que indica o que pode ser encontrado no PyPI .

Existem os pacotes:

• conjunto ordenado (baseado em Python)
• orderedset (baseado em Cython)
• coleções estendidas
• oset (última atualização em 2012)

Algumas dessas implementações são baseadas na receita postada por Raymond Hettinger no ActiveState, que também é mencionada em outras respostas aqui.

Algumas diferenças

• conjunto ordenado (versão 1.1)
  • vantagem: O (1) para pesquisas por índice (por exemplo my_set[5])
• oset (versão 0.1.3)
  • vantagem: O (1) para remove(item)
  • desvantagem: aparentemente O (n) para pesquisas por índice

Ambas as implementações têm O (1) para add(item)e __contains__(item)( item in my_set).

Se você estiver usando o conjunto ordenado para manter uma ordem classificada, considere usar uma implementação de conjunto classificado do PyPI. O módulo de contêineres classificados fornece um SortedSet apenas para essa finalidade. Alguns benefícios: implementações de Python puro, fast-as-C, 100% de cobertura de teste de unidade, horas de teste de estresse.

A instalação do PyPI é fácil com o pip:

pip install sortedcontainers

Observe que, se não puder pip install, basta puxar os arquivos sorted.py e sorted.set.py do repositório de código-fonte aberto .

Uma vez instalado, você pode simplesmente:

from sortedcontainers import SortedSet
help(SortedSet)

O módulo de contêineres classificados também mantém uma comparação de desempenho com várias implementações alternativas.

Para o comentário que foi perguntado sobre o tipo de dados da bolsa do Python, existe alternativamente um tipo de dados SortedList que pode ser usado para implementar com eficiência uma bolsa.

Caso você já esteja usando pandas em seu código, o Indexobjeto se comporta como um conjunto ordenado, conforme mostrado neste artigo .

Exemplos do artigo:

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

Um pouco tarde para o jogo, mas eu escrevi uma classe setlistcomo parte do collections-extendedque totalmente implementa ambos SequenceeSet

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

Documentação: http://collections-extended.lenzm.net/en/latest/

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

Não há OrderedSetna biblioteca oficial. Eu faço um cheatsheet exaustivo de toda a estrutura de dados para sua referência.

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

O pacote ParallelRegression fornece uma classe de conjunto ordenada setList () com mais método completo do que as opções baseadas na receita ActiveState. Ele suporta todos os métodos disponíveis para listas e a maioria, se não todos, métodos disponíveis para conjuntos.

Como outras respostas mencionam, como no python 3.7+, o dict é ordenado por definição. Em vez de subclassificar OrderedDict, podemos subclassificar abc.collections.MutableSetou typing.MutableSetusar as chaves do dict para armazenar nossos 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__()

Então apenas:

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

Coloquei esse código em uma pequena biblioteca , para que qualquer um possa fazer pip installisso.

Para muitos propósitos, basta chamar ordenado será suficiente. Por exemplo

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

Se você usar isso repetidamente, haverá uma sobrecarga ao chamar a função classificada, para que você queira salvar a lista resultante, desde que termine de alterar o conjunto. Se você precisar manter elementos exclusivos e classificados, concordo com a sugestão de usar OrderedDict de coleções com um valor arbitrário como Nenhum.

Então, eu também tinha uma pequena lista em que claramente tinha a possibilidade de introduzir valores não exclusivos.

Eu procurei a existência de uma lista exclusiva de algum tipo, mas depois percebi que testar a existência do elemento antes de adicioná-lo funciona muito bem.

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

Não sei se existem advertências para essa abordagem simples, mas isso resolve meu problema.