Python（2.7）：下面两个实现两个字典交集的代码片段之间的性能差异是什么

Question

以下两个代码段（A&B）都返回两个字典的交集。在

下面两个代码片段都应该在O（n）中运行并输出相同的结果。不过，python代码段B的运行速度似乎更快。这些代码片段来自Python食谱。

代码段A：

def simpleway():
    result = []
    for k in to500.keys():
          if evens.has_key(k):
                 result.append(k)
    return result

代码段B：

^{pr2}$

一些设置逻辑和用于为两个函数计时的函数=>

to500 = {}
for i in range(500): to500[i] = 1
evens = {}
for i in range(0,1000,2): evens[i] = 1

def timeo(fun, n=1000):
    def void(): pass
    start = time.clock()
    for i in range(n): void()
    stend = time.clock()
    overhead = stend - start
    start = time.clock()
    for i in range(n): fun()
    stend = time.clock()
    thetime = stend - start
    return fun.__name__, thetime - overhead

使用2.3 Ghz Ivy Bridge四核处理器（OS X 10.8.4）的Python2.7.5

我明白了

>>> timeo(simpleway)
('simpleway', 0.08928500000000028)
>>> timeo(pythonicsimpleway)
('pythonicsimpleway', 0.04579400000000078)

Answer 1

他们做的事情并不完全一样，第一个做的工作要多得多：

• 它在循环中每次都查找.has_key()和{}方法，然后调用它们。这需要对每个调用进行堆栈推送和弹出。在
• 它将每个新元素逐个附加到列表中。Python列表必须动态增长，以便为这些元素腾出空间。在

list comprehension在一个one操作中创建python list对象之前，收集C数组中所有生成的元素。在

这两个函数确实产生了相同的结果，一个只是不必要的慢。在

如果您想深入了解细节，请查看使用dis模块的字节码反汇编：

>>> dis.dis(simpleway)
  2           0 BUILD_LIST               0
              3 STORE_FAST               0 (result)

  3           6 SETUP_LOOP              51 (to 60)
              9 LOAD_GLOBAL              0 (to500)
             12 LOAD_ATTR                1 (keys)
             15 CALL_FUNCTION            0
             18 GET_ITER            
        >>   19 FOR_ITER                37 (to 59)
             22 STORE_FAST               1 (k)

  4          25 LOAD_GLOBAL              2 (evens)
             28 LOAD_ATTR                3 (has_key)
             31 LOAD_FAST                1 (k)
             34 CALL_FUNCTION            1
             37 POP_JUMP_IF_FALSE       19

  5          40 LOAD_FAST                0 (result)
             43 LOAD_ATTR                4 (append)
             46 LOAD_FAST                1 (k)
             49 CALL_FUNCTION            1
             52 POP_TOP             
             53 JUMP_ABSOLUTE           19
             56 JUMP_ABSOLUTE           19
        >>   59 POP_BLOCK           

  6     >>   60 LOAD_FAST                0 (result)
             63 RETURN_VALUE        
>>> dis.dis(pythonicsimpleway)
  2           0 BUILD_LIST               0
              3 LOAD_GLOBAL              0 (to500)
              6 GET_ITER            
        >>    7 FOR_ITER                24 (to 34)
             10 STORE_FAST               0 (k)
             13 LOAD_FAST                0 (k)
             16 LOAD_GLOBAL              1 (evens)
             19 COMPARE_OP               6 (in)
             22 POP_JUMP_IF_FALSE        7
             25 LOAD_FAST                0 (k)
             28 LIST_APPEND              2
             31 JUMP_ABSOLUTE            7
        >>   34 RETURN_VALUE        

对于显式for循环，每次迭代的字节码指令数要大得多。simpleway循环每次迭代必须执行11条指令（如果.has_key()为真），而列表理解则为7条，其中额外的指令主要覆盖LOAD_ATTR和{}。在

如果要使第一个版本更快，请将.has_key()替换为in测试，直接在字典上循环并将.append()属性缓存到一个局部变量中：

^{pr2}$

然后使用timeit模块正确地测试计时（重复运行，您的平台最精确的计时器）：

^{3}$

这里simpleway_optimized正在快速接近列表理解方法，但是后者仍然可以通过一步构建python列表对象来获胜。在