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 は決して遅くない．ただ，条件が不利になったときに遅いのである．
Python 3.6.0 の場合
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() 関数から得られるイテレータの段階では、まだ関数 (記事中での lambda i:) が評価されていないと思います。リストへの変換が重いように見えるのは、そのタイミングで関数が評価されているためです。
— もみじあめ (@momijiame) 2017年3月9日
つまり、即時評価されるもの (リスト内包表記) と遅延評価されるもの (map が返すイテレータ) を比べているので、この差が出るということですね
— もみじあめ (@momijiame) 2017年3月9日
例えば、同じく遅延評価されるジェネレータ式なんかと比べると、似たような速度になりますね
— もみじあめ (@momijiame) 2017年3月9日
def b():
return (i ** 2 for i in range(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)
.@utgwkk mapに渡す関数でも違うよなぁ。mapに渡す関数が組み込み関数や標準ライブラリの関数だとmapの方が基本的に速い。mapに渡すのがPythonで書かれた関数の場合(あとリスト内包に渡すのが式で済む場合)だとリスト内包の方が基本的に速い。
— Yamaguchi K. (@quintia) 2017年3月9日
間違った。リスト内包に渡すのが式で済む場合だとリスト内包の方が基本的に速い。でよかった。
— Yamaguchi K. (@quintia) 2017年3月9日
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追記)もあった
- Python3系ではそのコストの差も消えた
listに変換する処理はかなり重いそもそもlistを作るのが重い？
関数を呼ばない計算を適用した結果のリストが欲しいときはfor内包を使い，関数を呼ぶ場合や，(Python3系では)イテレータだけが欲しいときは map を使う，というふうにするのがよいと思われる．
いつの日にか map は遅延評価イテレータに化けていた．それは速いわけだ．map は極限まで最適化されていたのだろう．
