В какой структуре данных Python, `list` или `set`, поиск элемента выполняется быстрее и почему?

Поиск элемента значительно быстрее во множестве (set).

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

set (множество) — O(1)

• Структура: Множество реализовано на основе хеш-таблицы.
• Принцип поиска: Когда вы ищете элемент, Python вычисляет его хеш-значение. Этот хеш напрямую указывает на местоположение (или "корзину") в памяти, где может находиться элемент. Благодаря этому доступ к элементу происходит практически мгновенно, независимо от размера множества.
• Асимптотическая сложность: O(1) — константное время в среднем случае.

list (список) — O(n)

• Структура: Список — это упорядоченная последовательность элементов, хранящихся в памяти друг за другом.
• Принцип поиска: Для поиска элемента Python вынужден выполнять линейный перебор: он проверяет элементы один за другим, начиная с первого, пока не найдет совпадение.
• Асимптотическая сложность: O(n) — линейное время, где n — количество элементов в списке. В худшем случае придется проверить все элементы.

Практический пример производительности

import timeit

large_list = list(range(1_000_000))
large_set = set(large_list)
element_to_find = 999_999

# Поиск в списке (медленно)
list_time = timeit.timeit(lambda: element_to_find in large_list, number=100)

# Поиск в множестве (очень быстро)
set_time = timeit.timeit(lambda: element_to_find in large_set, number=100)

print(f"Поиск в list:  {list_time:.6f} секунд")
print(f"Поиск в set:   {set_time:.6f} секунд")
# Поиск в list:  1.234567 секунд (примерное значение)
# Поиск в set:   0.000008 секунд (примерное значение)

Когда что использовать