Эффективность Python в ключевом слове для отсортированного списка

В стандартной библиотеке есть бинарный поиск для Python, в модуле bisect. Он не поддерживает in/contains как есть, но вы можете написать небольшую функцию для его обработки:

from bisect import bisect_left
def contains(a, x):
    """returns true if sorted sequence `a` contains `x`"""
    i = bisect_left(a, x)
    return i != len(a) and a[i] == x

потом

>>> contains([1,2,3], 3)
True
>>> contains([1,2,3], 4)
False

Однако это не будет очень быстрым, так как bisect написан на Python, а не на C, поэтому во многих случаях вы, вероятно, обнаружите, что последовательный in быстрее. bisect имеет необязательный C ускорение в CPython начиная с Python 2.4.

Трудно определить точную точку безубыточности в CPython. Это потому, что код написан на C; если вы проверите значение, которое больше или меньше любого значения в последовательности, то предсказание ветвления ЦП сыграет с вами злую шутку, и вы получите:

In [2]: a = list(range(100))
In [3]: %timeit contains(a, 101)
The slowest run took 8.09 times longer than the fastest. This could mean that an intermediate result is being cached 
1000000 loops, best of 3: 370 ns per loop

Здесь лучшее из 3 не отражает истинное время работы алгоритма.

Но, настроив тесты, я пришел к выводу, что деление пополам может быть быстрее, чем in для списков, содержащих всего 30 элементов.

Однако, если вы выполняете действительно много in операций, вам следует использовать set; вы можете преобразовать список один раз в набор (он даже не будет отсортирован), и операция in будет асимптотически быстрее, чем любой двоичный поиск:

>>> a = [10, 6, 8, 1, 2, 5, 9]
>>> a_set = set(a)
>>> 10 in a_set
True

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

В стандартной библиотеке есть модуль bisect, поддерживающий поиск в отсортированных последовательностях.

Однако для небольших списков я готов поспорить, что реализация оператора in на C превзойдет bisect. Вам придется провести измерения с кучей распространенных случаев, чтобы определить реальную точку безубыточности на вашем целевом оборудовании...

Стоит отметить, что если вы можете обойтись без неупорядоченной итерации (например, set), то вы можете выполнить поиск в среднем за O(1) времени (используя оператор in), по сравнению с делением пополам последовательности, которая является O(logN) и оператором in в последовательности, которая O(N). И с набором вы также избегаете затрат на его сортировку в первую очередь :-).