tl;dr
map
が遅いとされるのは関数呼び出しの差があったため
- 現在では(
list
にこだわらなければ) map
は (2017/3/10 11:00追記)イテレータを生成するときは 圧倒的に速い
- 総合的に見ると,式のみのときはfor内包表記が速く,関数のときは
map
が速い様子か
追記が増えてきたので,追記部分も読んでもらえるとよさそう.
はじめに
「Python の map とfor内包表記(リスト内包表記)は結局どっちが速い?」というのは,Python 使いなら誰しもが抱く疑問かと思われる.そういう記事もいっぱいある.
そこで,今回はバイトコードと実行時間を見ることで,どちらが速いのかを検証してみた.
Python2.7.12 の場合
次のようなコードを用意した.どちらも0から9までの自然数の2乗のリストを返す.
初めに逆アセンブルされたバイトコードを出力し,次に timeit
で実行時間を計測する.
from __future__ import print_function
from timeit import timeit
from dis import dis
def b():
return [i ** 2 for i in xrange(10)]
def d():
return map(lambda i: i ** 2, xrange(10))
print('==========b=========')
dis(b)
print('==========d=========')
dis(d)
print('========timeit======')
print('b() ->', timeit('b()', 'def b(): return [i ** 2 for i in xrange(10)]'))
print('d() ->', timeit('d()', 'def d(): return map(lambda i: i ** 2, xrange(10))'))
結果は次の通り.
==========b=========
6 0 BUILD_LIST 0
3 LOAD_GLOBAL 0 (xrange)
6 LOAD_CONST 1 (10)
9 CALL_FUNCTION 1
12 GET_ITER
>> 13 FOR_ITER 16 (to 32)
16 STORE_FAST 0 (i)
19 LOAD_FAST 0 (i)
22 LOAD_CONST 2 (2)
25 BINARY_POWER
26 LIST_APPEND 2
29 JUMP_ABSOLUTE 13
>> 32 RETURN_VALUE
==========d=========
9 0 LOAD_GLOBAL 0 (map)
3 LOAD_CONST 1 (<code object <lambda> at 0x7f1406ac2cb0, file "hoge2.py", line 9>)
6 MAKE_FUNCTION 0
9 LOAD_GLOBAL 1 (xrange)
12 LOAD_CONST 2 (10)
15 CALL_FUNCTION 1
18 CALL_FUNCTION 2
21 RETURN_VALUE
========timeit======
b() -> 1.17981290817
d() -> 1.73737597466
結果から,バイトコードはfor内包の方が長いこと,一方で実行時間は map
のほうが1.5倍ほどかかっていることが分かる.
for内包では計算内容はバイトコードに直接展開されているのに対して, map
ではいったん関数にしてからそれを評価するので,そのオーバーヘッドが大きいのだろう.
ではこの場合はどうか? for内包表記でも関数を呼び出すようにしてみた.
from __future__ import print_function
from timeit import timeit
from dis import dis
def b():
f = lambda x: x ** 2
return [f(i) for i in xrange(10)]
def d():
return map(lambda i: i ** 2, xrange(10))
print('==========b=========')
dis(b)
print('==========d=========')
dis(d)
print('========timeit======')
print('b() ->', timeit('b()', 'def b(): f = lambda x: x ** 2; return [f(i) for i in xrange(10)]'))
print('d() ->', timeit('d()', 'def d(): return map(lambda i: i ** 2, xrange(10))'))
結果は次の通り.
==========b=========
6 0 LOAD_CONST 1 (<code object <lambda> at 0x7f61c40fc930, file "hoge2.py", line 6>)
3 MAKE_FUNCTION 0
6 STORE_FAST 0 (f)
7 9 BUILD_LIST 0
12 LOAD_GLOBAL 0 (xrange)
15 LOAD_CONST 2 (10)
18 CALL_FUNCTION 1
21 GET_ITER
>> 22 FOR_ITER 18 (to 43)
25 STORE_FAST 1 (i)
28 LOAD_FAST 0 (f)
31 LOAD_FAST 1 (i)
34 CALL_FUNCTION 1
37 LIST_APPEND 2
40 JUMP_ABSOLUTE 22
>> 43 RETURN_VALUE
==========d=========
10 0 LOAD_GLOBAL 0 (map)
3 LOAD_CONST 1 (<code object <lambda> at 0x7f61c40a37b0, file "hoge2.py", line 10>)
6 MAKE_FUNCTION 0
9 LOAD_GLOBAL 1 (xrange)
12 LOAD_CONST 2 (10)
15 CALL_FUNCTION 1
18 CALL_FUNCTION 2
21 RETURN_VALUE
========timeit======
b() -> 2.16676402092
d() -> 1.90643000603
なんと,map
のほうが速くなった.
これはmapと内包表記の差ではなく、おそらく関数呼び出しのコストの差が大きいのでしょう。
mapと内包表記の速度の差について - 素数好きの最高技術責任者のブログ
map
は決して遅くない.ただ,条件が不利になったときに遅いのである.
list
を返す場合
次に Python 3.6.0 の場合を考える.map
の返り値はイテレータになったので,list
が欲しい場合はたいていはこのようにして変換するとよい.
from timeit import timeit
from dis import dis
def b():
return [i ** 2 for i in range(10)]
def d():
return list(map(lambda i: i ** 2, range(10)))
print('==========b=========')
dis(b)
print('==========d=========')
dis(d)
print('========timeit======')
print('b() ->', timeit('b()', globals=globals()))
print('d() ->', timeit('d()', globals=globals()))
結果は次の通り.
==========b=========
5 0 LOAD_CONST 1 (<code object <listcomp> at 0x7fa8e6486ae0, file "hoge.py", line 5>)
2 LOAD_CONST 2 ('b.<locals>.<listcomp>')
4 MAKE_FUNCTION 0
6 LOAD_GLOBAL 0 (range)
8 LOAD_CONST 3 (10)
10 CALL_FUNCTION 1
12 GET_ITER
14 CALL_FUNCTION 1
16 RETURN_VALUE
==========d=========
8 0 LOAD_GLOBAL 0 (list)
2 LOAD_GLOBAL 1 (map)
4 LOAD_CONST 1 (<code object <lambda> at 0x7fa8e6449c90, file "hoge.py", line 8>)
6 LOAD_CONST 2 ('d.<locals>.<lambda>')
8 MAKE_FUNCTION 0
10 LOAD_GLOBAL 2 (range)
12 LOAD_CONST 3 (10)
14 CALL_FUNCTION 1
16 CALL_FUNCTION 2
18 CALL_FUNCTION 1
20 RETURN_VALUE
========timeit======
b() -> 4.135329754004488
d() -> 5.330336746992543
map
のほうが1.3倍ほど遅いことが分かった.一方,バイトコードの長さはあまり変わらない.
ここで,条件を少し変えてみる.
次のコードを考える.いずれもイテレータを返すように変更されている.
from timeit import timeit
from dis import dis
def b():
return iter([i ** 2 for i in range(10)])
def d():
return map(lambda i: i ** 2, range(10))
print('==========b=========')
dis(b)
print('==========d=========')
dis(d)
print('========timeit======')
print('b() ->', timeit('b()', globals=globals()))
print('d() ->', timeit('d()', globals=globals()))
結果は次の通り.
==========b=========
5 0 LOAD_GLOBAL 0 (iter)
2 LOAD_CONST 1 (<code object <listcomp> at 0x7f1db4912ae0, file "hoge.py", line 5>)
4 LOAD_CONST 2 ('b.<locals>.<listcomp>')
6 MAKE_FUNCTION 0
8 LOAD_GLOBAL 1 (range)
10 LOAD_CONST 3 (10)
12 CALL_FUNCTION 1
14 GET_ITER
16 CALL_FUNCTION 1
18 CALL_FUNCTION 1
20 RETURN_VALUE
==========d=========
8 0 LOAD_GLOBAL 0 (map)
2 LOAD_CONST 1 (<code object <lambda> at 0x7f1db48d5c90, file "hoge.py", line 8>)
4 LOAD_CONST 2 ('d.<locals>.<lambda>')
6 MAKE_FUNCTION 0
8 LOAD_GLOBAL 1 (range)
10 LOAD_CONST 3 (10)
12 CALL_FUNCTION 1
14 CALL_FUNCTION 2
16 RETURN_VALUE
========timeit======
b() -> 4.343064354005037
d() -> 0.6455312269972637
なんと,この場合は map
のほうが6倍以上速いという結果になった.これはどういうことか.原因はいくつか考えられる.
イテレータから list
への変換が遅い
そもそも list
へ変換する場合と比べて速すぎるので,list
への変換が重い処理であることは間違いないだろう.
for内包表記でも一時関数を作るようになった
b()
のバイトコードのうち,i ** 2
を計算する部分に注目してみよう.
Python 2.7.12 ではこうだった.
19 LOAD_FAST 0 (i)
22 LOAD_CONST 2 (2)
25 BINARY_POWER
一方で Python 3.6.0 ではこうだ.
2 LOAD_CONST 1 (<code object <listcomp> at 0x7ff334fd4ae0, file "hoge.py", line 5>)
4 LOAD_CONST 2 ('b.<locals>.<listcomp>')
6 MAKE_FUNCTION 0
16 CALL_FUNCTION 1
for内包表記の方にも MAKE_FUNCTION
という命令が登場していることが分かる.一時関数を作って,それを呼ぶようにしているのだろう.
追記(2017/3/9 17:10)
map
も遅延評価されているのは知らなかったです.確かにそれならイテレータだけ作る場合は圧倒的に速そう.
id:methane さんにも同じ指摘をいただきました.
追記(2017/3/9 17:22)
以下のコードを Python 3.6.0 で動かす.
from timeit import timeit
from dis import dis
def b():
for a in iter([i ** 2 for i in range(10)]):
continue
def d():
for a in map(lambda i: i ** 2, range(10)):
continue
print('==========b=========')
dis(b)
print('==========d=========')
dis(d)
print('========timeit======')
print('b() ->', timeit('b()', globals=globals()))
print('d() ->', timeit('d()', globals=globals()))
==========b=========
5 0 SETUP_LOOP 32 (to 34)
2 LOAD_GLOBAL 0 (iter)
4 LOAD_CONST 1 (<code object <listcomp> at 0x7f5c2c97aae0, file "hoge3.py", line 5>)
6 LOAD_CONST 2 ('b.<locals>.<listcomp>')
8 MAKE_FUNCTION 0
10 LOAD_GLOBAL 1 (range)
12 LOAD_CONST 3 (10)
14 CALL_FUNCTION 1
16 GET_ITER
18 CALL_FUNCTION 1
20 CALL_FUNCTION 1
22 GET_ITER
>> 24 FOR_ITER 6 (to 32)
26 STORE_FAST 0 (a)
6 28 JUMP_ABSOLUTE 24
30 JUMP_ABSOLUTE 24
>> 32 POP_BLOCK
>> 34 LOAD_CONST 0 (None)
36 RETURN_VALUE
==========d=========
11 0 SETUP_LOOP 28 (to 30)
2 LOAD_GLOBAL 0 (map)
4 LOAD_CONST 1 (<code object <lambda> at 0x7f5c2c93dc90, file "hoge3.py", line 11>)
6 LOAD_CONST 2 ('d.<locals>.<lambda>')
8 MAKE_FUNCTION 0
10 LOAD_GLOBAL 1 (range)
12 LOAD_CONST 3 (10)
14 CALL_FUNCTION 1
16 CALL_FUNCTION 2
18 GET_ITER
>> 20 FOR_ITER 6 (to 28)
22 STORE_FAST 0 (a)
12 24 JUMP_ABSOLUTE 20
26 JUMP_ABSOLUTE 20
>> 28 POP_BLOCK
>> 30 LOAD_CONST 0 (None)
32 RETURN_VALUE
========timeit======
b() -> 4.407405980993644
d() -> 4.945474245003425
for文で回すと map
のほうが遅いという結果になった.
「あらゆる場面で map
のほうが速い」というのは言えなさそうだ.
追記(2017/3/10 10:46)
from __future__ import print_function
from dis import dis
from timeit import timeit
def one():
for b in [abs(x) for x in range(-5, 5)]:
continue
def two():
for b in map(abs, range(-5, 5)):
continue
print("===========one===========")
dis(one)
print("===========two===========")
dis(two)
print('for comprehension:', timeit('for b in [abs(x) for x in range(-5, 5)]: continue'))
print('map:', timeit('for b in map(abs, range(-5, 5)): continue'))
===========one===========
6 0 SETUP_LOOP 30 (to 32)
2 LOAD_CONST 1 (<code object <listcomp> at 0x7f3fb9008ae0, file "fuga.py", line 6>)
4 LOAD_CONST 2 ('one.<locals>.<listcomp>')
6 MAKE_FUNCTION 0
8 LOAD_GLOBAL 0 (range)
10 LOAD_CONST 4 (-5)
12 LOAD_CONST 3 (5)
14 CALL_FUNCTION 2
16 GET_ITER
18 CALL_FUNCTION 1
20 GET_ITER
>> 22 FOR_ITER 6 (to 30)
24 STORE_FAST 0 (b)
7 26 JUMP_ABSOLUTE 22
28 JUMP_ABSOLUTE 22
>> 30 POP_BLOCK
>> 32 LOAD_CONST 0 (None)
34 RETURN_VALUE
===========two===========
10 0 SETUP_LOOP 26 (to 28)
2 LOAD_GLOBAL 0 (map)
4 LOAD_GLOBAL 1 (abs)
6 LOAD_GLOBAL 2 (range)
8 LOAD_CONST 2 (-5)
10 LOAD_CONST 1 (5)
12 CALL_FUNCTION 2
14 CALL_FUNCTION 2
16 GET_ITER
>> 18 FOR_ITER 6 (to 26)
20 STORE_FAST 0 (b)
11 22 JUMP_ABSOLUTE 18
24 JUMP_ABSOLUTE 18
>> 26 POP_BLOCK
>> 28 LOAD_CONST 0 (None)
30 RETURN_VALUE
for comprehension: 1.5314300169993658
map: 0.9652115959906951
これは Python 3.6.0 での結果だが,確かに map
の方が速かった(Python 2.7.12 でも map
が勝っていた).
まとめ
- 「
map
よりfor内包のほうが速い」とは一概に言えない
- 追記(2017/3/9 17:22) どちらも一概に言えない気がしてきた……
- (2017/3/9 17:04追記)
map
では要素が遅延評価されているので高速になっていた
- この速度差は関数呼び出しのコストの差(2017/3/9 17:04追記)もあった
list
に変換する処理はかなり重い
そもそも list
を作るのが重い?
関数を呼ばない計算を適用した結果のリストが欲しいときはfor内包を使い,関数を呼ぶ場合や,(Python3系では)イテレータだけが欲しいときは map
を使う,というふうにするのがよいと思われる.
いつの日にか map
は極限まで最適化されていたのだろう.map は遅延評価イテレータに化けていた.それは速いわけだ.
参考