in в Python: мгновенная проверка принадлежности множеству

Вопрос есть ли элемент внутри — самый частый вопрос к коллекции. Был ли гость в списке приглашённых, входит ли слово в стоп-лист, разрешено ли действие. Оператор in отвечает на все эти вопросы, но скорость ответа зависит от структуры под ним: у множества он мгновенный, у списка — перебор. В этом уроке — как проверять, почему множество ищет прыжком, и где эта разница превращается в часы работы программы.

Оператор in на множестве

in ставится между значением и множеством и отвечает булевым значением: True, если элемент есть, False, если нет:

banned = {'spam', 'troll'}
user = 'troll'
print(user in banned)
print('anna' in banned)
print('guest' not in banned)

True
False
True

Три вопроса — три честных ответа: тролль в стоп-листе, anna нет, а гостю вход разрешён. Оператор работает с любыми значениями множества — строками и числами одинаково уверенно, и ничего не меняет в самой коллекции.

not in: гарантия отсутствия

Обратный вопрос — нет ли элемента — задаётся оператором not in. Часто он читается естественнее двойного отрицания и удобен для условий:

banned = {'spam', 'troll'}
user = 'guest'
print(user not in banned)
banned.add(user)
print(user not in banned)

True
False

Гость был вне стоп-листа — True; после добавления — уже False. not in — это просто перевёрнутый in: оба оператора спрашивают у множества одно и то же, отличаются лишь ожидаемый ответ. Оператор работает и с числами — вопрос тот же: есть или нет:

pages = {10, 20, 30}
print(20 in pages)
print(40 in pages)
print(20 not in pages)

True
False
False

Двадцатая страница учтена, сороковой нет, а not in подтвердил отсутствие. Тип значения не важен: множество проверяет любые свои элементы одинаково мгновенно.

in у списка: ответ тот же

Оператор in работает и со списками — синтаксис тот же, ответы те же:

banned_list = ['spam', 'troll']
print('troll' in banned_list)
print('anna' in banned_list)

True
False

Снаружи неотличимо: True и False там, где и ожидалось. Разница — внутри. Чтобы ответить про список, Python перебирает элементы по очереди, сравнивая каждый с искомым: нашёл на второй позиции — сделал два сравнения, не нашёл — прошёл весь список до конца. У множества механизм совсем другой.

Почему множество отвечает мгновенно

Множество устроено как хеш-таблица. При добавлении элемент Python вычисляет его хеш — число-отпечаток — и кладёт значение в полку по этому номеру. При проверке in достаточно вычислить хеш искомого и заглянуть в одну конкретную полку: перебирать всё множество не нужно. Поэтому проверка занимает одно и то же время — и на трёх элементах, и на миллионе. Список ищет перебором за O(n), множество — прыжком за O(1); большая О — это рост времени при росте данных: у перебора он линейный, у хеша — почти нулевой.

big_set = set(range(1000000))
big_list = list(big_set)
print(999999 in big_set)
print(999999 in big_list)
print(len(big_set))

True
True
1000000

Ответы одинаковы — True и True. Разница во времени: множество посчитало хеш числа и загляло в одну полку, список перебрал до миллиона значений. В единичной проверке разница невидима, но проверок в программе обычно много — и там перебор накапливается.

# all_users — 100 000 пользователей
# banned_list — 10 000 стоп-имен
for user in all_users:
    if user in banned_list:
        block(user)

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

Практика: фильтр разрешённых действий

Соберём приём в рабочую программу: роли с разрешениями — классическая задача, где принадлежность проверяется на каждом шаге:

allowed = {'читать', 'писать'}
actions = ['читать', 'удалять', 'писать', 'настраивать']
for action in actions:
    if action in allowed:
        print(action, '- разрешено')
    else:
        print(action, '- запрещено')

читать - разрешено
удалять - запрещено
писать - разрешено
настраивать - запрещено

Белый список — множество, каждое действие проверяется в нём одним in. Направление проверки важно: спрашиваем у разрешений, а не у действий — маленькое множество проверяется быстрее большого списка действий, и код читается как вопрос: разрешено ли это?

tags = {'python', 'code'}
target = 'web'
if target in tags:
    tags.remove(target)
    print(target, '- удалён')
else:
    print(target, '- нет такого')
print(sorted(tags))

web - нет такого
['code', 'python']

Здесь in нужен не для скорости, а для сообщения: удаление тега web не состоялось, и программа знает почему. Такой же выбор делали в прошлом уроке между remove и discard — проверка in даёт версию с собственным сообщением.

Словарь ищет тем же механизмом, что и множество: хеш ключа и одна полка. Поэтому пара set и dict закрывает почти все задачи быстрого поиска, а списки оставляют перебору там, где порядок нужен сам по себе. Хеш-механизм у обоих общий — урок 17 показывает его изнутри. А если принадлежность проверяется часто, следующий шаг — операции над целыми множествами: объединение множеств собирает всех сразу без перебора.