3

以下 2 个代码片段 (A & B) 都返回 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)
4

1 回答 1

8

他们不完全做同样的事情。第一个做更多的工作：

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

列表推导在一次操作中创建 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()列表理解为 7 条指令，其中额外的指令主要涵盖LOAD_ATTR和CALL_FUNCTION.

如果您想让第一个版本更快，请替换.has_key()为in测试，直接遍历字典并将.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 列表对象来获胜。

于 2013-06-18T21:37:12.270 回答