はじめに
Go言語の標準ライブラリであるsortパッケージの中身を覗き、ソートアルゴリズムの理解を深めたいと思います。
sortパッケージのソートの実装は大きく分けて2つあり、Sort関数とStable関数があります。
Sort関数は、クイックソートをベースとした実装になっており、安定ソートではありません。
[]int,[]float64,[]stringの配列ソートは、それぞれのソート関数、Ints、Float64s、Stringsが内部でsort.Interfaceを満たす型に変更した後、Sort関数を呼んでいます。ソートのキーが一意なので安定ソートでなくとも問題ないです。
一方で、Stable関数は、マージソートをベースとした実装になっており、安定ソートです。こちらもsort.Interfaceを満たす型を渡して利用します。
Go1.8から導入されたSlice関数とSliceStable関数はそれぞれ、Sort関数、Stable関数に対応しており、ソースコードは分かれていますが、それぞれ同様のアルゴリズムで作られています。
2つの関数それぞれの実装を見ていきます。
環境
OS: macOS High Sierra 10.13.6
Go言語: go version go1.10.3 darwin/amd64
sort.Sort関数
// Sortはdataをソートします。
// この関数は、data.Lenメソッドを1回、data.Less関数とdata.Swap関数をO(n*log(n))回呼びます。
// ソートは安定しているとは限りません。
func Sort(data Interface) {
n := data.Len()
quickSort(data, 0, n, maxDepth(n))
}
// maxDepthは、クイックソートをヒープソートに切り替えるしきい値を返します。
// 2*ceil(lg(n+1))を返します。
func maxDepth(n int) int {
var depth int
for i := n; i > 0; i >>= 1 {
depth++
}
return depth * 2
}
SortにてquickSort(data Interface, a, b, maxDepth int)関数が呼ばれます。
第1引数(data)はソート対象配列の全体、第2引数(a)と第3引数(b)はそれぞれソート対象範囲(スライス)の開始と終了のインデックス、第4引数(maxDepth)は、"クイックソートをヒープソートに切り替えるしきい値"です(後述)。
func quickSort(data Interface, a, b, maxDepth int) {
for b-a > 12 { // スライスが12要素以下の場合はシェルソートを使用する
if maxDepth == 0 {
heapSort(data, a, b)
return
}
maxDepth--
mlo, mhi := doPivot(data, a, b)
// 大きな部分問題での再帰を回避することで、
// 最大lg(b-a)のスタック深さが保証されます。
if mlo-a < b-mhi {
quickSort(data, a, mlo, maxDepth)
a = mhi // i.e., quickSort(data, mhi, b)
} else {
quickSort(data, mhi, b, maxDepth)
b = mlo // i.e., quickSort(data, a, mlo)
}
}
if b-a > 1 {
// 6のギャップ数でシェルソートをします。
// これにより、b-a <= 12のケースを単純化された形式で書くことができます。
for i := a + 6; i < b; i++ {
if data.Less(i, i-6) {
data.Swap(i, i-6)
}
}
insertionSort(data, a, b)
}
}
quickSort関数はメインはクイックソートの実装が書かれていますが、heapSort、insertionSortのように異なったソートアルゴリズムが混在していることがわかります。
ソートアルゴリズムを使い分けている理由がソースコード内のコメントで補足的に記載されています。(私が拙訳をしております。)
ヒープソート
ヒープソートのアルゴリズムは書籍やこちらの動画などを参照してください。
対象が巨大な長さの配列の場合、クイックソート時に再帰スタック数も大きくなるためメモリ消費が大きくなるという課題があります。そのため、maxDepth関数で設定した数以上のスタックを持たないようにし、オーバーした場合はヒープソートを実施します。
クイックソートがメモリ使用量O(n)に対し、ヒープソートはメモリ使用量O(1)であり、かつO(nlogn)の平均計算時間なのでヒープソートが採用されているのだと思われます。
| 名称 | 平均計算時間 | 最悪計算時間 | メモリ使用量 | 安定性 | 手法 |
|---|---|---|---|---|---|
| クイックソート | $O(n\log{n})$ | $O(n\log{n})$ | $O(n)$ | X | パーティショニング |
| ヒープソート | $O(n\log{n})$ | $O(n\log{n})$ | $1$ | X | 選択 |
シェルソート(挿入ソート)
シェルソートのアルゴリズムはこちらの動画で楽しく学べます。
ソースコードのコメントにもあるようにクイックソートでの処理内にてスライスの要素数が12以下となった場合、シェルソートを採用しています。これは少ない要素数のときはクイックソートのパフォーマンスが処理時のオーバーヘッド等の理由により良くないためです。
ここでの実装ではGap数が6のケースのみで1度だけシェルソートを実施しています。ソースコードのコメントには「要素数は12以内なので6のみの実施がシンプルになり良い」といった主旨が読み取れますが真意は不明です(見識のある方、コメントをいただけると助かります)。
少要素に強い複数あるアルゴリズムのうち、シェルソートを採用する正確な理由も不明ですが、12要素以下では他のアルゴリズムと特に差は出ないのでStable関数側でも使われている挿入ソートの関数を利用したのかな、と推察しています。
sort.Stable関数
Stable関数のソースコードはここに貼りません。タイトルのリンクを参照してください。
ソースコードのコメントを読むと、Stable関数では、"Stable Minimum Storage Merging by Symmetric Comparisons", in Susanne Albers and Tomasz Radzik, editors, Algorithms - ESA 2004, volume 3221 of Lecture Notes in Computer Science, pages 714-723. Springer, 2004.の論文で発表されたSymmergeアルゴリズムというものを採用しそれを実装しています。
このアルゴリズムの詳細を理解する時間はなかったので省きますが、特徴として、マージソートの弱点である
- メモリ使用量の多さ
- 比較処理の回数が
O(n*log(n)*log(n))と大きい (クイックソートはO(n*log(n)))
この2点を改善できるためSymmergeアルゴリズムにはメリットがあるようです。
このアルゴリズムに関してソースコードのコメントでは
// Notes on stable sorting:
// The used algorithms are simple and provable correct on all input and use
// only logarithmic additional stack space. They perform well if compared
// experimentally to other stable in-place sorting algorithms.
とあるように、Symmergeアルゴリズムは「シンプルでスタック領域も対数的にしか増加利用しない、かつ、他のin-place(※)なソートアルゴリズムよりもパフォーマンスが良いことを確認している」とのことです。
※ in-placeとは入力データのメモリ領域をそのまま出力データに上書きする実装方法のこと。メモリ使用が小さくなることを意味します。
まとめ
Sort関数は以下のソートアルゴリズムを採用していました。
- クイックソート
- ヒープソート ← クイックソートの再帰処理によるメモリ使用過多を防ぐために利用する。
- シェルソート(挿入ソート) ← ソート対象の要素数が小さくなったときクイックソートよりもパフォーマンスが優れるので利用する。
このように、Sort関数は条件に応じてヒープソートとシェルソートを使い分けている点で、要素数の大小に関わらず我々は問題なくSort関数を利用して良さそうです。
Stable関数ではマージソートを改良したアルゴリズムを採用しており、ライブラリ開発者たちが調査と検証をしていることが伺えました。
【おまけ】 Sort関数とStable関数のパフォーマンス比較
Sort関数とStable関数のパフォーマンス検証をGoのベンチマークを使ってやってみたいと思います。
実行環境
プロセッサ: 2.3 GHz Intel Core i5
OS: macOS High Sierra 10.13.6
Go言語: go version go1.10.3 darwin/amd64
実行コード
package main
import (
"testing"
"sort"
"math/rand"
)
const POW = 4 // N=10^POW
func power(base, n int) int {
ret := 1
for ; n > 0; n-- {
ret *= base
}
return ret
}
func prepare(length int) sort.IntSlice {
s := make([]int, length)
for i:= 0; i < length; i++ {
s[i] = rand.Int()
}
return sort.IntSlice(s)
}
func BenchmarkSort(b *testing.B) {
iSlice := prepare(power(10, POW))
b.ResetTimer()
sort.Sort(iSlice)
}
func BenchmarkStable(b *testing.B) {
iSlice := prepare(power(10, POW))
b.ResetTimer()
sort.Stable(iSlice)
}
比較結果
N=10^4
------------------------
BenchmarkSort-4 2000000000 0.00 ns/op
BenchmarkStable-4 2000000000 0.00 ns/op
------------------------
N=10^5
------------------------
BenchmarkSort-4 2000000000 0.01 ns/op
BenchmarkStable-4 2000000000 0.03 ns/op
------------------------
N=10^6
------------------------
goarch: amd64
BenchmarkSort-4 2000000000 0.10 ns/op
BenchmarkStable-4 2000000000 0.33 ns/op
------------------------
N-10^7
------------------------
BenchmarkSort-4 1 2282982953 ns/op
BenchmarkStable-4 1 8700053948 ns/op
------------------------
N-10^8
------------------------
BenchmarkSort-4 1 25782233323 ns/op
BenchmarkStable-4 1 112217026661 ns/op
------------------------
Sort関数の方が3倍ほど優位であり、データ数が増えるごとに差が広がるのも確認できます。効率の良い改良マージソートでもデータ数が巨大になるとクイックソートには太刀打ちできないようです。巨大なオーダーの配列でStable関数を利用予定の際は、安定ソートにする必要が本当にあるかを一度見直した方が良いでしょう。