前々回に挿入ソート、前回にマージソートを実装した。今回は、実装したアルゴリズムの計算時間を実測して比較してみよう。

計算時間を計測するプログラム

早速、次の通り実装した。 timeit モジュールを使って、挿入ソート (insertion_sort) とマージソート (better_merge_sort) の実行時間を計測する。また、ソートする配列サイズを増やしていき実行時間がどう変わるかを確認する。

import timeit
from insertion_sort import insertion_sort
from merge_sort import better_merge_sort


TIMEIT_COUNT = 10
DATA_SIZES = range(100, 10001, 100)


def timeit_sort(sort_func, size):
    import numpy as np

    t = timeit.timeit(
        'sort_func(numbers)',
        'numbers = np.random.randint(255, size=size).tolist()',
        number=TIMEIT_COUNT,
        globals=locals()) / TIMEIT_COUNT

    return t


if __name__ == "__main__":
    print('\t'.join(['配列サイズ', '挿入ソート', 'マージソート']))
    for ds in DATA_SIZES:
        time_insertion = timeit_sort(insertion_sort, ds)
        time_merge = timeit_sort(better_merge_sort, ds)
        print('\t'.join(
            [str(x) for x in [ds, time_insertion, time_merge]]))

6行 : 計測回数
- 今回は各配列サイズについて10回計測し、その平均時間を計測結果とした。
7行 : 計測する配列サイズのリスト
- 今回は配列サイズを100から10000まで100刻みで増やしていく。
10-19行 : timeitによりソートアルゴリズムの計測を行う関数
- 引数について
  - 引数 sort_func にはソートアルゴリズムの関数を指定する。
  - 引数 size にはソートする配列サイズを指定する。
- timeit.timeit 関数
  - timeit.timeit の詳細はtimeit --- 小さなコード断片の実行時間計測 — Python 3.7.3 ドキュメントを参照。
  - 14行 : 計測対象となる命令。
  - 15行 : 計測の前処理。今回は数値の配列を宣言している。
    - 実装したソートを行う関数は、引数として与えた配列をソートする。
    - そのため、ソート毎に新たに数値の配列を生成する必要がある。
    - そうしなければソート済みの配列をさらにソートすることになる。
  - 16行 : 計測回数。
  - 17行 globals=locals() : 名前空間の指定
    - locals()を与えることでtimeit_sort 内の変数を行で使用できるようになる。
  - 17行 / TIMEIT_COUNT : 除算による平均時間の計算
- 19行 : 計測時間を返す
22-28行 : 配列サイズを変更して時間を計測
- 配列サイズを変更し、timeit_sortを呼び出す。
- 挿入ソート、マージソートについて時間計測し、文字列として出力する。

実行結果

実行結果は次の通り。

配列サイズ      挿入ソート      マージソート
100     3.676482799093628e-05   0.00018183132787456116
200     0.00013714634930878794  0.00046948608697807147
300     0.00026777773604795205  0.0008129140354521281
400     0.0004745192149240157   0.0008881810147858993
500     0.0007302123341271366   0.001120905697321993
600     0.0011119891407070967   0.0013245046648409447
700     0.0014507927432003576   0.0016004835890647772
800     0.002322724674871432    0.001769157247435979
900     0.002495894934859316    0.001994345012489565
1000    0.002764873467929904    0.0024118646921475807
(中略)
9000    0.22939420812163008     0.02326656646398817
9100    0.2297974204325058      0.02356484955418523
9200    0.23373858955403648     0.023853091937364467
9300    0.248510743428767       0.02403282825766695
9400    0.251492194691609       0.024942879107587145
9500    0.2581470117910598      0.025470948759947022
9600    0.2683966574920674      0.026154100070336028
9700    0.27378018822876554     0.0297308145210593
9800    0.26768251539894405     0.02650677671077233
9900    0.2821606783941107      0.026735081438309292
10000   0.2847239712554753      0.026817348808796736

グラフ化すると次の通り。

f:id:akaoto:20190609160831p:plain — 挿入ソートとマージソートの計算時間比較

挿入ソートの計算時間は $\theta(n^{2})$ であった。そのとおりで、配列サイズの二次関数となっていることがわかる。一方で、マージソートの計算時間は $\theta(n\log_{2}n)$ であり、挿入ソートより非常に計算時間が短いことも確認できる。また、配列の長さが長くなるとその差はどんどん開いていくため、効率のよいアルゴリズムというのは大事というわけだ。