Edited at

Pythonのリスト内包表記の速度

More than 3 years have passed since last update.


リスト内包表記は速いのか

Python 2.6.6にて、10,000,000個の整数をappendするのに、以下の1,2,3の方法の実行時間を比較しました。

結論だけ言うと、3のリスト内包表記が期待通り高速でした。

追記にも書きましたが、ここで述べた内容はPython2.7系, 3.3系にも適用できます。


  1. testfunc1: 空リストを用意してappend

  2. testfunc2: 1 + appendをオブジェクト化

  3. testfunc3: リスト内包表記


準備

# 1. testfunc1: 空リストを用意してappend

def testfunc1(rangelist):
templist = []
for temp in rangelist:
templist.append(temp)

# 2. testfunc2: 1+appendをオブジェクト化
def testfunc2(rangelist):
templist = []
append = templist.append
for temp in rangelist:
append(temp)

# 3. testfunc3: リスト内包表記
def testfunc3(rangelist):
templist = [temp for temp in rangelist]


測定

IPythonの%timeitコマンドを利用して、"3回実行した中で最速のものを抽出" を10回実行し平均実行時間を求めます。

# 10,000,000個の整数からなるリストを作成

>>> rangelist = range(1,10000000)

>>> %timeit -n 10 -r 3 testfunc1(rangelist)

10 loops, best of 3: 1.73 s per loop

>>> %timeit -n 10 -r 3 testfunc2(rangelist)

10 loops, best of 3: 1.08 s per loop

>>> %timeit -n 10 -r 3 testfunc3(rangelist)

10 loops, best of 3: 697 ms per loop


結果


  1. 1.73 s

  2. 1.08 s

  3. 697 ms


結論

実行時間が気になるループの中では、3のようにリスト内包表記を用いるのがよい。

もし仮にリスト内包表記を用いないとしても、2のようにappendメソッドの参照をあらかじめ変数に入れておくほうがよい。

なお、メソッドの参照をあらかじめ変数に入れておくという2の方法は、リスト作成以外のループ実行時間短縮にも使えます。



理由をディスアセンブルして確認

なぜこのような結果になったのかを、Pythonのdisモジュールを用いてそれぞれの関数をディスアセンブルして調べてみます。


ディスアセンブル

>>> import dis

>>> dis.dis(testfunc1)
3 0 BUILD_LIST 0
3 STORE_FAST 1 (templist)

4 6 SETUP_LOOP 27 (to 36)
9 LOAD_FAST 0 (rangelist)
12 GET_ITER
>> 13 FOR_ITER 19 (to 35)
16 STORE_FAST 2 (temp)

5 19 LOAD_FAST 1 (templist)
22 LOAD_ATTR 0 (append)
25 LOAD_FAST 2 (temp)
28 CALL_FUNCTION 1
31 POP_TOP
32 JUMP_ABSOLUTE 13
>> 35 POP_BLOCK
>> 36 LOAD_CONST 0 (None)
39 RETURN_VALUE

>>> dis.dis(testfunc2)
9 0 BUILD_LIST 0
3 STORE_FAST 1 (templist)

10 6 LOAD_FAST 1 (templist)
9 LOAD_ATTR 0 (append)
12 STORE_FAST 2 (append)

11 15 SETUP_LOOP 24 (to 42)
18 LOAD_FAST 0 (rangelist)
21 GET_ITER
>> 22 FOR_ITER 16 (to 41)
25 STORE_FAST 3 (temp)

12 28 LOAD_FAST 2 (append)
31 LOAD_FAST 3 (temp)
34 CALL_FUNCTION 1
37 POP_TOP
38 JUMP_ABSOLUTE 22
>> 41 POP_BLOCK
>> 42 LOAD_CONST 0 (None)
45 RETURN_VALUE

>>> dis.dis(testfunc3)
16 0 BUILD_LIST 0
3 DUP_TOP
4 STORE_FAST 1 (_[1])
7 LOAD_FAST 0 (rangelist)
10 GET_ITER
>> 11 FOR_ITER 13 (to 27)
14 STORE_FAST 2 (temp)
17 LOAD_FAST 1 (_[1])
20 LOAD_FAST 2 (temp)
23 LIST_APPEND
24 JUMP_ABSOLUTE 11
>> 27 DELETE_FAST 1 (_[1])
30 STORE_FAST 3 (templist)
33 LOAD_CONST 0 (None)
36 RETURN_VALUE


解説

上記出力のうち、FOR_ITERからJUMP_ABSOLUTEまでが10,000,000回呼ばれるループです。


testfunc1とtestfunc2の比較

testfunc1では、22 LOAD_ATTRでリストオブジェクトのappendメソッドを呼び出してから、28 CALL_FUNCTIONで実際にappendしていることがわかります。


testfunc1のforループ

        >>   13 FOR_ITER                19 (to 35)

16 STORE_FAST 2 (temp)

5 19 LOAD_FAST 1 (templist)
22 LOAD_ATTR 0 (append)
25 LOAD_FAST 2 (temp)
28 CALL_FUNCTION 1
31 POP_TOP
32 JUMP_ABSOLUTE 13


一方、testfunc2では、LOAD_ATTRがループの外に出ており、ループの中では28 LOAD_FASTでappendメソッドを呼び出してから、34 CALL_FUNCTIONでappendを実行しています。


testfunc2のforループ

        >>   22 FOR_ITER                16 (to 41)

25 STORE_FAST 3 (temp)

12 28 LOAD_FAST 2 (append)
31 LOAD_FAST 3 (temp)
34 CALL_FUNCTION 1
37 POP_TOP
38 JUMP_ABSOLUTE 22


LOAD_ATTRとLOAD_FASTではLOAD_ATTRのほうが時間がかかります。そのため、LOAD_ATTRがループの中にあるtestfunc1より、LOAD_ATTRがループの外にあるtestfunc2のほうが実行時間が短くなります。


testfunc2とtestfunc3の比較

testfunc2では、28 LOAD_FASTでappendメソッドをロードしてから、34 CALL_FUNCTIONで呼び出していました。

一方、testfunc3では、23 LIST_APPENDというリスト専用の処理を呼び出しており、CALL_FUNCTIONがありません。


testfunc3のforループ

        >>   11 FOR_ITER                13 (to 27)

14 STORE_FAST 2 (temp)
17 LOAD_FAST 1 (_[1])
20 LOAD_FAST 2 (temp)
23 LIST_APPEND
24 JUMP_ABSOLUTE 11

CALL_FUNCTIONとLIST_APPENDでは、リスト専用の処理であるLIST_APPENDの呼び出しのほうが高速です(CALL_FUNCTIONは一般的な関数呼び出しのためいろいろ処理があります)。そのため、CALL_FUNCTIONがループの中にあるtestfunc2より、CALL_FUNCTIONがLIST_APPENDに置き換わったtestfunc3のほうが実行時間が短くなります。


参考

この記事は、以下の記事を参考にして書きました。



追記

上述の内容が、Python 2.6だけの話ではないことを確認するために、Python 2.7と3.3でも比較してみました。

なお、マシンを変えたので、上述の実行時間との比較に意味はありません。


結果


Python 2.7.4

>>> %timeit -n 5 testfunc1()

5 loops, best of 3: 974 ms per loop

>>> %timeit -n 5 testfunc2()

5 loops, best of 3: 737 ms per loop

>>> %timeit -n 5 testfunc3()

5 loops, best of 3: 430 ms per loop


Python 3.3.3

>>> %timeit -n 5 testfunc1()

5 loops, best of 3: 1.21 s per loop

>>> %timeit -n 5 testfunc2()

5 loops, best of 3: 815 ms per loop

>>> %timeit -n 5 testfunc3()

5 loops, best of 3: 639 ms per loop

あれ、Python3のほうが遅い・・・。そういえば、Python3では、range関数がリストではなくイテレータを返すようになったようなので、range関数を使わずにリストを作成して実行してみます。


Python 3.3.3 + range関数未使用

>>> %timeit -n 5 testfunc1()

5 loops, best of 3: 1.19 s per loop

>>> %timeit -n 5 testfunc2()

5 loops, best of 3: 611 ms per loop

>>> %timeit -n 5 testfunc3()

5 loops, best of 3: 429 ms per loop

testfunc1についてはまだ怪しいですが、testfunc2とtestfunc3については、Python 2.7.4と同程度の時間で実行できるようになりました。


結論

Python 2.7系とPython3.3系でも1,2,3について上述したPython 2.6系の場合と同様のことがいえます。