Разница во времени Python

Question

Недавно я пытался решить проблему this problem на Hackerrank. Я закончил с следующим решением, которое дает правильный ответ в течение данного срока:

from collections import Counter 
lisa=[] 
for each in range(input()): 
    current=raw_input() 
    count=0 
    lookup_dict={} 
    i=0 
    for i in range(len(current)): 
     for j in range(i,len(current)): 
      sub_string=current[i:j+1] 
      sub_string=''.join(sorted(sub_string)) 
      if sub_string in lookup_dict.keys(): 
       lookup_dict[sub_string]+=1 
      else: 
       lookup_dict[sub_string]=1 

    for k in lookup_dict.values(): 
     count+=k*(k-1)/2 
    print count 

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

from collections import * 
for i in range(input()): 
    s = raw_input() 
    check = defaultdict(int) 
    l = len(s) 
    for i in range(l): 
     for j in range(i+1,l+1): 
      sub = list(s[i:j]) 
      sub.sort() 
      sub = "".join(sub) 
      check[sub]+=1 
    sum = 0 
    for i in check: 
     n = check[i] 
     sum += (n*(n-1))/2 
    print sum 

Я думаю, что это имеет какое-то отношение к методу defaultdict, но не могу понять, почему?

Answer 1

В Python 2.x, dict.keys() возвращает список, и в своем первом решении, вы фактически делаете -

if sub_string in lookup_dict.keys() 

Это будет O (п) операции (п быть размером справочник - lookup_dict), так как .keys() фактически возвращает список и список проверки сдерживания O (n), а также, вероятно, есть добавленная стоимость создания списка.

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

---

Пример, показывающий dict.keys() возвращения списка -

>>> d = {1:2,3:4,5:6,7:8} 
>>> d.keys() 
[1, 3, 5, 7] 

Answer 2

Говоря о defaultdict: оптимизированная немного по сравнению с простым ключом проверки. Т.е .:

x = defaultdict(int) 
for i in xrange(...): 
    x[i] += 1 

выполняет ~ 50% быстрее, чем

x = {} 
for i in xrange(...): 
    if i in x: 
     x[i] +=1 
    else: 
     x[1] = 1 

если случай все ключи отсутствуют.

Но основной случай заключается в том, что вызов dict.keys() в py2 фактически создает список. Поэтому при проверке key in dict.keys() необходимо сначала выделить память для списка, а затем заполнить ее фактическими значениями ключа, а после этого проверить свой ключ против него. Что самое плохое, сразу после этого этот список должен быть очищен сборщиком мусора, а в следующем for шаге вы сделаете то же самое, за исключением того, что для этого списка будет выделено больше памяти. Таким образом, это фактически убивает производительность в вашем примере.