Вызывает ли оператор 'in', используемый в словарях python, функцию keys () каждый раз?

Question

Допустим, у меня есть

dict = {...} #lots of words in dictionary  

Я должен сделать

for word in ...: #long list of words
    if word in dict:
        #do something

Мой вопрос заключается в том, вызывает ли слово if в dict функцию dict.keys () каждый раз и, следовательно, намного медленнее, чем если бы я добавил в начало другую переменную dict_keys = dict.keys ()? Результат того, о чем я говорю, будет следующим:

dict = {...}
dict_keys = dict.keys()

for word in ...:
    if word in dict_keys:
        #do something

Спасибо

Answer 1

нет. foo in mydict на самом деле намного быстрее , чем foo in keys_list, поскольку dict s являются хеш-таблицами, поэтому поиск элемента внутри него O(1). В то время как foo в keys_list будет O(n) (медленнее по мере увеличения количества ключей)

Но вы всегда можете проверить себя:

$ python -m timeit -s "x = range(1000)" "15 in x"
1000000 loops, best of 3: 0.311 usec per loop
$ python -m timeit -s "x = dict.fromkeys(xrange(1000))" "15 in x"
10000000 loops, best of 3: 0.0515 usec per loop

Таким образом, проверка непосредственно на dict для 1000 элементов происходит на один порядок быстрее, не учитывая время .keys()

Answer 2

На самом деле встроенные диктанты просто вызывают их __contains__, что напрямую вызывает функцию C dict_has_key, которая очень быстра.Таким образом, делать это первым способом лучше, потому что это не заставляет вас оценивать всю последовательность ключей внутри вашего dict как вызов keys().

Answer 3

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

for word in set(some_dict) & set(wordlist):
    # do something

Answer 4

Короткий ответ: нет, больше похоже на __contains__, то есть O (1) (т.е. дешево).

Answer 5

Просто на основе простых экспериментов с кодом, подобным:

_w= ['a', 'b', 'c', 'd', 'e']
d= {}
w= []
for k in xrange(123):
    for word in _w:
        wk= word+ str(k)
        d[wk]= k
        w.append(wk)

def m1():
    for word in w:
        if word in d:
            pass

def m2(n= 1):
    dk= d.keys()
    for word in w:
        if word in dk:
            pass

и временем:

In []: len(w)
Out[]: 5
In []: %timeit m1()
1000000 loops, best of 3: 657 ns per loop
In []: %timeit m2()
1000000 loops, best of 3: 1.55 us per loop

In []: len(w)
Out[]: 615
In []: %timeit m1()
10000 loops, best of 3: 49.2 us per loop
In []: %timeit m2()
100 loops, best of 3: 5.62 ms per loop

Вывод будет таким: m1 () - явный победитель (как и ожидалось; -).

Хорошо, это не совсем доказательство (в строгом смысле) превосходства m1().Все еще существует небольшая вероятность того, что кто-то определит набор ключей, в которых время выполнения m1() и m2() близко друг к другу (но я не могу найти ни одного случая, когда m1() будет на самом деле намного хуже, чем m2()).На практике m1() подход всегда побеждает.Всегда воодушевлено опробовать первые убедительные факты альтернативных подходов, а затем, если что-то противоречит вашим ожиданиям, вы будете более готовы выяснить, почему это происходит.