sets — Неупорядоченные коллекции уникальных элементов

Модуль sets предоставляет классы для создания и обработки неупорядоченных коллекций уникальных элементов. Общие применения включают проверку принадлежности, удаление дубликатов из последовательности и вычисление стандартных математических операций над множествами, таких как пересечение, объединение, разность и симметрическая разность.

Как и другие коллекции, множества поддерживают x in set, len(set), и for x in set. Будучи неупорядоченной коллекцией, множества не записывают позицию элемента или порядок вставки. Соответственно, множества не поддерживают индексирование, срезы или другие последовательностные операции.

Большинство применений множеств используют класс Set, который предоставляет все методы множества, кроме __hash__(). Для расширенных применений, требующих метода хеширования, класс ImmutableSet добавляет метод __hash__(), но опускает методы, изменяющие содержимое множества. Оба класса Set и ImmutableSet наследуются от BaseSet, абстрактного класса, полезного для определения, является ли объект множеством: isinstance(obj, BaseSet).

Классы множеств реализованы с использованием словарей. Соответственно, требования к элементам множества такие же, как и к ключам словарей; а именно, элемент должен определять как __eq__(), так и __hash__(). В результате, множества не могут содержать изменяемые элементы, такие как списки или словари. Однако они могут содержать неизменяемые коллекции, такие как кортежи или экземпляры ImmutableSet. Для удобства в реализации множеств множеств внутренние множества автоматически преобразуются в неизменяемую форму, например, Set([Set(['dog'])]) преобразуется в Set([ImmutableSet(['dog'])]).

class sets.Set([iterable])

Создает новый пустой объект Set. Если параметр iterable указан, обновляет множество элементами, полученными из итерации. Все элементы в iterable должны быть неизменяемыми или преобразуемы в неизменяемые с использованием протокола, описанного в разделе Протокол автоматического преобразования в неизменяемую форму.

class sets.ImmutableSet([iterable])

Создает новый пустой объект ImmutableSet. Если параметр iterable указан, обновляет множество элементами, полученными из итерации. Все элементы в iterable должны быть неизменяемыми или преобразуемы в неизменяемые с использованием протокола, описанного в разделе Протокол автоматического преобразования в неизменяемую форму.

Поскольку объекты ImmutableSet предоставляют метод __hash__(), они могут использоваться в качестве элементов множества или ключей словаря. Объекты ImmutableSet не имеют методов добавления или удаления элементов, поэтому все элементы должны быть известны при вызове конструктора.

1. Объекты множеств

Экземпляры Set и ImmutableSet оба поддерживают следующие операции:

Обратите внимание, что неоператорные версии union(), intersection(), difference(), и symmetric_difference() принимают в качестве аргумента любую итерируемую последовательность. В отличие от них, их операторные аналоги требуют, чтобы их аргументы были множествами. Это предотвращает такие склонные к ошибкам конструкции, как Set('abc') & 'cbs' в пользу более удобочитаемых Set('abc').intersection('cbs').

Кроме того, оба Set и ImmutableSet поддерживают сравнения множеств с множествами. Два множества равны тогда и только тогда, когда каждый элемент каждого множества содержится в другом (каждое является подмножеством другого). Множество меньше другого множества тогда и только тогда, когда первое множество является собственным подмножеством второго множества (является подмножеством, но не равно). Множество больше другого множества тогда и только тогда, когда первое множество является собственным надмножеством второго множества (является надмножеством, но не равно).

Сравнения подмножества и равенства не обобщаются на полную функцию упорядочения. Например, любые два непересекающихся множества не равны и не являются подмножествами друг друга, поэтому *все* из следующего возвращают False: a<b, a==b, или a>b. Соответственно, множества не реализуют метод __cmp__().

Поскольку множества определяют только частичное упорядочение (отношения подмножества), результат метода list.sort() неопределен для списков множеств.

В следующей таблице перечислены операции, доступные в ImmutableSet, но отсутствующие в Set:

В следующей таблице перечислены операции, доступные в Set, но отсутствующие в ImmutableSet:

Обратите внимание, что неоператорные версии update(), intersection_update(), difference_update(), и symmetric_difference_update() будут принимать любой итерируемый объект в качестве аргумента.

Также обратите внимание, что модуль также включает метод union_update(), который является псевдонимом для update(). Этот метод включён для обратной совместимости. Программисты должны предпочитать метод update(), так как он поддерживается встроенными типами set() и frozenset().

2. Пример

>>> from sets import Set
>>> engineers = Set(['John', 'Jane', 'Jack', 'Janice'])
>>> programmers = Set(['Jack', 'Sam', 'Susan', 'Janice'])
>>> managers = Set(['Jane', 'Jack', 'Susan', 'Zack'])
>>> employees = engineers | programmers | managers           # union
>>> engineering_management = engineers & managers            # intersection
>>> fulltime_management = managers - engineers - programmers # difference
>>> engineers.add('Marvin')                                  # add element
>>> print engineers # doctest: +SKIP
Set(['Jane', 'Marvin', 'Janice', 'John', 'Jack'])
>>> employees.issuperset(engineers)     # superset test
False
>>> employees.update(engineers)         # update from another set
>>> employees.issuperset(engineers)
True
>>> for group in [engineers, programmers, managers, employees]: # doctest: +SKIP
...     group.discard('Susan')          # unconditionally remove element
...     print group
...
Set(['Jane', 'Marvin', 'Janice', 'John', 'Jack'])
Set(['Janice', 'Jack', 'Sam'])
Set(['Jane', 'Zack', 'Jack'])
Set(['Jack', 'Sam', 'Jane', 'Marvin', 'Janice', 'John', 'Zack'])

3. Протокол автоматического преобразования в неизменяемый тип

Множества могут содержать только неизменяемые элементы. Для удобства, изменяемые объекты Set автоматически копируются в ImmutableSet перед добавлением в качестве элемента множества.

Механизм заключается в добавлении всегда хэшируемого элемента, или если элемент не хэшируем, проверяется, есть ли у него метод __as_immutable__(), который возвращает неизменяемый эквивалент.

Поскольку объекты Set имеют метод __as_immutable__(), возвращающий экземпляр ImmutableSet, можно создавать множества множеств.

Аналогичный механизм необходим для методов __contains__() и remove(), которые требуют хэширования элемента для проверки принадлежности к множеству. Эти методы проверяют элемент на хэшируемость и, если нет, проверяют наличие метода __as_temporarily_immutable__(), который возвращает элемент, обернутый классом, предоставляющим временные методы для __hash__(), __eq__() и __ne__().

Альтернативный механизм позволяет избежать необходимости создания отдельной копии исходного изменяемого объекта.

Объекты Set реализуют метод __as_temporarily_immutable__(), который возвращает объект Set, обернутый новым классом _TemporarilyImmutableSet.

Оба механизма, обеспечивающие хэшируемость, обычно незаметны пользователю; однако, может возникнуть конфликт в многопоточной среде, когда один поток обновляет множество, а другой временно обернул его в _TemporarilyImmutableSet. Другими словами, множества изменяемых множеств не являются потокобезопасными.

4. Сравнение со встроенными типами множеств

Встроенные типы set и frozenset были разработаны на основе опыта использования модуля sets. Ключевые отличия заключаются в следующем:

• Set и ImmutableSet были переименованы в set и frozenset.
• Нет аналога для BaseSet. Используйте isinstance(x, (set, frozenset)).
• Алгоритм хэширования встроенных типов работает значительно лучше (меньше коллизий) для большинства наборов данных.
• Встроенные версии имеют более эффективные (по объёму) pickle.
• Встроенные версии не имеют метода union_update(). Используйте метод update(), который эквивалентен.
• Встроенные версии не имеют метода _repr(sorted=True). Используйте встроенные функции repr() и sorted(): repr(sorted(s)).
• Встроенная версия не имеет протокола автоматического преобразования в неизменяемый тип. Многие сочли эту функцию запутанной, и никто из сообщества не сообщил о реальных случаях её использования.