Czy Python ma uporządkowany zestaw?

477

Python ma uporządkowany słownik . Co z zamówionym zestawem?

Casebash
źródło
18
a co z rozmową, torbą rzeczy? (nieuporządkowane i nie unikalne)
wim
19
@ wim collections.Counterto torba Pythona.
trzęsienie ziemi
1
Co jeśli coś zostanie dodane dwukrotnie? Jaka powinna być pozycja?
McKay
2
@McKay - jeśli miałby podążać za zachowaniem kolekcji.OrderDict nadal byłby w pozycji początkowego dodania
wojtow

Odpowiedzi:

206

Istnieje przepis na ten zestaw (możliwy nowy link ), do którego odwołuje się Dokumentacja Python 2 . Działa to na Py2.6 lub nowszym i 3.0 lub nowszym bez żadnych modyfikacji. Interfejs jest prawie dokładnie taki sam jak normalny zestaw, z tym wyjątkiem, że inicjalizacja powinna odbywać się za pomocą listy.

OrderedSet([1, 2, 3])

Jest to MutableSet, więc podpis dla .unionzestawu nie pasuje do zestawu, ale ponieważ zawiera __or__coś podobnego, można go łatwo dodać:

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

def union(self, *sets):
    for set in sets:
        self |= set
Casebash
źródło
6
Wybrałem własną odpowiedź, ponieważ odniesienie z dokumentacji zbliża się do oficjalnej odpowiedzi
Casebash
49
Interfejs nie jest dokładnie taka sama jak zwykłego zestawu obiektów, wiele istotnych metod brakuje, takie jak update, union, intersection.
xApple
5
FYI, zauważyłem, że lekko zmodyfikowana wersja tego przepisu przytoczonego w tej odpowiedzi został dodany do PyPI jako „uporządkowany-set”
Geoffrey Hing
7
Jestem pewien, że nie możesz mieć dwóch metod wywoływanych unionw tej samej klasie. Ostatni wygra, a pierwszy nie będzie istniał w czasie wykonywania. Wynika to z faktu, że OrderedSet.union(bez parens) musi odnosić się do pojedynczego obiektu.
Kevin
3
Istnieje również pakiet „uporządkowany” oparty na tej samej recepturze, ale zaimplementowany w Cython - pypi.python.org/pypi/orderedset .
mbdevpl
149

Uporządkowany zestaw jest funkcjonalnie specjalnym przypadkiem uporządkowanego słownika.

Klucze słownika są unikalne. Zatem jeśli pominiemy wartości w uporządkowanym słowniku (np. Poprzez przypisanie ich None), wówczas mamy zasadniczo uporządkowany zestaw.

Od wersji Python 3.1 istnieje collections.OrderedDict. Poniżej znajduje się przykładowa implementacja zestawu OrdersSet. (Należy pamiętać, że tylko kilka metod wymaga zdefiniowania lub zastąpienia: collections.OrderedDicti collections.MutableSetwykonaj ciężkie podnoszenie).

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
źródło
1
@Casebash: tak, może chcieć zdefiniować klasę OrderedSetktóra podklasy OrderedDicti abc.Set, a następnie określić __len__, __iter__i __contains__.
Stephan202
1
@ Stephan202: Niestety kolekcja ABC żyje collections, ale poza tym dobra sugestia
u0b34a0f6ae
4
To prawda, ale w rezultacie masz dużo zmarnowanej przestrzeni, co prowadzi do nieoptymalnej wydajności.
Daniel Kats
3
Dodatek; collectors.OrDERDict jest również dostępny w Pythonie 2.7.
Nurbldoff,
2
Wykonanie OrderedSet([1,2,3])podnosi błąd typu. Jak działa nawet konstruktor? Brak przykładu użycia.
xApple
90

Odpowiedź brzmi: nie, ale możesz używać collections.OrderedDictstandardowej biblioteki Pythona tylko z kluczami (i wartościami as None) do tego samego celu.

Aktualizacja : jak Pythona i CPython 3,7 (3,6) standardowe dictjest zagwarantowane zachowanie kolejności i jest bardziej wydajnych niż OrderedDict. (W celu zachowania kompatybilności wstecznej, a zwłaszcza czytelności, możesz nadal używać OrderedDict.)

Oto przykład użycia dictzestawu uporządkowanego do odfiltrowywania zduplikowanych elementów przy zachowaniu kolejności, a tym samym emulacji zestawu uporządkowanego. Użyj dictmetody klasy, fromkeys()aby utworzyć dykt, a następnie po prostu poproś o keys()poparcie.

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

>>> list(dict.fromkeys(keywords))
['foo', 'bar', 'baz']
jrc
źródło
4
Może warto wspomnieć, że działa to również (szybciej) z wanilią dict.fromkeys(). Ale w takim przypadku kolejność kluczy jest zachowywana tylko w implementacjach CPython 3.6+, więc OrderedDictjest to bardziej przenośne rozwiązanie, gdy liczy się kolejność.
jez
1
nie będzie działać, jeśli wartości nie będą ciągami
Anwar Hossain
4
@AnwarHossain keys = (1,2,3,1,2,1) list(OrderedDict.fromkeys(keys).keys())-> [1, 2, 3], python-3.7. To działa.
raratiru
1
Czy możemy wywnioskować, że zestaw w Pythonie 3.7+ również zachowuje porządek?
user474491,
2
@ user474491 przeciwieństwie dict, setw Pythonie 3.7+ niestety nie zachować porządek.
cz
39

Mogę zrobić ci jeden lepiej niż OrderedSet: Boltons ma czystej Python, 2/3-kompatybilny IndexedSettyp , który jest nie tylko zamówił zestaw, ale również wspiera indeksowanie (zgodnie z listą).

Po prostu pip install boltons(lub skopiuj setutils.pydo bazy kodu) zaimportuj IndexedSeti:

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

Wszystko jest wyjątkowe i zachowane w porządku. Pełne ujawnienie: Napisałem IndexedSet, ale oznacza to również, że możesz mnie popsuć, jeśli są jakieś problemy . :)

Mahmoud Hashemi
źródło
39

Wdrożenia dotyczące PyPI

Podczas gdy inni zwracali uwagę, że w Pythonie nie ma jeszcze wbudowanej implementacji zestawu zachowywania kolejności wstawiania, mam wrażenie, że w tym pytaniu brakuje odpowiedzi określającej, co można znaleźć w PyPI .

Istnieją pakiety:

Niektóre z tych implementacji oparte są na przepisie opublikowanym przez Raymonda Hettingera w ActiveState, o którym wspomniano również w innych odpowiedziach tutaj.

Niektóre różnice

  • zestaw zamówiony (wersja 1.1)
    • zaleta: O (1) dla wyszukiwań według indeksu (np. my_set[5])
  • oset (wersja 0.1.3)
    • korzyść: O (1) dla remove(item)
    • wada: najwyraźniej O (n) dla wyszukiwań według indeksu

Obie implementacje mają O (1) dla add(item)i __contains__(item)( item in my_set).

Daniel K.
źródło
2
Nowym pretendentem jest collections_extended.setlist . Funkcje takie jak set.unionna nim nie działają, mimo że dziedziczy collections.abc.Set.
timdiels
3
OrderedSetteraz obsługujeremove
warvariuc
17

Jeśli używasz uporządkowanego zestawu do utrzymania posortowanego porządku, rozważ użycie implementacji posortowanego zestawu z PyPI. Sortedcontainers moduł dostarcza SortedSet tylko dla tego celu. Niektóre korzyści: czysto Python, implementacje fast-as-C, 100% pokrycie testami jednostkowymi, godziny testów warunków skrajnych.

Instalacja z PyPI jest łatwa dzięki pip:

pip install sortedcontainers

Zauważ, że jeśli nie możesz pip install, po prostu ściągnij pliki sortedlist.py i sortedset.py z repozytorium open source .

Po zainstalowaniu możesz po prostu:

from sortedcontainers import SortedSet
help(SortedSet)

Moduł sortedcontainers utrzymuje również porównanie wydajności z kilkoma alternatywnymi implementacjami.

W przypadku komentarza dotyczącego typu danych worka Pythona istnieje alternatywnie typ danych SortedList, którego można użyć do wydajnej implementacji worka.

GrantJ
źródło
Zauważ, że SortedSetklasa tam wymaga, aby członkowie byli porównywalni i dali się mieszać.
gsnedders
4
@gsnedders przy pomocy poleceń wbudowanych seti frozensetwymagają również elementy, które należy hashable. Porównywalne ograniczenie jest dodatkiem SortedSet, ale jest również oczywistym ograniczeniem.
gotgenes
2
Jak sama nazwa wskazuje, nie zachowuje to porządku. To nic innego jak posortowane (set ([sekwencja])), co czyni lepiej?
ldmtwo,
@ldmtwo Nie jestem pewien, o którym mówisz, ale dla jasności, SortedSet jako część Sorted Containers utrzymuje posortowaną kolejność.
GrantJ,
2
@GrantJ - Jest to różnica między tym, czy zachowuje porządek wstawiania , czy porządek sortowania . Większość innych odpowiedzi dotyczy kolejności wprowadzania. Myślę, że już wiesz o tym na podstawie pierwszego zdania, ale prawdopodobnie tak mówi ldmtwo.
Justin,
8

W przypadku, gdy już używasz pand w swoim kodzie, jego Indexobiekt zachowuje się jak uporządkowany zestaw, jak pokazano w tym artykule .

Przykłady z artykułu:

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
źródło
Czy możesz podać przykład w tej odpowiedzi? Linki po pewnym czasie ulegają zerwaniu.
Alechan
1
dla różnicy między zestawami, faktycznie musisz użyć indA.difference(indB), znak minus wykonuje standardowe odejmowanie
gg349
7

Trochę późno do gry, ale pisałem klasę setlistjako element collections-extended, który w pełni zarówno narzędzi SequenceiSet

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

Dokumentacja: http://collections-extended.lenzm.net/en/latest/

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

Michael Lenzen
źródło
7

Nie ma OrderedSetw oficjalnej bibliotece. Przygotowuję wyczerpujący ściąg wszystkich struktur danych w celach informacyjnych.

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']
}
Rachunek różniczkowy
źródło
3

ParallelRegression pakiet dostarcza setlista () uporządkowanym zbiorem klasy, która jest więcej niż metoda uzupełniania opcji w oparciu o receptury ActiveState. Obsługuje wszystkie metody dostępne dla list i większość, jeśli nie wszystkie metody dostępne dla zestawów.

RichardB
źródło
2

Jak wspomniano w innych odpowiedziach, tak jak w Pythonie 3.7+, dykt jest uporządkowany z definicji. Zamiast podklasowania OrderedDictmożemy dokonać podklasy abc.collections.MutableSetlub typing.MutableSetużyć kluczy dykta do przechowywania naszych wartości.

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

Więc po prostu:

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

Umieszczam ten kod w małej bibliotece , aby każdy mógł to pip installzrobić.

paskudny
źródło
-4

Do wielu celów wystarczy po prostu posortowanie sortowane. Na przykład

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

Jeśli zamierzasz używać tego wielokrotnie, powstanie narzut związany z wywołaniem posortowanej funkcji, więc możesz chcieć zapisać wynikową listę, dopóki skończysz zmieniać zestaw. Jeśli chcesz zachować unikalne elementy i posortować, zgadzam się z sugestią użycia OrdersDict ze zbiorów o dowolnej wartości, takich jak None.

hwrd
źródło
43
Celem OrDERSet jest możliwość uzyskania elementów w kolejności, w jakiej zostały dodane do zestawu. Przykładem może być o nazwie SortedSet ...
Konserwacja okresowa
-4

Miałem też małą listę, na której wyraźnie miałem możliwość wprowadzenia wartości nieunikalnych.

Szukałem istnienia jakiejś unikalnej listy, ale potem zdałem sobie sprawę, że testowanie istnienia elementu przed dodaniem go działa dobrze.

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

Nie wiem, czy istnieją pewne zastrzeżenia do tego prostego podejścia, ale to rozwiązuje mój problem.

Loïc N.
źródło
Głównym problemem związanym z tym podejściem jest to, że dodawanie przebiega w O (n). Oznacza to, że robi się wolniej z dużymi listami. Wbudowane zestawy Pythona bardzo dobrze przyspieszają dodawanie elementów. Ale w przypadku prostych przypadków użycia z pewnością działa!
Draconis,