Как Python обрабатывает проверку «если объект в списке»

Question

Мне интересно, потому что мне нужна функция, которая бы отвратительно быстро проверяла, есть ли слово в списке словарей - я рассматриваю возможность оставить словарь в виде большой строки и использовать вместо него регулярное выражение. Это должно быть нелепо быстро. Так что мне просто нужен базовый обзор того, как python обрабатывает проверку того, находится ли строка в списке строк и не слишком ли быстро это выполняется.

Answer 1

Если вы хотите невероятно быстрый тест членства, тогда список - неправильная структура данных.Взгляните на реализацию list_contains в listobject.c, строка 437 .Он перебирает список по порядку, сравнивая элемент с каждым элементом по очереди.Чем позже элемент появляется в списке, тем больше времени потребуется для его поиска, и если элемент отсутствует, то весь список должен быть отсканирован.

Используйте взамен set .Наборы реализуются внутренне с помощью хеш-таблицы, поэтому поиск объекта включает в себя вычисление его хеша, а затем сканирование нескольких записей таблицы (обычно только одной).Для конкретного случая поиска строки см. set_lookkey_string в setobject.c, строка 156 .

Answer 2

Набор строк будет иметь время поиска O (1): фактически постоянное независимо от размера набора. Сделать набор из вашего списка строк легко:

my_set = set(my_list)
if my_word in my_set:
    print "it's there!"

Answer 3

Согласно этот сайт , x in s является O (n). Поэтому он проверяет каждую запись (в худшем случае).

В любом случае, не используйте регулярные выражения. Использование наборов или списков является гораздо более интуитивным способом представления данных, и регулярные выражения не будут работать лучше, чем O (n).

Answer 4

Если вам нужна очень быстрая проверка, используйте set:

words = set(words_list)
if "hello" in words:
    print("hello found!"")

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

Answer 5

Если вы используете обычный список, рассмотрите вместо него set.

Если вы хотите реализовать свой собственный детально настроенный тест членства для объекта-контейнера, переопределите __contains__.

Answer 6

Запуск регулярного выражения для вашего списка слов - очень плохая идея;это очень плохо масштабируется.Использование dict(), set() или frozenset() будет масштабироваться намного лучше:

s = set(['one','two','three'])
'two' in s     ## true

b='four'
b in s         ## false

s.add('four')
b in s         ## true

Answer 7

Используйте набор.Если вам нужна проверка без учета регистра, просто сохраните слова в наборе в нижнем регистре.Затем, при проверке наличия определенного слова в наборе, перед проверкой членства используйте слово в нижнем регистре.

Общее правило: нормализуйте записи при построении набора и нормализуйте элемент перед проверкой по набору.Другим примером нормализации является объединение последовательных пробельных символов в один пробел и удаление начальных / конечных пробелов.

Answer 8

Возможно, вы захотите использовать Набор, если беспокоитесь о времени.Набор очень похож на список, но он проверяет членство на основе хеширования.