人工知能系のプログラムは、実はとても計算量が多いので、プログラムが効率がよいかどうか常に気にしておく必要がある。
時間を計測するのに、自分で、対象範囲の前後でシステムの時間を読み取り、差を取るということで求めることはできる。でも、そんなことをしなくても、Pythonには時間計測の仕組みが用意されている。
以下では、リストに追加するときに、insertとappendでどのくらい差が出るかを計測してみたものだ。計測する部分は、それぞれ関数にまとめてある。
import timeit
def insfirstfunc(n):
a = []
for i in range(n):
a.insert(0,i)
def inslastfunc(n):
a = []
for i in range(n):
a.insert(len(a),i)
def apdfunc(n):
a = []
for i in range(n):
a.append(i)
for i in range(1000,10001,1000):
t = timeit.Timer("insfirstfunc(i)","from __main__ import insfirstfunc,i")
t1 = t.timeit(number=1000)
t = timeit.Timer("inslastfunc(i)","from __main__ import inslastfunc,i")
t2 = t.timeit(number=1000)
t = timeit.Timer("apdfunc(i)","from __main__ import apdfunc,i")
t3 = t.timeit(number=1000)
print("%6d t1=%10.6f t2=%10.6f t3=%10.6f" % (i,t1,t2,t3))
timeitをインポートしておいて、timeit.Timerでタイマーを生成している。
Timerの第１引数に実行したいことを文字列で書く。ここには、変数などが含まれてもよい。
第２引数に、”from main import”の後ろにインポートしたいものを並べておけば大丈夫なようだ。
Timerを作ったら、実際の時間計測を作ったTimerオブジェクトのtimeitメソッドで計測できる。引数に number=繰り返し回数 を指定することができる。とくに短時間の計測の場合、システムの状態に大きく依存してしまうので、なんども繰り返し実行すると誤差が減る。
詳細はマニュアルを参照して欲しい。
iPython3 で実行してみた結果を以下に示す。
In [1]: %run timeit
1000 t1= 0.395643 t2= 0.204404 t3= 0.073373
2000 t1= 1.217943 t2= 0.423568 t3= 0.153751
3000 t1= 2.477653 t2= 0.639693 t3= 0.238761
4000 t1= 4.179113 t2= 0.859387 t3= 0.316046
5000 t1= 6.390812 t2= 1.081363 t3= 0.400768
6000 t1= 9.033100 t2= 1.297038 t3= 0.481604
7000 t1= 12.073041 t2= 1.506441 t3= 0.561811
8000 t1= 15.538109 t2= 1.731817 t3= 0.645874
9000 t1= 20.012774 t2= 2.071590 t3= 0.771902
10000 t1= 24.719389 t2= 2.313333 t3= 0.866832
appendが一番高速で、insertで最後に挿入するのは３倍程度遅くなる。
そして、insertで最初に挿入するのは、O(n**2)のオーダーで遅くなっているのが分かる。
appendで済むなら、insertを使うのはやめるべきなのだ。
timeitを使うことで、big-O がどの程度か簡単に調べることができる。
＃人気の記事
＃タグ
