Какой алгоритм используется при использовании оператора in в python для поиска списка?

При использовании оператора "in" для поиска элемента в списке, например.

if item in list:
  print item

Какой алгоритм используется для поиска этого элемента. Является ли это прямым поиском списка от начала до конца или использует ли он что-то вроде бинарного поиска?

Ответы

Ответ 1

list нельзя считать упорядоченным (или любым порядком), поэтому двоичный поиск не будет работать. Также нельзя считать ключи хешируемыми, поэтому в отличие от dict или set поиск хеш-таблицы не может использоваться для ускорения поиска

Угадайте, что это сквозная проверка каждого элемента от первого до последнего.

Я попытаюсь выкопать соответствующий исходный код Python.

-

Изменить: функция Python list.__contains__(), которая реализует оператор in, определена в listobject.c:

   393 static int
   394 list_contains(PyListObject *a, PyObject *el)
   395 {
   396     Py_ssize_t i;
   397     int cmp;
   398 
   399     for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)
   400         cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),
   401                                            Py_EQ);
   402     return cmp;
   403 }

Он выполняет итерацию по каждому элементу в списке, от первого элемента до последнего элемента (или до тех пор, пока не найдет совпадение). Здесь нет ярлыков.

-

Изменить 2: Сюжет сгущается. Если Python обнаруживает, что вы тестируете членство в элементе в константе list или set, например:

if letter in ['a','e','i','o','u']:    # list version
if letter in {'a','e','i','o','u'}:    # set version

Изменить 3 [@JohnMachin]:

Список констант оптимизирован для константного кортежа в 2.5-2.7 и 3.1-3.3.
Постоянный набор оптимизирован для (константного) frozenset в 3.3.

См. также ответ @CoryCarson.