Czy Python ma uporządkowany zestaw?

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

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

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__

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

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

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:

• zestaw uporządkowany (oparty na języku Python)
• uporządkowany (oparty na Cython)
• rozszerzone kolekcje
• oset (ostatnia aktualizacja w 2012 r.)

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

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.

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

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

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

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.

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

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.

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.