Python «set» с повторяющимися/повторяющимися элементами

Question

Существует ли стандартный способ представления «набора», который может содержать повторяющиеся элементы.

Как я понимаю, набор имеет ровно один или ноль элемента. Я хочу, чтобы функциональность имела любое число.

В настоящее время я использую словарь с элементами как ключами и количеством в качестве значений, но по многим причинам это кажется неправильным.

Мотивация: Я считаю, что существует множество приложений для такой коллекции. Например, обзор любимых цветов может быть представлен: survey = ['blue', 'red', 'blue', 'green']

Здесь я не забочусь о заказе, но я делаю о количествах. Я хочу сделать что-то вроде:

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

... и, возможно, даже

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

Примечания: Да, установить не правильный термин для такого рода коллекции. Есть ли более правильный?

Список курсов будет работать, но требуемая коллекция неупорядочена. Не говоря уже о том, что метод, названный для наборов, кажется мне более подходящим.

Answer 1

Вы ищете multiset.

ближайший тип данных Python является collections.Counter:

Counter является dict подкласс для подсчета hashable объектов. Это неупорядоченная коллекция , где элементы хранятся в виде словарных ключей, а - их значения хранятся в виде значений словаря. Графам разрешено быть любое целочисленное значение, включая нулевые или отрицательные значения. Counter класс похож на мешки или мультимножители на других языках.

Для фактической реализации мультимножества, используйте bag класс из пакета структур данных на PyPI. Обратите внимание, что это только для Python 3. Если вам нужен Python 2, here является рецептом для bag, написанного для Python 2.4.

Answer 2

Ваш подход с dict с элементом/count кажется мне удобным. Вероятно, вам нужна еще одна функциональность. Посмотрите на collections.Counter.

• O (1) Тест на элемент, является ли настоящее и текущее значение счетчика поиска (быстрее, чем с element in list и list.count(element))
• counter.elements() выглядит как список со всеми дублирует
• простой манипуляции с накидной/разница с другими Счетчики

Answer 3

Если вам нужны дубликаты, используйте список и преобразуйте его в набор, когда вам нужно работать как набор.

Answer 4

Вы можете использовать простой list и использовать list.count(element) всякий раз, когда вы хотите получить доступ к «количеству» элементов.

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

my_list.count(1) # will return 2 

Answer 5

В альтернативной реализации мультисайта Python используется структура данных отсортированного списка. В PyPI есть несколько реализаций. Одним из вариантов является модуль sortedcontainers, который реализует тип данных SortedList, который эффективно реализует подобные методу, такие как add, remove и contains. Модуль sortedcontainers реализован в версиях pure-Python, fast-as-C (даже быстрее), имеет 100% -ный охват тестирования и часы стресс-тестирования.

Установка проста в PyPI:

pip install sortedcontainers 

Если вы не pip install можете просто вытащить sortedlist.py файл вниз от open-source repository.

Используйте его, как вы бы набор:

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

Модуль sortedcontainers также поддерживает performance comparison с другими популярными реализациями.

Answer 6

Что вы ищете действительно multiset (или мешок), коллекция не обязательно различных элементов (в то время как набор не содержит дубликатов).

Здесь реализована реализация для мультимножителей: https://github.com/mlenzen/collections-extended (модуль Pypy's collections extended).

Структура данных для мультимножеств называется bag. A bag является подклассом класса Set от модуля collections с дополнительным словарем для отслеживания кратности элементов.

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) 

Хороший метод bag является nlargest (аналогичен Counter для списков), который возвращает кратности всех элементов сверхбыстрых, так как число вхождений каждого элемента хранятся уточненным в словаре мешка :

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