リスト内包表記は速いのか
Python 2.6.6にて、10,000,000個の整数をappendするのに、以下の1,2,3の方法の実行時間を比較しました。
結論だけ言うと、3のリスト内包表記が期待通り高速でした。
追記にも書きましたが、ここで述べた内容はPython2.7系, 3.3系にも適用できます。
- testfunc1: 空リストを用意してappend
- testfunc2: 1 + appendをオブジェクト化
- 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.73 s
- 1.08 s
- 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していることがわかります。
>> 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を実行しています。
>> 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がありません。
>> 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系の場合と同様のことがいえます。