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

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

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

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

Мотивация: Я считаю, что существует множество приложений для такой коллекции. Например, обзор любимых цветов может быть представлен: 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']

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

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

Ответ 1

Вы ищете multiset.

Ближайший тип данных Python collections.Counter:

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

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

Ответ 2

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

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

Ответ 3

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

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

my_list.count(1) # will return 2

Ответ 4

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

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

pip install sortedcontainers

Если вы не можете pip install, просто вытащите файл sortedlist.py из репозитория с открытым исходным кодом.

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

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

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

Ответ 5

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

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

Структура данных для мультимножеств называется 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})

Ответ 6

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