Множества set в Python: создание и свойства

Обновлено:

Класс:

set

представляет множество.

Например:

numbers = {
    10,
    20,
    30,
}

Основные свойства set:

  • изменяемый тип данных;
  • итерируемый объект;
  • неупорядоченная коллекция;
  • содержит только уникальные элементы.

1. set основан на хеш-таблице

Как и dict, множество использует хеширование.

У словаря есть пары:

ключ → значение

Например:

{
    'name': 'Alex',
    'age': 30,
}

У set отдельных значений для ключей нет.

Он хранит сами элементы:

{
    'Python',
    'SQL',
    'Django',
}

Поэтому в очень упрощённом виде set можно представить как структуру, похожую на хеш-таблицу словаря, но где нас интересуют только сами хешируемые элементы.


Создание set

2. Множество с элементами

Используем фигурные скобки:

numbers = {
    10,
    20,
    30,
}

print(numbers)

Получим множество:

{10, 20, 30}

Но конкретный порядок элементов не следует считать гарантированным.


3. Пустой set

Так написать нельзя:

data = {}

Потому что:

{}

создаёт пустой:

dict

Проверим:

data = {}

print(
    type(data)
)

Результат:

<class 'dict'>

Чтобы создать пустое множество, необходимо вызвать:

set()

Например:

numbers = set()

print(
    type(numbers)
)

Результат:

<class 'set'>

4. Создание через класс set

В класс:

set

можно передать итерируемый объект.

Например, список:

numbers = set(
    [
        10,
        20,
        30,
    ]
)

print(numbers)

Получим множество из этих элементов.


5. Из tuple

numbers = set(
    (
        10,
        20,
        30,
    )
)

print(numbers)

6. Из строки

Строка тоже является итерируемым объектом:

letters = set(
    'python'
)

print(letters)

В множество попадут отдельные символы строки:

p
y
t
h
o
n

Конкретный порядок вывода не гарантируется.


Уникальность элементов

7. Дубликаты удаляются

Возьмём список:

numbers = [
    10,
    20,
    10,
    30,
    20,
    10,
]

Преобразуем:

unique_numbers = set(
    numbers
)

print(unique_numbers)

Получим множество:

{10, 20, 30}

Каждое значение присутствует только один раз.


8. В set не может быть двух равных элементов

Например:

numbers = {
    10,
    20,
    10,
    20,
    30,
}

В результате всё равно получим множество только из:

10
20
30

Поэтому set часто применяется, когда нужно убрать дубликаты.


Set comprehension

9. Создание множества через comprehension

Мы уже знаем:

[
    expression
    for element in iterable
]

для списка.

Для множества используются фигурные скобки:

{
    expression
    for element in iterable
}

Например:

squares = {
    number ** 2
    for number in range(1, 6)
}

print(squares)

В множество попадут:

1
4
9
16
25

10. С фильтрующим if

even_squares = {
    number ** 2
    for number in range(1, 11)
    if number % 2 == 0
}

print(even_squares)

Мы:

  1. обходим числа от 1 до 10;
  2. оставляем только чётные;
  3. возводим их в квадрат;
  4. помещаем результаты в set.

Какие объекты можно хранить в set

11. Элементы должны быть хешируемыми

Так как set построен на хешировании, его элементы должны быть:

hashable

Например:

values = {
    10,
    3.14,
    'Python',
    (10, 20),
}

Такие объекты могут находиться внутри множества.


12. Список положить в set нельзя

values = {
    [10, 20],
}

приведёт к:

TypeError: unhashable type: 'list'

То же самое:

numbers = set(
    [
        [10, 20],
        [30, 40],
    ]
)

тоже закончится:

TypeError

Потому что вложенные списки являются нехешируемыми.


13. Неизменяемость и хешируемость

На текущем этапе удобно помнить:

int
float
str
подходящий tuple

обычно можно хранить в set.

А:

list
dict
set

обычно нельзя.

Но более точное правило звучит так:

Элемент set должен быть хешируемым.

Просто «неизменяемый» и «хешируемый» — близкие, но не полностью одинаковые понятия.


Почему нужна хешируемость

14. Элементу соответствует хеш

Упрощённо:

элемент
↓
hash(element)
↓
поиск позиции в хеш-таблице

Например, когда Python проверяет:

value in numbers

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

Хеш искомого объекта помогает быстро определить, где его искать.


set неупорядочен

15. Порядок вставки не гарантируется

Например:

technologies = {
    'Python',
    'SQL',
    'Django',
    'Flask',
}

Мы записали элементы в определённом порядке.

Но при:

print(technologies)

не следует рассчитывать, что Python обязательно покажет:

Python
SQL
Django
Flask

в том же порядке.

set не гарантирует порядок вставки.


16. Нельзя полагаться на порядок

Иногда при нескольких выводах порядок может выглядеть одинаковым.

Например:

print(technologies)
print(technologies)

Это не означает, что множество стало упорядоченным.

После:

  • другого запуска Python;
  • изменения множества;
  • изменения состава элементов;

расположение может выглядеть иначе.

Поэтому код не должен зависеть от порядка элементов set.


17. У set нет обычных индексов

Раз порядок не определён, мы не можем написать:

numbers[0]

как со списком или кортежем.

Такой код приведёт к:

TypeError

set не является последовательностью с индексами.


set нельзя складывать через +

18. Оператор сложения

first = {
    10,
    20,
}

second = {
    30,
    40,
}

result = (
    first
    + second
)

приведёт к:

TypeError

Для set оператор:

+

не определён.

Позже познакомимся со специальными операциями объединения множеств.


19. Умножение тоже не работает

numbers = {
    10,
    20,
}

print(
    numbers * 3
)

Получим:

TypeError

В отличие от:

str
list
tuple

множество не поддерживает повторение через:

*

Повторение элементов для множества и не имело бы привычного смысла, потому что одинаковые элементы всё равно не могут существовать в нём одновременно.


Главное преимущество set

20. Быстрая проверка через in

Возьмём список:

numbers = [
    10,
    20,
    30,
]

Проверка:

20 in numbers

должна искать значение среди элементов списка.

В худшем случае приходится пройти практически весь список.

Средняя сложность такого поиска:

O(n)

У множества:

numbers = {
    10,
    20,
    30,
}

проверка:

20 in numbers

работает через хеш-таблицу.

В среднем сложность:

O(1)

Сравнение скорости

21. list против set

Можно провести эксперимент:

from timeit import timeit


numbers_range = range(
    10_000_001
)

numbers_list = list(
    numbers_range
)

numbers_set = set(
    numbers_range
)


def contains_in_list():
    return (
        10_000_000
        in numbers_list
    )


def contains_in_set():
    return (
        10_000_000
        in numbers_set
    )


print(
    timeit(
        contains_in_list,
        number=10,
    )
)

print(
    timeit(
        contains_in_set,
        number=10,
    )
)

Оба алгоритма возвращают:

True

Но время работы будет очень сильно отличаться.


22. Почему список медленнее

В списке:

10_000_000 in numbers_list

Python ищет значение среди элементов.

Упрощённо:

0
↓
1
↓
2
↓
3
↓
...
↓
10 000 000

Чем дальше находится искомое значение, тем больше сравнений может потребоваться.

Если значения вообще нет, в худшем случае приходится проверить весь список.

Поэтому:

list membership → O(n)

23. Почему set быстрее

У множества работа очень упрощённо выглядит так:

искомый объект
↓
hash(object)
↓
поиск подходящей позиции
↓
проверка найденного элемента
↓
True / False

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

Поэтому в среднем:

set membership → O(1)

24. O(1) — средняя сложность

Важно:

O(1)

для set — это средняя сложность.

Хеш-таблицы могут сталкиваться с:

  • коллизиями;
  • перестройкой внутренней таблицы;
  • другими неблагоприятными ситуациями.

Поэтому в худшем теоретическом случае поиск может быть медленнее.

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


Где это полезно

25. Много проверок принадлежности

Предположим, есть большой список запрещённых идентификаторов:

blocked_ids = {
    105,
    208,
    501,
    700,
    901,
}

Проверка:

user_id = 501

if user_id in blocked_ids:
    print(
        'Доступ запрещён'
    )

очень хорошо соответствует назначению множества.

Нам:

  • не нужны индексы;
  • не нужны повторяющиеся значения;
  • не важен порядок;
  • зато нужен быстрый in.

Это типичный случай для:

set

Сравнение множеств

26. Порядок не влияет на равенство

Например:

first = {
    10,
    20,
    30,
}

second = {
    30,
    10,
    20,
}

print(
    first == second
)

Результат:

True

Оба множества содержат одинаковые элементы.

Порядок записи:

10, 20, 30

и:

30, 10, 20

никакого значения для равенства не имеет.


27. Сравним со списками

first = [
    10,
    20,
    30,
]

second = [
    30,
    10,
    20,
]

print(
    first == second
)

Результат:

False

Для списков порядок элементов является частью значения последовательности.

Для множеств — нет.


Удаление дубликатов

28. Простое практическое применение

Есть:

numbers = [
    10,
    20,
    10,
    30,
    20,
    40,
    10,
]

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

unique_numbers = set(
    numbers
)

print(unique_numbers)

Получим:

10
20
30
40

каждое значение только один раз.

Это одно из самых распространённых простых применений множества.


Главное по теме

set — это:

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

Множество с данными:

numbers = {
    10,
    20,
    30,
}

Пустое множество:

numbers = set()

Пустые:

{}

создают не set, а:

dict

В set() можно передать итерируемый объект:

set(
    [10, 20, 30]
)
set(
    (10, 20, 30)
)
set(
    'Python'
)

Можно использовать set comprehension:

squares = {
    number ** 2
    for number in range(10)
}

Элементы должны быть:

hashable

Поэтому:

{
    10,
    'Python',
    (1, 2),
}

работает.

А попытка добавить обычный:

list

приведёт к:

TypeError: unhashable type: 'list'

Одинаковые элементы автоматически объединяются в один:

set(
    [
        10,
        10,
        20,
        20,
    ]
)

даёт множество:

{10, 20}

set не гарантирует порядок элементов и не поддерживает обращение по обычным индексам.

При сравнении:

{
    1,
    2,
    3,
} == {
    3,
    2,
    1,
}

получаем:

True

Одно из главных преимуществ set — оператор:

in

Для списка поиск имеет среднюю линейную сложность:

O(n)

Для множества поиск по хеш-таблице в среднем:

O(1)

Поэтому set особенно полезен, когда:

  • нужны только уникальные элементы;
  • порядок не важен;
  • приходится очень часто проверять наличие значения.