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

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していることがわかります。

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系の場合と同様のことがいえます。