Nad*_*nes 39 python performance python-3.x python-internals dictionary-comprehension
我不是来自软件/计算机科学背景,但我喜欢用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
Mar*_*ers 70
你的测试输入太小了; 虽然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更快,但只是在这个范围内.键值对的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_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用于b每次迭代,并STORE_SUBSCR在加载的dict中存储键值对.字典理解用于MAP_ADD实现相同的功能,STORE_SUBSCR但不必b每次都加载该名称.
但是只有3次迭代,dict理解必须执行的MAKE_FUNCTION/ CALL_FUNCTIONcombo才是对性能的真正拖累:
>>> 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,然后调用它(我们传入LOAD_CONST的None值为额外值)!这就是3个键值对的循环和理解时序之间的差异.
你可以把这比作惊讶,一个拿着铲子的人可以比反铲挖掘机更快地挖一个小洞.反铲挖掘机当然可以快速挖掘,但是如果你需要开始反铲并首先移动到位,那么带铲子的人可以更快地开始!
除了几个键值对(挖掘更大的洞)之外,功能创建和调用成本逐渐消失.在这一点上,字典理解和显式循环基本上做同样的事情:
dict.__setitem__通过字节码操作调用钩子,使用堆栈中的前两项(STORE_SUBSCR或者MAP_ADD.或者.这不算作'函数调用',因为它在解释器循环中都是内部处理的.这与列表推导不同,其中普通循环版本必须使用list.append(),涉及属性查找,并且函数调用每个循环迭代.列表理解速度优势来自于这种差异; 看看Python列表理解昂贵
dict理解添加的是,当绑定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
所以只需使用字典理解.与处理的<30个元素的差异太小而无法关注,并且当您生成全局或有更多项目时,dict理解无论如何都会胜出.
Kas*_*mvd 17
从某种意义上说,这个问题非常类似于为什么列表理解比附加到列表要快得多？我很久以前就回答过了.但是,这种行为令你感到惊讶的原因显然是因为你的字典太小而无法克服创建新功能框架并在堆栈中推/拉它的成本.要了解更好的让我们在你所拥有的两个片段的皮肤下:
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_FUNCTION操作码,因为它在文档中也说明了在堆栈上推送一个新的函数对象.后来CALL_FUNCTION该呼叫与位置参数一个可调用对象.然后:
将所有参数和可调用对象弹出堆栈,使用这些参数调用可调用对象,并推送可调用对象返回的返回值.
所有这些操作都有它们的成本,但是当字典变大时,将键值项目分配给字典的成本将大于创建一个功能.换句话说,__setitem__从某一点调用字典方法的成本将超过在运行中创建和暂停字典对象的成本.
另外,请注意,当然还有其他多个操作(在这种情况下为OP_CODES)在这个游戏中扮演着至关重要的角色,我认为值得调查并考虑我将把它作为一种练习来实现;).
| 归档时间： |
|
| 查看次数： |
4439 次 |
| 最近记录： |