> ## Content Index > Fetch the complete content index at: https://www.geekjp.com/llms.txt > Use this file to discover other available public pages before exploring further. # 初心者がpythonでソートアルゴリズム実装して時間計測してみた - URL: https://www.geekjp.com/2019-10-25-022314/ - Published: 2019-10-24T17:23:14.000Z - Updated: 2026-08-01T12:58:50.000Z - Description: 選択・バブル・シェーカー・挿入・シェルソートをPythonで実装し、データ数を変えながら処理時間を計測。時間の測定方法と、各アルゴリズムの実行時間の違いを比較します。 - Author: 工学じじい - Tags: コンピュータサイエンス, 技術, アルゴリズム, Python, プログラミング # 初心者がpythonでソートアルゴリズム実装して時間計測してみた - 初心者がpythonでソートアルゴリズム実装して時間計測してみた - pythonの時間計測 - 時間計測の方法 - 時間計測用のスクリプト - ソートアルゴリズムの計測 - 結果 - 所感 ### pythonの時間計測 ソートアルゴリズムをいくつか実装したので、その計算時間の違いを見るために計算時間を計測してみました。 学生時代を思い出します(笑) 昔のプログラミング言語に比べてコンピュータの時間に対する分解能も上がってますし、計測が簡単になってる気がしました。 数値計算の課題でいくら計測しても計算時間０ｓで出力されて、担当の先生に文句言いに行ったのを思い出します。 結局先生が資料を作った時よりも、使用していたWSの計算能力がかなり上がっていて、課題程度の処理ではすぐ終わってしまい、もっと細かい命令を使わないと時間が図れないという落ちでした(笑) 今回は、これまで実装した、 - 選択ソート - バブルソート - シェーカーソート - 挿入ソート - シェルソート のデータ数を変化させたときの処理時間を測ってみたいと思います。 ### 時間計測の方法 [https://docs.python.org/ja/3/library/time.html](https://docs.python.org/ja/3/library/time.html?ref=geekjp.com) によると、時間計測のための関数はいくつかあるらしいです。 んで、 | 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() とりあえず表示してみればいっかｗ ```python 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')) ``` 実行、っと。 ```python 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()」 ってことで、計測は**time.perf\_counter()**を使います。 ### 時間計測用のスクリプト 時間計測の関数を調べていると。。。 > 一方、time() および sleep() は Unix の同等の関数よりましな精度を持っています。 [time --- 時刻データへのアクセスと変換 — Python 3.8.0 ドキュメント](https://docs.python.org/ja/3/library/time.html?ref=geekjp.com#time.monotonic) じゃぁ、高精度で測ってみよう！ｗ ```python 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 ### ソートアルゴリズムの計測 各ソート処理の計算時間を計測するスクリプトを書いていきます。 ```python3 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 | 結果記録用のファイル | です。 ```python 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 ``` データは、左から比較回数、交換（代入）回数、処理時間、のつもりです。 ### 結果 それぞれのソートでデータ数を増やしながら時間計測をしてみます。 ![f:id:gomta777:20191025021153p:plain](https://www.geekjp.com/content/files/images/import/hatena/2019/10/20191025021153.png "f:id:gomta777:20191025021153p:plain") 表：各ソートアルゴリズムの処理時間 ![f:id:gomta777:20191025021114p:plain](https://www.geekjp.com/content/files/images/import/hatena/2019/10/20191025021114.png "f:id:gomta777:20191025021114p:plain") 図：データ数別の各ソートアルゴリズムの処理時間推移 大体、最悪計算量がO(ｎ^2)のアルゴリズムなので、それに従って計算時間が伸びているのがわかります。 シェルソートのみ最悪O(nlog2n)、最良O(n)、平均O(n^1.25)なので、なぞの安定感を見せていますw ### 所感 今回は、学生時代を思いだして、ソートアルゴリズムの処理時間を計測して比べてみました。 こうしてみると、シェーカーソートとバブルソートのグラフはほぼ重なっており、あまり改良されてるとは言えない結果となりました。 （アルゴリズムなんか間違ってるかもしれないので、後で見直してみないと。。。） 最後に今回のソースコードをすべて載せておきます。 なにか突っ込みどころがあれば、コメントお願いします。 [Gistのソースコードを直接開く](https://gist.github.com/gomta777/e2b4e3d286a98eceb7a6611f40c180a4?ref=geekjp.com)