提问者:小点点

为什么创建字典时,这个循环比字典理解快?


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

问题:给定一个包含这些键和值的字典a,返回一个值为键、键为值的字典。(挑战:在一行中完成此操作)

还有密码

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

共2个答案

匿名用户

您正在使用太小的输入进行测试;虽然与列表理解相比,字典理解对于循环的没有那么大的性能优势,但对于现实的问题大小,它可以而且确实优于循环的,尤其是针对全球名称时。

您的输入仅由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速度更快,但仅限于此规模。由于键值对的数量是原来的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

当考虑两个处理的近100K键值对时,这并不是很大的差别。不过,for循环显然要慢一些。

那么,为什么3个元素的速度差异?因为理解(字典、集合、列表理解或生成器表达式)是作为新函数实现的,调用该函数有一个基本成本,普通循环不必支付。

下面是两个备选方案的字节码反汇编;请注意,对于dict理解,顶级字节码中的MAKE_函数CALL_函数操作码有一个单独的部分说明该函数的作用,实际上这两种方法之间几乎没有区别:

>>> 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进行b,而STORE_SUBSCR将键值对存储在dico加载中。字典理解使用MAP_ADD来实现与STORE_SUBSCR相同的东西,但不必每次都加载那个b名称。

但是只有3次迭代,dict理解必须执行的MAKE_函数/CALL_函数组合才是性能的真正阻力:

>>> 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 cost逐渐消失为虚无。此时,dict理解和显式循环基本上做了相同的事情:

  • 获取下一个键值对,弹出堆栈上的键值对
  • 通过一个字节码操作调用,__setitem__钩子,其中有堆栈上的前两个项目(要么是STORE_SUBSCR,要么是MAP_ADD。这不能算作函数调用,因为它都是在解释器循环中内部处理的。

这与列表理解不同,普通循环版本必须使用list。append(),涉及属性查找和每个循环迭代的函数调用。列表理解速度的优势来自于这种差异;请参见Python列表

当将b绑定到最终字典对象时,目标字典名称只需要查找一次。如果目标字典是一个全局变量而不是一个局部变量,那么理解力就赢了:

>>> 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

所以只要用一个判断理解。与的区别

匿名用户

从某种意义上说,这个问题非常类似于为什么列表理解比附加到列表中要快得多?我很久以前就回答过了。然而,这种行为让您感到惊讶的原因显然是因为您的字典太小,无法克服创建新函数框架并在堆栈中推/拉它的成本。为了更好地理解这一点,让我们看看你有的两个片段:

In [1]: a = {'a':'hi','b':'hey','c':'yo'}
   ...: 
   ...: def reg_loop(a):
   ...:     b = {}
   ...:     for i,j in a.items():
   ...:         b[j]=i
   ...:         

In [2]: def dict_comp(a):
   ...:     b = {v: k for k, v in a.items()}
   ...:     

In [3]: 

In [3]: %timeit reg_loop(a)
529 ns ± 7.89 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [4]: 

In [4]: %timeit dict_comp(a)
656 ns ± 5.39 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [5]: 

In [5]: import dis

In [6]: dis.dis(reg_loop)
  4           0 BUILD_MAP                0
              2 STORE_FAST               1 (b)

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

  6          22 LOAD_FAST                2 (i)
             24 LOAD_FAST                1 (b)
             26 LOAD_FAST                3 (j)
             28 STORE_SUBSCR
             30 JUMP_ABSOLUTE           14
        >>   32 POP_BLOCK
        >>   34 LOAD_CONST               0 (None)
             36 RETURN_VALUE

In [7]: 

In [7]: dis.dis(dict_comp)
  2           0 LOAD_CONST               1 (<code object <dictcomp> at 0x7fbada1adf60, file "<ipython-input-2-aac022159794>", line 2>)
              2 LOAD_CONST               2 ('dict_comp.<locals>.<dictcomp>')
              4 MAKE_FUNCTION            0
              6 LOAD_FAST                0 (a)
              8 LOAD_METHOD              0 (items)
             10 CALL_METHOD              0
             12 GET_ITER
             14 CALL_FUNCTION            1
             16 STORE_FAST               1 (b)
             18 LOAD_CONST               0 (None)
             20 RETURN_VALUE

在第二个反汇编代码(dict comprehension)中,您有一个MAKE_函数opcode,正如文档中所述,它将一个新的函数对象推到堆栈上。以及稍后的CALL\u函数,该函数调用具有位置参数的可调用对象。然后:

从堆栈中弹出所有参数和可调用对象,使用这些参数调用可调用对象,并推送可调用对象返回的返回值。

所有这些操作都有其成本,但是当字典变得更大时,将键值项分配给字典的成本将变得比在引擎盖下创建函数的成本更大。换句话说,从某个点调用字典的__setitem__方法的成本将超过动态创建和挂起字典对象的成本。

此外,请注意,当然还有许多其他操作(在这种情况下OP_CODES)在这个游戏中扮演着至关重要的角色,我认为值得调查和考虑,我将把它作为一种实践来给你;)。