Полное руководство по множествам в Python

Класс set является одной из ключевых структур данных в Python. Это неупорядоченная коллекция элементов без дубликатов. В определенной степени он представляет собой математическое множество, и многие из часто используемых математических операций для множеств существуют в Python. Часто операции для множеств выполняются гораздо быстрее, чем альтернативные операции со списками, поэтому для написания эффективного кода множества необходимы. В этой статье я расскажу об особенностях класса множеств. Давайте приступим к этому.

Инициализация

В Python существует два способа создания объекта множества: использование set(iterable) или помещение элементов, разделенных запятой, внутрь фигурных скобок { ... }. Исключением является случай, когда фигурные скобки пусты, т.е. {}, тогда будет создан словарь, а не пустое множество. Для пустого множества используйте set(). Обратите внимание, что порядок элементов не имеет значения, а дубликаты будут удалены.

a = { "a", "b", "c", "d", "e", "f", "f" }
# any iterable to the set constructor
b = set(["a", "b", "c", "d", "e", "f"])
c = set(("a", "b", "c", "d", "e", "e", "f", "f"))
# order does not matter
d = set(["d", "e", "f", "a", "b", "c"])
# destructuring list
e = { *["a", "b", "c", "d", "e", "f"] }
assert a == b == c == d == e

# different types can be stored in the same set
f = set(["a", True, 123])
g = { "a", True, 123, True, 123 }
assert f == g

# set() is a set, {} is a dictionary
assert set() != {}

Какие элементы могут быть включены в множество? Ответ: только объекты типа immutable* . К ним относятся такие типы, как float, int, string, bool и т.д. В отличие от изменяемых типов, таких как списки, словари и сами множества. Если вы хотите узнать больше о различных типах переменных в Python, я рекомендую прочитать эту статью . Таким образом, следующие действия приведут к ошибке:

{ ["a", "b", "c"], True }
# => TypeError: unhashable type: 'list'

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

*Замечание о неизменности

Изменяемость является ограничением только для встроенных типов. Практически, объект должен быть hashable только для того, чтобы быть вставленным в набор или быть ключом в словаре. По умолчанию пользовательские классы имеют хэш, основанный на их id, и равенство определяется по их id. Это означает, что два объекта, которые равны по своим атрибутам, не равны при проверке на равенство, если только они не являются одним и тем же объектом или если не определен пользовательский оператор __eq__.

Если определен пользовательский оператор __eq__, то они больше не хэшируются , если только не определен пользовательский оператор . Здесь важно, что если два объекта равны, то их хэши также должны быть равны. В противном случае возникнут проблемы при добавлении объекта в словарь или набор, так как при проверке существования в ключах словарей и наборах проверяется и хэш-значение, и равенство __hash__

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

Добавление элементов

Существует несколько способов добавления элементов к множеству. Чтобы мутировать множество, вы добавляете отдельные элементы с помощью .add() и итерации с помощью .update() или эквивалентно |=:

a = set()
# adding a string element
a.add("hello")
# The following does NOT do the same thing.
# Update expects an iterable and so
# the string is seen as an iterable of characters
# that are all added
a.update("hello")
assert a == { 'hello', 'h', 'e', 'l', 'o' }
# here two strings are added since they are in a list
a.update(["hi", "world"])
assert a == { 'hello', 'h', 'e', 'l', 'o', "hi", "world" }

Под словом mutate я подразумеваю изменение исходного объекта. Вы также можете добавлять элементы, которые не будут изменять исходный набор. Это можно сделать с помощью union() или эквивалентно с помощью | :

a = { "a", "b" , "c" }
b = { "a", "c", "d" }

assert a | b == a.union(b) == { "a", "b", "c", "d" }
# original objects are unchanged
assert a == { "a", "b" , "c" } and b == { "a", "c", "d" }

Четкая разница в поведении между использованием .update() и .union() может быть показана на следующем примере:

def add_to_set1(a, b):
    a.update(b)
    return a

def add_to_set2(a, b):
    a = a.union(b)
    return a

a = { "a", "b" , "c" }
b = { "a", "c", "d" }

# the original object has been modified
# and will be equal to the returned object
assert a == add_to_set1(a, b)

a = { "a", "b" , "c" }
b = { "a", "c", "d" }

# the original object has NOT been modified
# and will not be equal to the returned object
assert a != add_to_set2(a, b)

Наконец, вы также можете объединить два набора с помощью деструктуризации:

a = { "a", "b" , "c" }
b = { "a", "c", "d" }
assert { *a, *b } == { "a", "b", "c", "d" }

Это будет работать как union(), но я бы рекомендовал union() вместо него.

Обратите внимание, в приведенных выше примерах я использовал .update(), но вы также можете использовать |= . Это означает, что a |= b ( .update() ) - это НЕ то же самое, что a = a | b (.union()), поскольку первое мутирует объект в a, а второе присваивает новое значение a.

Удаление элементов

Как и для добавления элементов, существуют эквивалентные операции для удаления элементов. Ниже я покажу вам соответствующий оператор удаления для ранее показанных операторов добавления:

• .add() это .remove()
• .update() - это .difference_update() или -=
• .union() это .difference() или -

Примеры:

a = { "a", "b" , "c" }
a.remove("b")
assert a == { "a", "c" }

a = { "a", "b" , "c" } 
# just like .update() it expects an iterable
# thus, here "a" and "b" is removed as opposed
# to the entire string "ab"
a.difference_update("ab")
assert a == { "c" }

a = { "a", "b" , "c" } 
a.difference_update(["ab"])
# "ab" doesn't exist in set, nothing was removed
assert a == { "a", "b", "c" }

# - or equivalently difference
# does not modify original object
a = { "a", "b" , "c" } 
b = a - { "b", "c" }
assert a != b and b == { "a" }

Опять же, помните о разнице между a -= b (мутирует) и a = a — b (не мутирует).

Есть также несколько других полезных методов удаления:

• .clear() удалит все элементы в списке.
• В то время как .remove() удаляет элемент только если он существует (иначе выдает ошибку), .discard() просто ничего не делает, если элемент не существует.
• .pop() удалит и вернет случайный элемент из множества.

Другие модифицирующие операции

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

Пересечение

Пересечение двух множеств - это множество элементов, которые входят в оба множества. Операторами для него являются:

• Не мутирующие: .intersection() или &, т.е. a.intersection(b) или a & b
• Мутирующие: .intersection_update или &=

Пример:

a = { "a", "b", "c" }
b = { "b", "c", "d" }
assert a & b == { "b", "c" }

Симметричная разность или дизъюнктивное объединение

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

• Немутирующий: .symmmetric_difference() или ^ , т. е. a.symmmetric_difference(b) или a ^ b
• Мутирование: .symmetric_difference_update() или ^=

a = { "a", "b", "c" }
b = { "b", "c", "d" }
assert a ^ b == { "a", "d" }

Методы сравнения

Я показал вам, как изменять множества, но то, для чего в основном используются множества - это изучение того, какие элементы находятся внутри них, а какие нет быстро, что в противном случае было бы медленнее со списками. Давайте посмотрим, какие операции могут это сделать.

Проверить существование в множестве

Это, скорее всего, та операция, которую вы чаще всего будете выполнять с множествами. Для этого используется оператор in для проверки существования элемента или not in для проверки несуществования элемента. В отличие от поиска элемента в списке, временная сложность постоянна, O(1). То есть, даже по мере добавления все новых и новых элементов операции будут выполняться так же быстро.

a = { "a", "b", "c" }
assert "a" in a
assert "d" not in a

Проверить, является ли одно множество подмножеством другого

Множество является подмножеством другого множества, если все элементы первого множества существуют во втором множестве. Например, (A, B, C) является подмножеством (A, B, C, D). В Python это можно проверить с помощью .issubset или <=. Чтобы проверить, является ли одно множество правильным подмножеством другого, то есть является ли оно подмножеством и не равны ли они, можно использовать < . Но обратите внимание, что вы также можете использовать >=, > .

a = { "a", "b", "c" }
b = { "a", "b" }
assert a.issubset(b) == (a <= b) == False
assert b.issubset(a) == (b <= a) == True
# it is a subset of itself but not a proper subset of itself
assert a.issubset(a) == (a <= a) and not a < a
# changing direction
assert a >= b and a > b

Проверить, нет ли у множества общих элементов

Если множества не имеют общих элементов, они называются disjoint, и в Python это можно вычислить с помощью .isdisjoint() .

a = { "a", "b", "c" }
b = { "a", "b" }
c = { "d" }
# without isdisjoint()
assert len(a & c) == 0 and len(a & b) != 0
# with it
assert a.isdisjoint(c) and not a.isdisjoint(b)

Устанавливает понимание

Как и в случае со списками и словарями, вы можете использовать понимание.  Это делается путем добавления выражения понимания внутри фигурных скобок и возврата одного изменяемого элемента в каждом цикле: { <element> for ... in ... }. Примеры:

# turning a list into sets while adding 1 to each element
assert { i+1 for i in [1, 2, 3, 4] } == { 2, 3, 4, 5 }

# only even numbers
a = { i for i in range(10) if i % 2 == 0 }
a.update({ -3, 100 })
# Turning a set into a list and adding 1
# NOTE: do not assume the order of insertion will be 
# preserved when looping over sets
print([i+1 for i in a])
# => [1, 3, 5, 101, 7, 9, -2]

Хранение более сложных типов

Представьте, что вы ходите от узла к узлу графа в отдельных итерациях. Например, допустим, вы прошли граф два раза и достигли путей:

• A -> B -> D
• D -> C -> E -> B

После этого вы захотите быстро посмотреть, прошли ли вы определенный путь, и из-за скорости поиска множество является естественным выбором. Как же это сделать, если списки нельзя вставлять, потому что они изменяемы? К счастью, в этих обстоятельствах можно использовать кортеж class, который по сути является неизменяемой версией списка. Рассмотрим пример.

Сначала я создам граф со словарем. Каждый ключ будет представлять узел, а значения будут перечислять все возможные направления из узла.

# you can go from key to values
graph = {
    "A": ["B", "D", "F"],
    "B": ["C", "F"],
    "C": ["D", "E"],
    "D": "A",
    "E": "F",
    "F": "B",
}

Это создаст следующий график:

Если вам интересно, как я создал график, то это было сделано с помощью graphviz и следующего кода:

from graphviz import Digraph

dot = Digraph()
for k in graph.keys():
    dot.node(k, k)
edges = []
for k, v in graph.items():
    edges += [f"{k}{to}" for to in v]
dot.edges(edges)
dot.render(view=True)

Теперь я буду выполнять так называемые случайные прогулки длиной 1-10, а затем хранить полученные пути в наборе в виде кортежей. Давайте посмотрим, сколько уникальных путей мы сможем сгенерировать за 100 прогулок:

import random

def perform_random_walk(graph, n_steps):
    node = random.sample(list(graph), 1)[0]
    path = [node]
    for _ in range(n_steps):
        node = random.sample(graph[node], 1)[0]
        path.append(node)
    return tuple(path)
    
paths = set()
lengths = list(range(1, 10+1))
for _ in range(100):
    paths.add(perform_random_walk(graph, random.choice(lengths)))
len(paths)
# => 83

Из 100 случайных прогулок 83 были разными.

Теперь, что если нам не важен порядок узлов, а нужно просто хранить, какие узлы были посещены? Тогда имеет смысл использовать множество, но, опять же, множества являются изменяемыми. Вместо этого мы можем использовать класс frozenset , неизменяемое множество. Давайте добавим новый цикл, чтобы сделать это:

paths = set()
lengths = list(range(1, 10+1))
for _ in range(100):
    path = perform_random_walk(graph, random.choice(lengths))
    paths.add(frozenset(path))
len(paths)
# => 21

Summary

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

Вернуться на верх