Help us understand the problem. What is going on with this article?

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

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした