Python: поиск элемента в списке и множестве

А вы знали, что в Питоне операция in для множеств (set) работает намного быстрее, чем для списков (list)? Да, я слоупок.

Julian Andres Klode приводит пример у себя в блоге:

In [1]: a = range(10**6)

In [2]: b = set(a)

In [3]: %timeit 10**6 in a
10 loops, best of 3: 31.8 ms per loop

In [4]: %timeit 10**6 in b
10000000 loops, best of 3: 98.6 ns per loop

В случае со списком операция выполняется за 31,8 миллисекунды, а для множества результат составляет 98,6 наносекунд. Нанотехнологии в действии!

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

In [5]: %timeit b = set(a)
10 loops, best of 3: 60.2 ms per loop

В данном случае на преобразование требуется 60,2 мс. Это значит, что использование множества здесь имеет смысл, только если нужно произвести поиск не менее двух раз.

Скорость поиска в списке также зависит от того, какой именно элемент нужно найти. В своём примере Julian рассматривает элемент, который расположен в самом конце.

А что если он расположен в начале?

In [6]: %timeit 1 in a
10000000 loops, best of 3: 107 ns per loop

Не сильно отличается от множества.

Но, тем не менее, я всё-таки рекомендую использовать множества, если требуется многократно производить поиск по произвольному списку.