Python速度差异

Question

最近我在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方法有关，但是不知道为什么？

- Clock Slave

---

你可以尝试仅替换 defaultdict 部分，然后再次检查所花费的时间。此外，在每个循环中你正在计算 len(current)，第二个示例缓存该值，因为它不会改变。 - Hacketo

尝试根据 @cnluzon 的评论，将 lookup_dict.keys() 替换为 lookup_dict，看看对速度的影响。 - Kevin

虽然速度差别不大，但你应该使用 from collections import defaultdict，这更符合 Python 的风格。 - SuperBiasedMan

@ClockSlave 我相信 .keys() 会立即生成完整的列表，而 in dict 检查每个值。 - SuperBiasedMan

我怀疑keys()的时间复杂度是O(n)，其中n是字典中元素的数量。x in dict的时间复杂度为O(1)，因此对于大型字典来说，它往往具有更好的性能。 - Kevin

Answer 1

在Python 2.x版本中，dict.keys()函数返回一个列表。在你的第一个解决方案中，实际上你正在执行 -

if sub_string in lookup_dict.keys()

这将是一个O(n)的操作（n是字典lookup_dict的大小），因为.keys()实际上返回一个列表，而列表中包含检查的成分是O(n)，也很可能存在创建列表的额外成本。

而在第二种方法中，你没有任何这样的检查，相反，默认字典自动处理设置默认值，这可能是你的第一种解决方案比第二种慢得多的原因之一（假设你在最内层循环中执行dict.keys()查找，因此会发生那么多次查找）。

---

下面是一个示例，显示dict.keys()返回列表 -

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

- Anand S Kumar

---

除了列表查找的O(N)之外，还有内存分配的O(M)，其中M是唯一键的总数。因此，在最坏的情况下，它非常接近于O(N²)。 - Slam

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

如果所有键都丢失，则需要使用all关键字进行判断。

但主要情况是，在py2中调用dict.keys()实际上会创建一个列表。因此，检查key in dict.keys()需要首先为列表分配内存，然后用实际的键值填充它，并在此之后检查您的键是否存在。更糟糕的是，在此之后，垃圾收集器应该清理此列表，并在下一个for步骤中执行相同操作，除了将为该列表分配更多内存。因此，在您的示例中，这实际上会影响性能。

- Slam

---

谢谢。你能推荐一些关于该语言架构的阅读材料吗？ - Clock Slave

可能听起来很明显，但 https://docs.python.org/ 是一个不错的选择，特别是当你知道要找什么时。对于入门级别的人...Mark Lutz 应该就可以了，但阅读最新版本可能会很痛苦，因为它非常详细。对于稍微高一点的水平——当你实际上能够编写代码，但并不总是知道为什么事情会这样工作——看看 Julien Danjou 的 "Hackers guide to Python" 和 Luciano Ramalho 的 "Fluent Python"。最后一个结果出奇的酷。还有一件事：我强烈推荐使用带有其魔法 %timeit 的 iPython - 这将节省您很多时间) - Slam