Go言語でソートのベンチマークを計測してみた

はじめに

今回使用するソートアルゴリズムは「バブルソート」「選択ソート」「挿入ソート」「シェルソート」です。ソートアルゴリズムによってどれくらいの差がでるのかベンチマークを計測したら、面白かったので各ソートアルゴリズムの特徴と合わせて紹介したいと思います。
※ 今回使用していない「クイックソート」「マージソート」についてもいつか追記できたらと思います。

ベンチマークの計測について

ベンチマークの計測は go の標準パッケージの testing を使用します。
100,000 個のランダムな数値を持つスライスを生成し、各ソートアルゴリズムで生成されたスライスのソートが完了するまでの時間を計測します。

• 計測に使うPCのスペック

  機種:　MacBook Pro
  プロセッサ名:　Dual-Core Intel Core i5
  プロセッサ速度:　2.3 GHz
  メモリ:    16 GB

• ベンチマーク計測に使用するコード

// 1,000,000 以下の n 個のランダムなスライスを生成する
func GenerateSlice(n int) []int {
    input := make([]int, n)
    for i := range input {
        rand.Seed(time.Now().UnixNano())
        input[i] = rand.Intn(1000000)
    }
    return input
}

// 挿入ソートの場合
// ベンチマークを取るコードは以下の通り
func BenchmarkInsertSort(b *testing.B) {
    // スライスを生成
    input := GenerateSlice(100000)
    // b.ResetTimer()でスライスの生成時間をリセットする
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        // ソートを実行
        InsertSort(input)
    }
}

バブルソート

バブルソートは配列の末尾から隣接する要素を順番に比較し、大小関係が逆だったら入れ替え、順番が逆になっている要素がなくなるまで入れ替えるソートです。
Wikipedia
計算量 O(N^2)

コードは以下の通り

// input は int のスライス
// 例) input := []int{2,7,8,3,1}
func BubbleSort(input []int) []int {
    for i := 0; i < len(input); i++ {
        j := len(input) - 1
        for j > 0 && j > i {
            if input[j] < input[j-1] {
                input[j], input[j-1] = input[j-1], input[j]
            }
            j--
        }
    }
    return input
}

実行結果

BenchmarkBubbleSort-4                  1        14395273888 ns/op              0 B/op          0 allocs/op

バブルソートで100,000の要素を並び替えた場合にかかる時間は 約 14.4 秒

選択ソート

選択ソートは、各計算ステップですべての要素の中から最小値を選択し、先頭からソート済みの部分列を決定していくソートアルゴリズムです。
Wikipedia
計算量 O(N^2)
コードは以下の通り

// input は int のスライス
// 例) input := []int{2,7,8,3,1}
func SelectionSort(input []int) []int {
    for i := 0; i < len(input); i++ {
        minj := i
        for j := i + 1; j < len(input); j++ {
            if input[j] < input[minj] {
                minj = j
            }
        }
        if i != minj {
            input[i], input[minj] = input[minj], input[i]
        }
    }
    return input
}

実行結果

BenchmarkSelectionSort-4               1        4726739202 ns/op               0 B/op          0 allocs/op

選択ソートで100,000の要素を並び替えた場合にかかる時間は 約 4.7 秒

挿入ソート

整列してある要素に追加要素を適切な場所に挿入するソートアルゴリズムで、ほぼ整列されている要素に対しては高速に動作する特徴を持っています。
Wikipedia
計算量 O(N^2)
コードは以下の通り

// input は int のスライス
// 例) input := []int{2,7,8,3,1}
func InsertSort(input []int) []int {
    for i := 1; i < len(input); i++ {
        for j := i - 1; j >= 0; j-- {
            if input[j+1] < input[j] {
                input[j], input[j+1] = input[j+1], input[j]
            } else {
                break
            }
        }
    }
    return input
}

実行結果

BenchmarkInsertSort-4                  1        3211718521 ns/op               0 B/op          0 allocs/op

挿入ソートで100,000の要素を並び替えた場合にかかる時間は 約 3.2 秒

シェルソート

シェルソートは、挿入ソートを応用して、数列を組み合わせたソートアルゴリズムです。数列を組み合わせることで、挿入ソートの「ほぼ整列したデータにおいては高速に動作する」という特徴を活かすことができます。
Wikipedia
計算量 O(N^2) だけど使用する数列によって平均計算量が O(N^1.25)
コードは以下の通り

func ShellSort(input []int) []int {
    var l int = len(input)
    var n int = 0
    sequence := []int{}
    // 数列 sequence[n+1] = 3 * sequence[n] + 1 を生成
    for n < l {
        n = 3*n + 1
        sequence = append(sequence, n)
    }
    // 数列 sequence を降順にする
    sort.Sort(sort.Reverse(sort.IntSlice(sequence)))
    // sequence[n]の分、離れた要素に対して挿入ソートを行う
    for _, g := range sequence {
        for i := g; i < l; i++ {
            for j := i - g; j >= 0; j -= g {
                if input[j] > input[j+g] {
                    input[j], input[j+g] = input[j+g], input[j]
                } else {
                    break
                }
            }
        }
    }
    return input
}

実行結果

BenchmarkShellSort-4                2000            835694 ns/op             296 B/op          7 allocs/op

シェルソートで100,000の要素を並び替えた場合にかかる時間は 約 0.0008 秒

実行結果まとめ

すべてのベンチマークを並べると以下の通りです。

BenchmarkBubbleSort-4                  1        14575993594 ns/op              0 B/op          0 allocs/op
BenchmarkSelectionSort-4               1        4723814506 ns/op               0 B/op          0 allocs/op
BenchmarkInsertSort-4                  1        3247207398 ns/op               0 B/op          0 allocs/op
BenchmarkShellSort-4                2000            835784 ns/op             296 B/op          7 allocs/op

シェルソートが桁違いに高速！！
試しに今回計測に使用した 10 倍の 1,000,000 の要素に対してソートしたところ、シェルソート以外は処理が終わりませんでした。
今回取り上げたシェルソート以外にもクイックソートやマージソートなど高速なソートアルゴリズムがありますので、いつか追記できたらと思います。

さいごに

普段は標準パッケージで用意されているアルゴリズムを使うので、アルゴリズムについて考える機会がなかなかなかったのですが、実際に自分で考えながら実装してみると各ソートアルゴリズムがどういった仕組みでソートしているのか理解でき、学ぶことが多かったです。また、ベンチマークを計測することで、同じサイズの要素を扱う場合でも、パフォーマンスにかなりの差が出てくることがわかりました。今後も、アルゴリズムについても学んで行きたいと思いました。