Pythonのlistの処理速度

Python

はじめに

どちらかというと計算機寄りの人間なもので、プログラミング言語の処理速度というのは気になってしょうがない。特に処理時間のオーダーを考えずにプログラム書くなんて考えられない！

特にPythonのlistは結構不可解な部分が多い。名前からしてC++のListコンテナっぽいのだが、メソッドを調べてみると、項目追加は後方に追加するappendと、どこでも追加できるinsertしかない

insertメソッドは、listコンテナならO(n)掛かることは明かなのだが、ひょっとしたら、0に追加するときだけ例外的にO(1)で処理できるのかもしれない、とか考えて、結局計測してみるのが早いという結論に達した。

ベースとなるコード

MAX = 10000000

if __name__ == "__main__":
    l = []
    for i in xrange(MAX):
        l.append(i)

listの前に

range関数で数字を生成するので、xrangeとの比較が必要であろう。という訳で、rangeとxrangeの処理速度を比較した。要素の数は10^7で実験した。結果は、

  • range :: 4.880(s)
  • xrange :: 4.371(s)

という訳で、以後はxrangeを使う。

list要素追加速度1

  • append(i) :: 4.371(s)
  • []演算子(初期化含む) :: 5.647(s)
  • insert(i,i) :: 7.998(s)
  • insert(i,0) :: 5.811(s)

list要素追加速度2

真ん中に追加するとどうなるのっ…ということで、こんな感じに書いてみた。

MAX = 10000000

if __name__ == "__main__":
    l = []
    for i in xrange(MAX/2):
        l.insert(i*2, i)
        l.insert(i*2+1, i)

結果は7.814(s)。計算分のオーバヘッドという認識で良い気がする。

結論

とりあえずappendは早いが、insertも特別遅くないので、どちらもO(1)の範疇に収まってる気がする。それかどちらもO(n)なのか。いずれにせよ、

「良く分かりません（キリッ」

追記

この謎だが、最近解決した。というのも、公式ページのcollections.dequeの項に依ると、

listのinsert(0,i)はO(n)時間掛かる

ということらしい。そーゆーときはdequeを使いましょうねという話だが、listはC++でいうところのvectorと同じ扱いで良いのだろう。