前回はテストを書いたので、今回はベンチマークです。対象アルゴリズムは前回同様、以下7つのソートアルゴリズムです。
ベンチマークの書き方
Go言語標準のtestパッケージにあるようにBenchMark<関数名>
の形で関数を書き、引数をb *testing.B
にします。
するとb.N
が自動的に設定され、[0, b.N)
でループし、ベンチマークが計測されます。
前回と同様にBubbleSortを例に取ると以下のようになります。
gistb8368c3fa411a7150eaa662d441979a1
ここで注意が必要なのは、ソート対象を毎回初期化してあげることです。
今回のコードではsliceを渡しているので値渡しではなく、参照渡しとなります。そのため、2回目以降のループではソート済みのsliceをソートすることになり、正しくベンチマークできません。
詳細は「ソート対象の初期化漏れ」にて後述します。
今回やりたいのは他のソートアルゴリズムも含めた比較なので、ソート対象の変数は以下のように別ファイルで定義することにします。
(以下の例の対象は適当です)
gistf3b900057c02e0905169e3e7ebf0aac7
-bench
オプションを付けて実行してみると以下のようになります。
# go test -bench BubbleSort PASS BenchmarkBubbleSort-2 20000000 111 ns/op
2000万回実行し、一回あたり平均で111nsでした。
簡単にベンチマークが書けていいですね。
ディレクトリ内をまとめて実行したい場合はgo test -bench .
とすればOKです。
ハマったところ
ベンチマーク結果の前にハマったところです。
ソート対象の初期化漏れ
ソート対象をsliceとしてソートアルゴリズムに渡していることに注意を払っておらず、ソート済みの配列でベンチマークを取っていました。
毎回、sliceを初期化してあげないと二回目以降のループでソート済みの配列をソートすることになってしまいます。
(前述の通り、値渡しではなく、参照渡しのため)
実際、初期化をせずに行ったベンチマークの結果は以下です。
// ソート対象: {0, 3, 1, 2, 3, 4, 5, 1, 9, 0} # go test -bench . PASS BenchmarkBubbleSort-2 20000000 83.7 ns/op BenchmarkHeapSort-2 3000000 572 ns/op BenchmarkInsertionSort-2 100000000 17.7 ns/op BenchmarkMergeSort-2 2000000 804 ns/op BenchmarkMQuickSort-2 20000000 86.8 ns/op BenchmarkSelectionSort-2 20000000 99.6 ns/op BenchmarkShellSort-2 3000000 528 ns/op
やたらと挿入ソート(InsertionSort)が早くなっていることがわかります。
ちなみにBubbleSortを例としたコードは以下です。
2回目以降はソート対象a
が初期化されず、ソート済み配列となります。
gistc5799874dd907597a619a0f2d60f8c84
ベンチマークのループ内でStartTimer()
とStopTimer()
を呼ぶと遅い
今回の場合、ソース対象を初期化したり、乱数でソート対象を生成してベンチマークを測定します。
その処理はソートアルゴリズムの実行時間とは関係ないので、初期化処理中はベンチマークのタイマーを止めたくなります。
実際、testパッケージにはStartTimer()とStopTimer()が用意されています。
ところがこれはベンチマークループの外で呼ぶべきです。
ベンチマークタイマーの計測開始は、[0, b.N)
のループからではなく、BenchMark<関数名>(b *testing.B)
が実行されたときから、だからです。
stackoverflowですが、Golang benchmarking b.StopTimer() hangs — is it me?
にも書いてあるように、b.N
が10億などとなった場合、ループ中でStartTimer()
やStopTimer()
を呼ぶとベンチマークに膨大な時間を要します。
例えば1回のタイマー停止/開始に要するが100nsだとしても、現実世界では10億回のループ中に100秒が経過してしまいます。
これとは別にStartTimer()
やStopTimer()
を呼ぶコストやベンチマーク対象の時間が乗ってきます。
今回はその回避策として、初期化処理だけのベンチマークを測定し、それに要する時間をソートアルゴリズムのベンチマークから引く方法を取ります。
計測用のコードは以下です。
gist68c61fa11c1371912da88d55ef316e5d
Base(baseline)じゃなくてoffsetで名前統一すべきだった
結果
以下の3パターンをベンチマークしてみます。
- 無印: {0, 3, 1, 2, 3, 4, 5, 1, 9, 0}
- Sorted: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
- RandomizedData: [0, 9]をランダムに並べた順列(重複なし)
# go test -bench . PASS BenchmarkBaseCopy-2 200000000 8.14 ns/op BenchmarkBaseRandom-2 100000 14619 ns/op BenchmarkBubbleSort-2 10000000 111 ns/op BenchmarkBubbleSorted-2 20000000 90.1 ns/op BenchmarkBubbleSortRandomizedData-2 100000 14923 ns/op BenchmarkHeapSort-2 2000000 696 ns/op BenchmarkHeapSorted-2 2000000 615 ns/op BenchmarkHeapSortRandomizedData-2 100000 15420 ns/op BenchmarkInsertionSort-2 10000000 149 ns/op BenchmarkInsertionSorted-2 50000000 23.2 ns/op BenchmarkInsertionSortRandomizedData-2 100000 14848 ns/op BenchmarkMergeSort-2 2000000 884 ns/op BenchmarkMergeSorted-2 2000000 771 ns/op BenchmarkMergeSortRandomizedData-2 100000 15719 ns/op BenchmarkQuickSort-2 10000000 206 ns/op BenchmarkQuickSorted-2 20000000 90.5 ns/op BenchmarkQuickSortRandomizedData-2 100000 14814 ns/op BenchmarkSelectionSort-2 10000000 184 ns/op BenchmarkSelectionSorted-2 20000000 108 ns/op BenchmarkSelectionSortRandomizedData-2 100000 15197 ns/op BenchmarkShellSort-2 2000000 668 ns/op BenchmarkShellSorted-2 3000000 529 ns/op BenchmarkShellSortRandomizedData-2 100000 15568 ns/op
流石に生そのままだと見づらいので、グラフにします。 offsetも引いてあります。
ソート済みの挿入ソート圧倒的ですね。
また要素数が10個程度なのでバブルソートでも有用な感じですね。
せっかくなので要素数を多くしてみましょう。
手でソート対象を10万個も書くのは大変なのでソート済みと乱数のみにします。
結果は以下です。軸は縦横ともにlogスケールにしています。
こちらでもソート済みであれば、挿入ソートの速さが伺えます。
また乱数の結果から、一般にはクイックソートが速いというのもわかりますね。
各ソートアルゴリズムの平均計算量は、以下です。
ソートアルゴリズム | 平均計算量 |
---|---|
バブルソート | O(n2) |
ヒープソート | O(n log n) |
挿入ソート | O(n2) |
マージソート | O(n log n) |
クイックソート | O(n log n) |
選択ソート | O(n2) |
シェルソート | O(n log n) |
乱数のほうを見ると要素数が大きくなるにつれて、O(n2)とではっきりとわかれてくることがわかります。
要素数が小さい範囲では、クイックソートが最速ではないので、実用上は入力の要素数によってソートアルゴリズムを使い分けるのがよさそうです。
最後に
コードはGitHubにもあげてあります。
2017/1/14 修正 Gitではなく、GitHubとの指摘を頂いたので修正しました。