Насколько эффективен/быстрый Python 'in'? (Временная сложность)

В Python какова эффективность ключевого слова in, например:

a = [1, 2, 3]
if 4 in a:
  ...

Ответы

Ответ 1

Это зависит от правой руки операнда:

Операторы in и not in проверяют членство в коллекции. [...] Тест на членство в коллекции традиционно связан с последовательностями; объект является членом коллекции, если коллекция является последовательностью и содержит элемент, равный этому объекту. Однако для многих других типов объектов имеет смысл поддерживать тесты на членство без последовательности. В частности, словари (для ключей) и множества поддерживают тестирование членства.

Классы могут реализовать специальный метод __contains__ для переопределения поведения по умолчанию (итерации по последовательности) и, таким образом, могут предоставить больше (или менее) эффективный способ тестирования членства, чем сравнение каждого элемента контейнера.

Операторы тестирования членства (in и not in) обычно реализуются как итерация через последовательность. Однако объекты контейнера могут предоставить следующий специальный метод с более эффективной реализацией, что также не требует, чтобы объект был последовательностью.

Поскольку у вас есть список в вашем примере, он повторяется и каждый элемент сравнивается до тех пор, пока не будет найдено совпадение или список не будет исчерпан. Сложность времени обычно O(n).