読者です 読者をやめる 読者になる 読者になる

Golangでソートアルゴリズムのベンチマークを書いてみる

前回はテストを書いたので、今回はベンチマークです。対象アルゴリズムは前回同様、以下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も引いてあります。

f:id:cipepser:20170122171809p:plain

ソート済みの挿入ソート圧倒的ですね。 また要素数が10個程度なのでバブルソートでも有用な感じですね。 せっかくなので要素数を多くしてみましょう。 手でソート対象を10万個も書くのは大変なのでソート済みと乱数のみにします。
結果は以下です。軸は縦横ともにlogスケールにしています。

f:id:cipepser:20170122171811p:plain

f:id:cipepser:20170122171815p:plain

こちらでもソート済みであれば、挿入ソートの速さが伺えます。
また乱数の結果から、一般にはクイックソートが速いというのもわかりますね。

各ソートアルゴリズムの平均計算量は、以下です。

ソートアルゴリズム 平均計算量
バブルソート O(n2)
ヒープソート O(n log n)
挿入ソート O(n2)
マージソート O(n log n)
クイックソート O(n log n)
選択ソート O(n2)
シェルソート O(n log n)

乱数のほうを見ると要素数が大きくなるにつれて、O(n2)と O(n log n)ではっきりとわかれてくることがわかります。
素数が小さい範囲では、クイックソートが最速ではないので、実用上は入力の要素数によってソートアルゴリズムを使い分けるのがよさそうです。

最後に

コードはGitHubにもあげてあります。

2017/1/14 修正 Gitではなく、GitHubとの指摘を頂いたので修正しました。

Reference