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

• 初心者がpythonでソートアルゴリズム実装して時間計測してみた
  • pythonの時間計測
  • 時間計測の方法
  • 時間計測用のスクリプト
  • ソートアルゴリズムの計測
  • 結果
  • 所感

pythonの時間計測

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

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

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

時間計測の方法

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

で、その情報が得られると、ほうほう。
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.perf_counter()　または、time_process_time() を使うのがよさそうですね。
って、ところまで読んだところで、ちゃんと検証している方発見(´;ω;｀)

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

ってことで、計測は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)

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

うん。いいのか悪いのか、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回実行して、実行時間の平均値を出す

ここで、

です。

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

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

結果

それぞれのソートでデータ数を増やしながら時間計測をしてみます。

表：各ソートアルゴリズムの処理時間

図：データ数別の各ソートアルゴリズムの処理時間推移

大体、最悪計算量がO(ｎ^2)のアルゴリズムなので、それに従って計算時間が伸びているのがわかります。
シェルソートのみ最悪O(nlog2n)、最良O(n)、平均O(n^1.25)なので、なぞの安定感を見せていますw

所感

今回は、学生時代を思いだして、ソートアルゴリズムの処理時間を計測して比べてみました。
こうしてみると、シェーカーソートとバブルソートのグラフはほぼ重なっており、あまり改良されてるとは言えない結果となりました。
（アルゴリズムなんか間違ってるかもしれないので、後で見直してみないと。。。）

最後に今回のソースコードをすべて載せておきます。

なにか突っ込みどころがあれば、コメントお願いします。

Gistのソースコードを直接開く