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(n) 操作(n 是字典的大小 - 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]