python (2.7) : Why is there a performance difference between the following 2 code snippets that implement the intersection of two dictionaries

Question

以下 2 个代码片段(A 和 B)都返回 2 个字典的交集。

以下 2 个代码片段应该在 O(n) 内运行并输出相同的结果。然而，pythonic 的代码片段 B 似乎运行得更快。 这些代码片段来自 Python Cookbook。

代码片段A:

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

代码片段 B:

def pythonicsimpleway():
    return [k for k in to500 if k in evens]

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

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

Python 2.7.5 使用 2.3 Ghz Ivy Bridge 四核处理器 (OS X 10.8.4)

我明白了

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

Answer 1

他们做的事情并不完全相同；第一个做了更多的工作:

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

在 one 操作中创建 python 列表对象之前，列表理解将所有生成的元素收集到 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() 为 True)，而列表推导则为 7 条，其中额外的指令主要覆盖 LOAD_ATTR 和 CALL_FUNCTION。

如果你想让第一个版本更快，用 in 测试替换 .has_key() ，直接在字典上循环并缓存 .append () 局部变量中的属性:

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

然后使用 timeit 模块正确测试计时(重复运行，您平台的最准确计时器):

>>> timeit('f()', 'from __main__ import evens, to500, simpleway as f', number=10000)
1.1673870086669922
>>> timeit('f()', 'from __main__ import evens, to500, pythonicsimpleway as f', number=10000)
0.5441269874572754
>>> timeit('f()', 'from __main__ import evens, to500, simpleway_optimized as f', number=10000)
0.6551430225372314

此处simpleway_optimized在速度上接近于列表理解方法，但后者仍然可以通过一步构建python列表对象胜出。