Golangでソートアルゴリズムのテストを書いてみる

背景

先日書いた記事 にてクイックソートのバグをご指摘頂きました。
実装中は適当に入力値を変えてソートがうまくできていることを確認していたものの、実装して満足してしまったためにバグが混入していました。
やはり テストはしっかり書かなくてはいけない と思い、go testしようじゃないかと思い立ちました。

どうやってテストするか

未整列な配列は用意するにしても、いちいちそれを手作業で正しい順番にするのもめんどくさいしですし、それこそバグが混入するかもしれません。
テスト対象と比較すべきは、正しい結果 です。 Go言語標準のsortパッケージを使いましょう。
Godocにもあるように以下のように使用します(l.11)。

gist432ad7127932ecf06acd2978e0dcc2a1

配列同士の比較はreflectパッケージのDeepEqual を使用します。

gistf0ec9f7b3753cda59d84d05d2b631557

今回ソートアルゴリズムについて、テストの入力パターンは[]intに限るとすると go test で出来ること のTipsが有効なのでループでテストさせます。

テストパターンはソートアルゴリズムにまたがり共通なので以下のように別出ししておきます。
パッケージ名はMySortとしました。

gist4a671073d198359db81104618e763db2

BubbleSortでの例は以下です。

gista7dace84aae086af18858a69693ad9c4

gist59f87abcfd8397c552fcaddf79e143ca

テスト結果

では前回実装した以下7つのソートをテストしてみましょう。

実装はgitにあげてあります。

いよいよテストです。
git testを実行する際はMySortディレクトリ内で行います。

# go test
PASS
ok      MySort  0.004s

通ってますね。
ちなみにわざと失敗するケースとしてactualとexpectedの比較の前にactual[0] = 100とすると以下のようになります。
どのように表示するかはif文の中に書けばよいので見やすいよう成形しましょう。

# go test
--- FAIL: TestSort (0.00s)
    BubbleSort_test.go:27:
        expected: [1 2 3 4 5]
        actual: [100 2 3 4 5]
    BubbleSort_test.go:27:
        expected: [1 2 3 4 5]
        actual: [100 2 3 4 5]
    BubbleSort_test.go:27:
        expected: [1 1 2 3 4 5]
        actual: [100 1 2 3 4 5]
    BubbleSort_test.go:27:
        expected: [0 1 2]
        actual: [100 1 2]
    BubbleSort_test.go:27:
        expected: [1 1 1 1 1 1 1 1]
        actual: [100 1 1 1 1 1 1 1]
FAIL
exit status 1
FAIL    MySort  0.007s

最後に

テスト書きましょうというのは、よく聞くものの実はこれまでテストというものを書いたことがありませんでした。
今回、実際に書いてみてどんなものなのかイメージが掴めました。
が、テストパターンが足りてない気配しかないので網羅性難しいですね......。

またせっかくソートを実装しているので次はベンチマークやりたいですね。
テストだとうまく実装できていれば同じ結果になるので比較して楽しみたいところです。

Reference