python - 为什么这个循环比创建字典的字典理解更快？

Question

我不是软件/计算机科学背景，但我喜欢用 Python 编写代码，并且通常可以理解为什么事情会更快。我真的很想知道为什么这个 for 循环比字典理解运行得更快。有什么见解吗？

Problem : Given a dictionary a with these keys and values, return a dictionary with the values as keys and the keys as values. (challenge: do this in one line)

和代码

a = {'a':'hi','b':'hey','c':'yo'}

b = {}
for i,j in a.items():
    b[j]=i

%% timeit 932 ns ± 37.2 ns per loop

b = {v: k for k, v in a.items()}

%% timeit 1.08 µs ± 16.4 ns per loop

Answer 1

您正在使用太小的输入进行测试；虽然与列表推导相比，字典推导对 for 循环的性能优势并不大，但对于实际问题大小，它可以并且确实击败 for 循环，尤其是在定位全局名称时。

您的输入仅包含 3 个键值对。相反，使用 1000 个元素进行测试，我们发现时间非常接近:

>>> import timeit
>>> from random import choice, randint; from string import ascii_lowercase as letters
>>> looped = '''\
... b = {}
... for i,j in a.items():
...     b[j]=i
... '''
>>> dictcomp = '''b = {v: k for k, v in a.items()}'''
>>> def rs(): return ''.join([choice(letters) for _ in range(randint(3, 15))])
...
>>> a = {rs(): rs() for _ in range(1000)}
>>> len(a)
1000
>>> count, total = timeit.Timer(looped, 'from __main__ import a').autorange()
>>> (total / count) * 1000000   # microseconds per run
66.62004760000855
>>> count, total = timeit.Timer(dictcomp, 'from __main__ import a').autorange()
>>> (total / count) * 1000000   # microseconds per run
64.5464928005822

区别就在那里，dict comp 更快，但只有 just 在这个规模上。有 100 倍的键值对，差异会更大:

>>> a = {rs(): rs() for _ in range(100000)}
>>> len(a)
98476
>>> count, total = timeit.Timer(looped, 'from __main__ import a').autorange()
>>> total / count * 1000  # milliseconds, different scale!
15.48140200029593
>>> count, total = timeit.Timer(dictcomp, 'from __main__ import a').autorange()
>>> total / count * 1000  # milliseconds, different scale!
13.674790799996117

当您考虑到都处理了近 10 万个键值对时，这并不是 大的差异。尽管如此，for 循环显然更慢。

那么为什么有 3 个元素的速度差异呢？因为推导式(字典、集合、列表推导式或生成器表达式)在底层实现为一个新的函数，并且调用该函数具有基本成本，普通循环不必支付。

这是两种替代方案的字节码反汇编；注意 dict 理解的顶级字节码中的 MAKE_FUNCTION 和 CALL_FUNCTION 操作码，该函数的作用有一个单独的部分，实际上几乎没有区别在这两种方法之间:

>>> import dis
>>> dis.dis(looped)
  1           0 BUILD_MAP                0
              2 STORE_NAME               0 (b)

  2           4 SETUP_LOOP              28 (to 34)
              6 LOAD_NAME                1 (a)
              8 LOAD_METHOD              2 (items)
             10 CALL_METHOD              0
             12 GET_ITER
        >>   14 FOR_ITER                16 (to 32)
             16 UNPACK_SEQUENCE          2
             18 STORE_NAME               3 (i)
             20 STORE_NAME               4 (j)

  3          22 LOAD_NAME                3 (i)
             24 LOAD_NAME                0 (b)
             26 LOAD_NAME                4 (j)
             28 STORE_SUBSCR
             30 JUMP_ABSOLUTE           14
        >>   32 POP_BLOCK
        >>   34 LOAD_CONST               0 (None)
             36 RETURN_VALUE
>>> dis.dis(dictcomp)
  1           0 LOAD_CONST               0 (<code object <dictcomp> at 0x11d6ade40, file "<dis>", line 1>)
              2 LOAD_CONST               1 ('<dictcomp>')
              4 MAKE_FUNCTION            0
              6 LOAD_NAME                0 (a)
              8 LOAD_METHOD              1 (items)
             10 CALL_METHOD              0
             12 GET_ITER
             14 CALL_FUNCTION            1
             16 STORE_NAME               2 (b)
             18 LOAD_CONST               2 (None)
             20 RETURN_VALUE

Disassembly of <code object <dictcomp> at 0x11d6ade40, file "<dis>", line 1>:
  1           0 BUILD_MAP                0
              2 LOAD_FAST                0 (.0)
        >>    4 FOR_ITER                14 (to 20)
              6 UNPACK_SEQUENCE          2
              8 STORE_FAST               1 (k)
             10 STORE_FAST               2 (v)
             12 LOAD_FAST                1 (k)
             14 LOAD_FAST                2 (v)
             16 MAP_ADD                  2
             18 JUMP_ABSOLUTE            4
        >>   20 RETURN_VALUE

实质区别:循环代码每次迭代使用LOAD_NAME for b，STORE_SUBSCR将键值对存储在dict加载.字典理解使用 MAP_ADD 来实现与 STORE_SUBSCR 相同的功能，但不必每次都加载该 b 名称。

但只有 3 次迭代，dict 理解必须执行的 MAKE_FUNCTION/CALL_FUNCTION 组合才是性能的真正拖累:

>>> make_and_call = '(lambda i: None)(None)'
>>> dis.dis(make_and_call)
  1           0 LOAD_CONST               0 (<code object <lambda> at 0x11d6ab270, file "<dis>", line 1>)
              2 LOAD_CONST               1 ('<lambda>')
              4 MAKE_FUNCTION            0
              6 LOAD_CONST               2 (None)
              8 CALL_FUNCTION            1
             10 RETURN_VALUE

Disassembly of <code object <lambda> at 0x11d6ab270, file "<dis>", line 1>:
  1           0 LOAD_CONST               0 (None)
              2 RETURN_VALUE
>>> count, total = timeit.Timer(make_and_call).autorange()
>>> total / count * 1000000
0.12945385499915574

用一个参数创建一个函数对象并调用它超过 0.1 μs(为我们传入的 None 值加上一个额外的 LOAD_CONST)!这就是 3 个键值对的循环时间和理解时间之间的差异。

你可以把这比作惊讶于一个人用铲子挖一个小洞的速度比反铲挖得快。反铲当然可以快速挖掘，但如果您需要先启动反铲并移动到适当位置，一个有铲子的人可以更快地开始!

除了几个键值对(挖一个更大的洞)之外，函数 create 和 call 成本逐渐消失。此时，dict 理解和显式循环基本上做同样的事情:

• 取出下一个键值对，将它们出栈
• 通过字节码操作调用 dict.__setitem__ 钩子(Hook)，使用堆栈顶部的两项(STORE_SUBSCR 或 MAP_ADD。这不会'不算作'函数调用'，因为它都是在解释器循环中内部处理的。

这与列表推导不同，普通循环版本必须使用 list.append()，涉及属性查找和函数调用每次循环迭代 。列表理解速度优势来自于这种差异；见 Python list comprehension expensive

dict 推导式添加的内容是，在将 b 绑定(bind)到最终字典对象时，只需查找目标字典名称一次。如果目标字典是一个全局而不是一个局部变量，那么理解获胜，放下手:

>>> a = {rs(): rs() for _ in range(1000)}
>>> len(a)
1000
>>> namespace = {}
>>> count, total = timeit.Timer(looped, 'from __main__ import a; global b', globals=namespace).autorange()
>>> (total / count) * 1000000
76.72348440100905
>>> count, total = timeit.Timer(dictcomp, 'from __main__ import a; global b', globals=namespace).autorange()
>>> (total / count) * 1000000
64.72114819916897
>>> len(namespace['b'])
1000

所以只需使用 dict 理解。处理 < 30 个元素的差异太小了，无法在意，而当您生成全局或有更多项目时，dict 理解无论如何都会胜出。