Как Python проверяет, существует ли элемент в списке?

Question

Используя стандартный синтаксис, который поставляет Python, чтобы проверить, если элемент находится в списке:

if someElement in someList: 

Что фактически выполняется здесь? Является ли Python зацикливанием по каждому индексу и проверяет на равенство или что-то более сложное реализуется?

Программа, которую я пишу, работает очень медленно. Никакая математика не выполняется, но она в значительной степени зависит от проверки, существуют ли элементы в длинных списках. Есть ли более быстрое решение?

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

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

Не стоит недооценивать скорость проверки предметов в наборе.

Answer 1

Да, это цикл по каждому индексу и проверка равенства.

Это:

someElement in someList 

эквивалентно:

any(x == someElement for x in someList) 

Для ускорения, вероятно, можно использовать set вместо list, но это действительно зависит от типа элементов в вашей коллекции.

Если список большой, поиск может быть медленным.

Answer 2

nc=set(someList) 
if someElement in nc: #this will now be O(1) rather than O(n) 

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

Answer 3

Да, Python перебирает каждый индекс. Оператор in вызывает специальный метод __contains__() (source).

Я думаю, что для списка - предполагающей CPython 2 - она ​​заканчивается в this list_contains code в listobject.c, простой for цикл над элементами списка:

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; 
} 

есть более быстрое решение?

Используйте контейнер с более быстрым поиском - @vks предлагает набор, словари также распространены. Оба зависят от того, что ваши данные хешируются с hash(item), или они не могут работать.

Но изучение структур данных и их различных характеристик производительности слишком велико для ответа, особенно без каких-либо подробностей о том, что ваша задача, и без какого-либо кода и никакой производительности.Структуры деревьев также могут иметь быстрый поиск, но отгрузка работы в существующую библиотеку, написанную на C, является хорошей тактикой Python, если вы ее можете найти.