Python "set" z powtarzającymi się/powtarzanymi elementami

Question

Czy istnieje standardowy sposób reprezentowania "zestawu", który może zawierać zduplikowane elementy.

Jak rozumiem, zestaw ma dokładnie jeden lub zero elementu. Chcę funkcjonalność mieć dowolną liczbę.

Obecnie używam słownika z elementami jako kluczami i ilością jako wartościami, ale wydaje się to błędne z wielu powodów.

Motywacja:Wierzę, że istnieje wiele aplikacji do takiej kolekcji. Na przykład ankieta dotycząca ulubionych kolorów może być reprezentowana przez: ankieta = ["niebieski", "czerwony", "niebieski", "zielony"]

Tutaj nie obchodzi mnie zamówienie, ale robię o ilościach. Chcę robić takie rzeczy jak:

survey.add('blue') 
# would give survey == ['blue', 'red', 'blue', 'green', 'blue'] 

... a może nawet

survey.remove('blue') 
# would give survey == ['blue', 'red', 'green'] 

Uwagi: Tak ustaw nie jest prawidłowe określenie dla tego rodzaju kolekcji. Czy jest bardziej poprawny?

Lista kursów będzie działać, ale wymagana kolekcja jest nieuporządkowana. Nie wspominając już o tym, że metoda nazywania zestawów wydaje mi się bardziej odpowiednia.

Answer 1

Szukasz multiset.

najbliżej typ danych Pythona jest collections.Counter:

Counter jest dict podklasa liczenia hashable obiektów. Jest to kolekcja nieuporządkowana , w której elementy są zapisywane jako klucze słownika i ich wartości są zapisywane jako wartości słownikowe. Liczby mogą być dowolną liczbą całkowitą zawierającą zero lub ujemną liczbę. Ta klasa Counter jest podobna do toreb lub wielosekcyjnych w innych językach.

Dla rzeczywistej implementacji MultiSet, użyć klasy bag z pakietu struktur danych na PyPI. Zauważ, że dotyczy to tylko Pythona 3. Jeśli potrzebujesz Python 2, here to przepis na bag napisany dla Pythona 2.4.

Answer 2

Twoje podejście do dyktowania z elementem/count wydaje mi się ok. Prawdopodobnie potrzebujesz więcej funkcji. Spójrz na collections.Counter.

• O (1) sprawdzenie, czy element jest obecny i prądu pobierania Ilość (szybciej niż element in list i list.count(element))
• counter.elements() wygląda listę wszystkich powiela
• łatwe manipulowanie Union/różnica z innymi licznikami

Answer 3

Jeśli potrzebujesz duplikatów, użyj listy i przekształć ją w zestaw, gdy potrzebujesz działać jako zestaw.

Answer 4

Możesz użyć zwykłego list i używać list.count(element), gdy chcesz uzyskać dostęp do "liczby" elementów.

my_list = [1, 1, 2, 3, 3, 3] 

my_list.count(1) # will return 2 

Answer 5

Alternatywna implementacja multiset Python wykorzystuje posortowaną strukturę danych list. W PyPI jest kilka implementacji. Jedną z opcji jest moduł sortedcontainers, który implementuje typ danych typu SortedList, który wydajnie implementuje podobne do zestawu metody, takie jak add, remove i contains. Moduł sortedcontainers jest zaimplementowany w czysto-Python, implementacjach szybkich as-C (jeszcze szybciej), ma 100% pokrycia testem jednostkowym i godziny testów obciążeniowych.

Instalacja jest łatwa z PyPI:

pip install sortedcontainers 

Jeśli nie pip install można po prostu wyciągnąć plik sortedlist.py dół od open-source repository.

Używaj go jak byś zestawie:

from sortedcontainers import SortedList 
survey = SortedList(['blue', 'red', 'blue', 'green']] 
survey.add('blue') 
print survey.count('blue') # "3" 
survey.remove('blue') 

Moduł sortedcontainers utrzymuje również performance comparison z innych popularnych implementacji.

Answer 6

Co szukasz jest rzeczywiście multiset (lub torba), zbiór niekoniecznie odrębnych elementów (podczas gdy ustawić nie zawiera duplikaty).

Istnieje implementacja dla multiset tutaj: https://github.com/mlenzen/collections-extended (moduł Pypy collections extended).

Struktura danych dla multisetów nazywa się bag. A bag to podklasa klasy Set z modułu collections z dodatkowym słownikiem do śledzenia wielu elementów.

class _basebag(Set): 
    """ 
    Base class for bag and frozenbag. Is not mutable and not hashable, so there's 
    no reason to use this instead of either bag or frozenbag. 
    """ 
    # Basic object methods 

    def __init__(self, iterable=None): 
     """Create a new basebag. 

     If iterable isn't given, is None or is empty then the bag starts empty. 
     Otherwise each element from iterable will be added to the bag 
     however many times it appears. 

     This runs in O(len(iterable)) 
     """ 
     self._dict = dict() 
     self._size = 0 
     if iterable: 
      if isinstance(iterable, _basebag): 
       for elem, count in iterable._dict.items(): 
        self._inc(elem, count) 
      else: 
       for value in iterable: 
        self._inc(value) 

Miła metoda bag jest nlargest (podobny do Counter na listach), która zwraca krotności wszystkich elementów niesamowicie szybka, ponieważ liczba wystąpień każdego elementu utrzymuje się na bieżąco w słownika torby :

>>> b=bag(random.choice(string.ascii_letters) for x in xrange(10)) 
>>> b.nlargest() 
[('p', 2), ('A', 1), ('d', 1), ('m', 1), ('J', 1), ('M', 1), ('l', 1), ('n', 1), ('W', 1)] 
>>> Counter(b) 
Counter({'p': 2, 'A': 1, 'd': 1, 'm': 1, 'J': 1, 'M': 1, 'l': 1, 'n': 1, 'W': 1})