В каких случаях использовать set вместо list в Python

Что проверяют

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

Как отвечать

Берите set, когда важны уникальность и быстрые проверки, и list, когда нужны порядок, дубли и доступ по индексу:

• проверка вхождения: x in s для множества в среднем O(1), для списка O(n). На цикле разница огромная: проверка m элементов по списку длиной n стоит O(m·n), по множеству O(m);
• уникальность: set(items) убирает дубли за один проход. Если порядок важен, используйте list(dict.fromkeys(items)): словари сохраняют порядок вставки с Python 3.7, а множества его не гарантируют;
• операции над множествами: a | b, a & b, a - b, a ^ b, методы issubset и isdisjoint. Сравнить два набора ID или найти новые записи так проще и быстрее, чем вложенными циклами;
• ограничения: элементы должны быть хешируемыми. Числа, строки и кортежи из хешируемых элементов подходят, list и dict нет. Если множество нужно как ключ словаря или элемент другого множества, берите frozenset;
• память: хеш-таблица держит запас пустых слотов, поэтому множество заметно тяжелее списка из тех же элементов.

Отдельно отметьте цену построения: set(big_list) это тоже O(n). Ради одной проверки превращать список в множество смысла нет, выигрыш появляется при многократных проверках. Для последовательности, где важен порядок и нужен быстрый поиск, иногда держат обе структуры сразу.

Где спотыкаются

Пишут s = {} и ждут пустое множество. Это пустой словарь, множество создаётся через set().

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

Говорят, что in в множестве всегда O(1). Это средний случай: при массовых коллизиях хешей возможна деградация до O(n).