読者です 読者をやめる 読者になる 読者になる

私が歌川です

@utgwkk が書いている

Python の map とfor内包表記(リスト内包表記)は結局どっちが速い?

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 も遅延評価されているのは知らなかったです.確かにそれならイテレータだけ作る場合は圧倒的に速そう.

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追記)もあった
    • Python3系ではそのコストの差も消えた
  • list に変換する処理はかなり重い
  • そもそも list を作るのが重い?

関数を呼ばない計算を適用した結果のリストが欲しいときはfor内包を使い,関数を呼ぶ場合や,(Python3系では)イテレータだけが欲しいときは map を使う,というふうにするのがよいと思われる.

いつの日にか map は極限まで最適化されていたのだろう.map は遅延評価イテレータに化けていた.それは速いわけだ.

参考