Python: Как работает «IN» (для списков)?

Question

У меня есть этот код

list = ['a','b','c']

if 'b' in list:
   return "found it"
return "not found"

Теперь, как это работает? Обходит ли весь список, сравнивая элемент? Использует ли он какую-то хэш-функцию?

Кроме того, то же самое для этого кода?

list.index('b')

Answer 1

in использует метод __contains__.Каждый тип контейнера реализует его по-своему.Для списка используется линейный поиск.Для указания он использует поиск по хешу.

Answer 2

Python Wiki утверждает , что val in list имеет O(n) среднюю сложность времени.Это подразумевает линейный поиск.Я ожидаю, что list.index(val) будет таким же.

В конце концов, list - это, ну, список.Если вам нужны хеш-таблицы, рассмотрите возможность использования set или dict.

Answer 3

Сравнение оценивается один раз для каждого элемента в списке.

См. http://effbot.org/zone/python-list.htm для получения дополнительной информации о списках Python (и перечислениях, которые вы опубликовали).

Answer 4

Оба in и list.index() зацикливаются на всех элементах и ​​поэтому имеют линейное время выполнения.В дополнение к интуитивной логике (так должно быть, поскольку список - это просто динамический массив), вы можете убедиться в этом, взглянув на реализацию C из list_contains (in) и listindex.

Например, подпрограмма __contains__ реализована так просто:

static int
list_contains(PyListObject *a, PyObject *el)
{
    Py_ssize_t i;
    int cmp;

    for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)
        cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),
                                           Py_EQ);
    return cmp;
}

Answer 5

Вот разборка:

>>> from dis import dis
>>> def foo():
...     a = ['a', 'b', 'c']
...     if 'b' in a:
...             print "Found it!"
... 
>>> dis(foo)
  2           0 LOAD_CONST               1 ('a')
              3 LOAD_CONST               2 ('b')
              6 LOAD_CONST               3 ('c')
              9 BUILD_LIST               3
             12 STORE_FAST               0 (a)

  3          15 LOAD_CONST               2 ('b')
             18 LOAD_FAST                0 (a)
             21 COMPARE_OP               6 (in)
             24 POP_JUMP_IF_FALSE       35

  4          27 LOAD_CONST               4 ('Found it!')
             30 PRINT_ITEM          
             31 PRINT_NEWLINE       
             32 JUMP_FORWARD             0 (to 35)
        >>   35 LOAD_CONST               0 (None)
             38 RETURN_VALUE  

Внутриоператор вызывает __contains__ в инструкции COMPARE_OP.Вы можете увидеть это в действии здесь:

class X(object):
    def __init__(self, elements):
        self.elements = elements
    def __contains__(self, element):
        print "Called __contains__"
        return element in self.elements

x = X(['a', 'b', 'c'])
if 'b' in x:
    print "Found it!"

Вы получите этот вывод:

...
>>> x = X(['a', 'b', 'c'])
>>> if 'b' in x:
...     print "Found it!"
... 
Called __contains__
Found it!