初心者がpythonでソートアルゴリズム実装して時間計測してみた
初心者が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
データは、左から比較回数、交換（代入）回数、処理時間、のつもりです。
初心者がpython３とpygameでソートアルゴリズムを可視化してみる【シェーカーソート】
シェーカーソート
シェーカーソートはバブルソートの改良版です。
バブルソートは、並びが良い場合（交換が少なくて済む場合）はソートが早いという特徴があります。
ということは、最悪のケースを考えてみたときに、逆側からバブルソートを行うと早くソートが終わるってことになります。
最悪のケースの逆は最高のケースででしょう、という前提でバブルソートを往復で行うことにより、交換回数を減らそうというものです。
実際比較はほぼすべてに対して行うので、アニメーションの処理回数的には変わらないですが、交換という部分で見ると処理は早くなっているはずです。
所感
実装は当然のように簡単なアルゴリズムだけれども、効果はそれなりにあるかなぁと思いました。
アニメーションではわからないですが、交換回数は減ってるはずです。
【python】python3とpycharmとpygameでテトリス風ゲーム作ってみた 第２回 前半【入門】
【python】python3とpycharmとpygameでテトリス風ゲーム作ってみた 第１回【入門】
python3とpycharmとpygameでテトリス風ゲーム作ってみた
今回の内容
初心者ですが、生意気にもゲームプログラミングにチャレンジしようと思います。
今回は、テトリス風ゲームに挑戦してみました。
今回は一回目なので、
- プロジェクトの作成
- 画像の生成
- 画像の読み込み
- 画像の切り出しと表示
までやってみました。
結果
今回やったところまで、動画にまとめました。
初心者がpythonとpygameでテトリス風ゲームを作ってみた ＃０１
（NEW) 今回使った画像です。良かったらどうぞ
良かったら、チャンネル登録お願いします。
 |
初心者がpython３とpygameでソートアルゴリズムを可視化してみる【シェルソート】
シェルソート
前回に引き続いて調子に乗って別のソートアルゴリズムも試してみました。
まぁありがちですが。。。
あちこち見れば書いてますが、シェルソートは挿入ソートを改良したものです。
挿入ソートは、整列済みに近いデータ列に対しては、割と早い特徴があります。
最悪に近いケース
youtu.be
最善に近いケース
youtu.be
原理を考えれば、そりゃそうですが、かなり違いますね。
なので、この最善に近いケースにデータを近づけながら挿入ソートしたら早くなるんじゃね？
って言うのが、シェルソートの基本的なアイデアです。
アルゴリズム
データをある刻み幅hでグループ分けします。
例えば、
| v = [ 3, 7, 1, 4, 10, 2, 8, 9, 5, 6 ] |
を h=4 で分割すると、
| v1 = [ 3, 10, 5 ] |
| v2 = [ 7, 2, 6 ] |
| v3 = [ 1, 8 ] |
| v4 = [ 4, 9 ] |
のグループに分けられます。
これをそれぞれ、ソートして元の順番でつなぎ合わせます。
①ソート
| v1 = [ 3, 5, 10 ] |
| v2 = [ 2, 6, 7 ] |
| v3 = [ 1, 8 ] |
| v4 = [ 4, 9 ] |
②繋ぎなおし
| v = [ 3, 2, 1, 4, 5, 6, 8, 9, 10, 7] |
なんとなく、昇順に近い並びで並んでいるのがわかります。
次は、刻み幅を h = 2 として同じことを行うと、もう少し完全な昇順に近づきます。
最後に、通常の挿入ソートを行う。という手順です。
python的には、以下のように書いてみました。
（初心者ですので、効率は悪いと思います。）
結果
データの比較、並び替えの処理のみ記録してゆき、アニメーションにしてみました。
初めはランダムだったデータがだんだん昇順に近づいていくのがわかると思います。
最後は、気持ちいい速さで整列されますね。
