tl;dr
mapが遅いとされるのは関数呼び出しの差があったため- 現在では(
listにこだわらなければ)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)
@utgwkk map() 関数から得られるイテレータの段階では、まだ関数 (記事中での lambda i:) が評価されていないと思います。リストへの変換が重いように見えるのは、そのタイミングで関数が評価されているためです。
— もみじあめ (@momijiame) 2017年3月9日
@utgwkk つまり、即時評価されるもの (リスト内包表記) と遅延評価されるもの (map が返すイテレータ) を比べているので、この差が出るということですね
— もみじあめ (@momijiame) 2017年3月9日
@utgwkk 例えば、同じく遅延評価されるジェネレータ式なんかと比べると、似たような速度になりますね
— もみじあめ (@momijiame) 2017年3月9日
def b():
return (i ** 2 for i in range(10))
map も遅延評価されているのは知らなかったです．確かにそれならイテレータだけ作る場合は圧倒的に速そう．
id:methane さんにも同じ指摘をいただきました．
まとめ
- 「
mapよりfor内包のほうが速い」とは一概に言えない - (2017/3/9 17:04追記)
mapでは要素が遅延評価されているので高速になっていた - この速度差は関数呼び出しのコストの差(2017/3/9 17:04追記)もあった
- Python3系ではそのコストの差も消えた
listに変換する処理はかなり重いそもそもlistを作るのが重い？
関数を呼ばない計算を適用した結果のリストが欲しいときはfor内包を使い，関数を呼ぶ場合や，(Python3系では)イテレータだけが欲しいときは map を使う，というふうにするのがよいと思われる．
いつの日にか map は遅延評価イテレータに化けていた．それは速いわけだ．map は極限まで最適化されていたのだろう．