初心者がpythonでソートアルゴリズム実装して時間計測してみた

f:id:gomta777:20191025033754p:plain

初心者がpythonでソートアルゴリズム実装して時間計測してみた

pythonの時間計測

　ソートアルゴリズムをいくつか実装したので、その計算時間の違いを見るために計算時間を計測してみました。
学生時代を思い出します(笑)
昔のプログラミング言語に比べてコンピュータの時間に対する分解能も上がってますし、計測が簡単になってる気がしました。
数値計算の課題でいくら計測しても計算時間０ｓで出力されて、担当の先生に文句言いに行ったのを思い出します。
結局先生が資料を作った時よりも、使用していたWSの計算能力がかなり上がっていて、課題程度の処理ではすぐ終わってしまい、もっと細かい命令を使わないと時間が図れないという落ちでした(笑)
今回は、これまで実装した、

選択ソート
バブルソート
シェーカーソート
挿入ソート
シェルソート

のデータ数を変化させたときの処理時間を測ってみたいと思います。

時間計測の方法

https://docs.python.org/ja/3/library/time.html
によると、時間計測のための関数はいくつかあるらしいです。
んで、

time.get_clock_info(name)

で、その情報が得られると、ほうほう。
nameに入るのは、

'clock': time.clock()
'monotonic': time.monotonic()
'perf_counter': time.perf_counter()
'process_time': time.process_time()
'thread_time': time.thread_time()
'time': time.time()

とりあえず表示してみればいっかｗ

    print(time.get_clock_info('clock'))
    print(time.get_clock_info('monotonic'))
    print(time.get_clock_info('perf_counter'))
    print(time.get_clock_info('process_time'))
    print(time.get_clock_info('thread_time'))
    print(time.get_clock_info('time'))

実行、っと。

DeprecationWarning: time.clock has been deprecated in Python 3.3 and will be removed from Python 3.8: use time.perf_counter or time.process_time instead
  print(time.get_clock_info('clock'))
namespace(adjustable=False, implementation='QueryPerformanceCounter()', monotonic=True, resolution=1e-07)
namespace(adjustable=False, implementation='GetTickCount64()', monotonic=True, resolution=0.015625)
namespace(adjustable=False, implementation='QueryPerformanceCounter()', monotonic=True, resolution=1e-07)
namespace(adjustable=False, implementation='GetProcessTimes()', monotonic=True, resolution=1e-07)
namespace(adjustable=False, implementation='GetThreadTimes()', monotonic=True, resolution=1e-07)
namespace(adjustable=True, implementation='GetSystemTimeAsFileTime()', monotonic=False, resolution=0.015625)

なんかいっぺーでてきたｗ
ドキュメントに戻ると、

adjustable: 自動 (NTP デーモンによるなど) またはシステム管理者による手動で変更できる場合は True、それ以外の場合は False になります。
implementation: クロック値を取得するために内部で使用している C 関数の名前です。使える値については Clock ID Constants を参照してください。
monotonic: クロック値が後戻りすることがない場合 True が、そうでない場合は False になります。
resolution: クロックの分解能を秒 (float) で表します。

なるほど、resolutionの値を比べてみると

関数名	分解能	備考
time.clock()	resolution=1e-07	python3.8から削除？
time.monotonic()	resolution=0.015625	モノトニッククロックの値 (小数点以下がミリ秒) を返します
time.perf_counter()	resolution=1e-07	パフォーマンスカウンターの値 (float) を返す短時間を正確に計測スリープも計測
time.process_time()	resolution=1e-07	CPU 時間の合計値 (小数点以下はミリ秒) を返すスリープは含まない
time.thread_time()	resolution=1e-07	現在のスレッドのシステムおよびユーザーの CPU 時間の合計値 (小数点以下ありの秒数) を返す
time.time()	resolution=0.015625	エポック秒(UNIX時間)を返す

つまり、time.perf_counter()　または、time_process_time() を使うのがよさそうですね。
って、ところまで読んだところで、ちゃんと検証している方発見(´;ω;｀)

20ms以上の精度を求めるなら「time.perf_counter()」，それ以下で良いなら「time.process_time()」funmatu.wordpress.com

ってことで、計測はtime.perf_counter()を使います。

時間計測用のスクリプト

時間計測の関数を調べていると。。。

一方、time() および sleep() は Unix の同等の関数よりましな精度を持っています。

time --- 時刻データへのアクセスと変換 — Python 3.8.0 ドキュメント

じゃぁ、高精度で測ってみよう！ｗ

import time
import sys
mtime = 0.0
for i in range(10):
    start = time.perf_counter()
    time.sleep(10.0)
    end = time.perf_counter()
    mtime += end - start
    print(end - start)

mtime = mtime/10.0

print(mtime)

１０秒を１０回計測してみます。

1	10.000415
2	9.999896600000001
3	10.000802
4	9.999936600000002
5	10.000314600000003
6	10.000423999999995
7	10.006602
8	10.000490799999994
9	9.999910200000002
10	10.000438899999992
平均	10.000923069999999

うん。いいのか悪いのか、Sleep()の誤差もあるしねw

ソートアルゴリズムの計測

各ソート処理の計算時間を計測するスクリプトを書いていきます。

def sort_sammary(f, datalist, file):
    pd = copy.deepcopy(datalist)
    ttime = 0.0
    i = 0
    while i < 10:
        p = copy.deepcopy(pd)
        starttime = time.perf_counter()
        s = f(p)
        endtime = time.perf_counter()
        interval = endtime - starttime
        ttime += interval
        i = i + 1
        print(interval)
    ttime = ttime/10.0
    file.write(str(s[0])+","+str(s[1])+","+str(ttime)+"\n")
# ソートを10回実行して、実行時間の平均値を出す

ここで、

f	ソートを行う関数（計測される処理）
datalist	ソートされるデータ
file	結果記録用のファイル

です。

def bakasort(datalist):
    change = 0
    comp = 0
    for x in range(0, len(datalist)):
        tmp = x
        for y in range(x, len(datalist)):
            comp += 1
            if datalist[tmp] >= datalist[y]:
                tmp = y
                change += 1
        datalist[x], datalist[tmp] = datalist[tmp], datalist[x]

    return comp, change
# 単純選択ソートの実装

     file = open('test2.txt', 'w')
#valには、ソートされるデータが入っている
    file.write('selection sort\n')
    sort_sammary(bakasort,vals, file)

    file.close()

こんな感じで書くと、計測できるはずですね。

selection sort
500500,6336,0.06867423000000002
shell sort
2693,2693,0.012094429999999979
bubble sort
499500,249107,0.12809839
shaker sort
273034,214243,0.09548444999999997

データは、左から比較回数、交換（代入）回数、処理時間、のつもりです。