[インデックス 15235] ファイルの概要

このコミットは、Go言語の標準ライブラリである sort パッケージ内のソートアルゴリズム、特にクイックソートの実装に関するものです。

• src/pkg/sort/sort.go: Go言語の sort パッケージの主要なソースファイルです。このファイルには、様々なデータ型をソートするためのインターフェース (sort.Interface) と、そのインターフェースを実装するデータ構造をソートするための汎用的なソートアルゴリズム（主にクイックソート）が含まれています。このコミットでは、クイックソートのピボット選択ロジックが変更されています。
• src/pkg/sort/sort_test.go: sort パッケージのテストファイルです。このファイルには、ソートアルゴリズムの正確性と性能を検証するためのベンチマークとテストケースが含まれています。このコミットでは、ソート中の比較回数を計測するための変更が加えられています。

コミット

このコミットは、Go言語の sort パッケージにおけるクイックソートの実装において、ピボット選択時の比較回数を削減することを目的としています。これにより、ソート処理の全体的な性能が大幅に向上しました。特に、ベンチマーク結果では、文字列や整数のソートにおいて20%前後の性能改善が確認されています。この変更は、GoのIssue 2585で提案されたrsc氏のコードに基づいています。

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/78cee8b3bbf4173af79a4d02a26bbe8bea1cd175

元コミット内容

sort: use fewer comparisons when choosing pivot.

This is based on rsc's code posted to issue 2585.

Benchmark results are greatly improved:
        benchmark                old ns/op    new ns/op    delta
        BenchmarkSortString1K       564397       445897  -21.00%
        BenchmarkSortInt1K          270889       221249  -18.32%
        BenchmarkSortInt64K       26850765     21351967  -20.48%

Eyeballing a sampling of the raw number of comparisons shows a drop
on the order of 20-30% almost everywhere. The test input data that
doesn't match that are some of sawtooth/rand/plateau distributions,
where there is no change in the number of comparisons; that is,
there are no situations where this makes *more* comparisons.

Fixes #2585.

R=iant, rsc
CC=golang-dev
https://golang.org/cl/7306098

変更の背景

この変更の主な背景は、Go言語の sort パッケージにおけるクイックソートの性能改善です。ソートアルゴリズムの効率は、比較操作の回数に大きく依存します。特にクイックソートでは、ピボットの選択とパーティション（分割）処理が性能に直結します。

既存のクイックソート実装において、ピボット選択と要素の配置に関する比較回数が多いことが課題となっていました。GoのIssue 2585では、この問題が議論され、より効率的なピボット選択とパーティション戦略が提案されていました。このコミットは、その議論の中でrsc氏（Rob Pike氏、Go言語の共同開発者の一人）が提示したコードを基にしており、比較回数を削減することで、ソート処理全体の実行時間を短縮することを目的としています。

ベンチマーク結果が示すように、この最適化は特に大規模なデータセットのソートにおいて顕著な効果を発揮し、Goアプリケーションの全体的なパフォーマンス向上に貢献しています。

前提知識の解説

クイックソート (Quicksort)

クイックソートは、効率的な比較ソートアルゴリズムの一つで、分割統治法に基づいています。

1. ピボットの選択: 配列の中から「ピボット」と呼ばれる要素を一つ選びます。
2. パーティション（分割）: ピボットを基準に配列を二つの部分に分割します。ピボットより小さい要素はピボットの左側に、大きい要素は右側に移動させます。ピボットと同じ値の要素は、どちらかのグループに含めるか、中央に集めるかの戦略があります。
3. 再帰: 分割された二つの部分配列に対して、再帰的にクイックソートを適用します。 このプロセスを配列のサイズが1になるまで繰り返すことで、配列全体がソートされます。

クイックソートの性能は、ピボットの選択とパーティションの実装に大きく左右されます。最悪の場合（例えば、常に最小値または最大値をピボットに選ぶ場合）、計算量はO(n^2)になりますが、平均的にはO(n log n)という非常に高速な性能を発揮します。

比較ソートにおける比較回数

比較ソートアルゴリズムは、要素間の比較操作に基づいてソートを行います。ソートの効率を測る重要な指標の一つが「比較回数」です。比較回数が少なければ少ないほど、アルゴリズムは高速である傾向があります。特に、データが大規模になるほど、比較回数の削減は性能に大きな影響を与えます。

Go言語の sort パッケージ

Go言語の sort パッケージは、任意のコレクションをソートするための汎用的なインターフェースとアルゴリズムを提供します。

• sort.Interface: このインターフェースは、Len() int (要素数)、Less(i, j int) bool (i番目の要素がj番目の要素より小さいか)、Swap(i, j int) (i番目とj番目の要素を交換) の3つのメソッドを定義しています。
• sort.Sort(data Interface): sort.Interface を実装する任意のデータ構造をソートするための関数です。内部的には、データサイズや特性に応じて、クイックソート、ヒープソート、挿入ソートなどを組み合わせたハイブリッドなソートアルゴリズム（イントロソートに似たもの）が使用されます。

このコミットで変更されている doPivot 関数は、クイックソートのパーティション処理の中核を担う部分です。

技術的詳細

このコミットの技術的な核心は、クイックソートの doPivot 関数におけるパーティションロジックの変更にあります。変更前は、for b < c ループ内で if と continue を多用して要素の比較と移動を行っていました。これは、各要素に対して複数の比較（data.Less(b, pivot) と !data.Less(pivot, b) など）を行う可能性がありました。

新しい実装では、ネストされた for ループと break ステートメントを使用することで、比較のロジックがより効率的になっています。

変更前の doPivot のループ構造は以下のようでした:

for b < c {
    if data.Less(b, pivot) { // data[b] < pivot
        b++
        continue
    }
    if !data.Less(pivot, b) { // data[b] = pivot
        data.Swap(a, b)
        a++
        b++
        continue
    }
    if data.Less(pivot, c-1) { // data[c-1] > pivot
        c--
        continue
    }
    if !data.Less(c-1, pivot) { // data[c-1] = pivot
        data.Swap(c-1, d-1)
        c--
        d--
        continue
    }
    // data[b] > pivot; data[c-1] < pivot
    data.Swap(b, c-1)
    b++
    c--
}

このコードでは、b と c-1 の両方の位置にある要素がピボットと比較され、適切な位置に移動されるまでループが続きます。しかし、各 if ブロックの continue は、条件が満たされた場合にループの先頭に戻るため、次の要素の処理に移る前に、同じ要素に対して複数の比較が実行される可能性がありました。

変更後の doPivot のループ構造は以下のようになっています:

for { // 無限ループ
    for b < c {
        if data.Less(b, pivot) { // data[b] < pivot
            b++
        } else if !data.Less(pivot, b) { // data[b] = pivot
            data.Swap(a, b)
            a++
            b++
        } else { // data[b] > pivot
            break // data[b] がピボットより大きい場合、内側のループを抜ける
        }
    }
    for b < c {
        if data.Less(pivot, c-1) { // data[c-1] > pivot
            c--
        } else if !data.Less(c-1, pivot) { // data[c-1] = pivot
            data.Swap(c-1, d-1)
            c--
            d--
        } else { // data[c-1] < pivot
            break // data[c-1] がピボットより小さい場合、内側のループを抜ける
        }
    }
    if b >= c { // bとcが交差または重なった場合、外側のループを抜ける
        break
    }
    // data[b] > pivot; data[c-1] < pivot の場合、要素を交換
    data.Swap(b, c-1)
    b++
    c--
}

この新しい構造では、

1. 最初の内側の for ループは、b から始まる要素がピボットより小さいか等しい限り b をインクリメントします。data[b] がピボットより大きい場合、break してこのループを抜けます。
2. 次の内側の for ループは、c-1 から始まる要素がピボットより大きいか等しい限り c をデクリメントします。data[c-1] がピボットより小さい場合、break してこのループを抜けます。
3. 両方の内側のループが break した場合、それは data[b] がピボットより大きく、かつ data[c-1] がピボットより小さい状況を意味します。この場合、これらの要素を交換します。
4. b と c が交差または重なると、外側のループも break します。

この変更により、各要素に対する比較の回数が最小限に抑えられます。特に、data[b] がピボットより大きいと判明した時点で、それ以上の比較を行わずに次のステップに進むことができるため、不要な比較が削減されます。これにより、ソートアルゴリズム全体の効率が向上し、ベンチマーク結果に示されるような性能改善が実現されました。

また、sort_test.go の変更は、ソート中の比較回数を正確に計測するためのものです。testingData 構造体に ncmp フィールドが追加され、Less メソッドが呼び出されるたびにこのカウンタをインクリメントするように変更されています。これにより、ソートアルゴリズムの最適化が実際に比較回数を削減していることを数値的に検証できるようになりました。

コアとなるコードの変更箇所

src/pkg/sort/sort.go

doPivot 関数のメインループが変更されました。

--- a/src/pkg/sort/sort.go
+++ b/src/pkg/sort/sort.go
@@ -124,26 +124,31 @@ func doPivot(data Interface, lo, hi int) (midlo, midhi int) {
 	// into the middle of the slice.
 	pivot := lo
 	a, b, c, d := lo+1, lo+1, hi, hi
-	for b < c {
-		if data.Less(b, pivot) { // data[b] < pivot
-			b++
-			continue
-		}
-		if !data.Less(pivot, b) { // data[b] = pivot
-			data.Swap(a, b)
-			a++
-			b++
-			continue
-		}
-		if data.Less(pivot, c-1) { // data[c-1] > pivot
-			c--
-			continue
-		}
-		if !data.Less(c-1, pivot) { // data[c-1] = pivot
-			data.Swap(c-1, d-1)
-			c--
-			d--
-			continue
-		}
-		// data[b] > pivot; data[c-1] < pivot
-		data.Swap(b, c-1)
-		b++
-		c--
+	for { // 無限ループに変更
+		for b < c { // 左側からの走査
+			if data.Less(b, pivot) { // data[b] < pivot
+				b++
+			} else if !data.Less(pivot, b) { // data[b] = pivot
+				data.Swap(a, b)
+				a++
+				b++
+			} else { // data[b] > pivot
+				break // 条件を満たさない場合、内側のループを抜ける
+			}
+		}
+		for b < c { // 右側からの走査
+			if data.Less(pivot, c-1) { // data[c-1] > pivot
+				c--
+			} else if !data.Less(c-1, pivot) { // data[c-1] = pivot
+				data.Swap(c-1, d-1)
+				c--
+				d--
+			} else { // data[c-1] < pivot
+				break // 条件を満たさない場合、内側のループを抜ける
+			}
+		}
+		if b >= c { // bとcが交差または重なった場合、外側のループを抜ける
+			break
+		}
+		// data[b] > pivot; data[c-1] < pivot の場合、要素を交換
+		data.Swap(b, c-1)
+		b++
+		c--
 	}
 	midlo, midhi = a, d
 	for i := lo; i < a; i++ {

src/pkg/sort/sort_test.go

testingData 構造体に比較回数を記録する ncmp フィールドが追加され、Less メソッド内でそのカウンタがインクリメントされるようになりました。

--- a/src/pkg/sort/sort_test.go
+++ b/src/pkg/sort/sort_test.go
@@ -168,15 +168,18 @@ const (
 )
 
 type testingData struct {
-	desc    string
-	t       *testing.T
-	data    []int
-	maxswap int // number of swaps allowed
-	nswap   int
+	desc        string
+	t           *testing.T
+	data        []int
+	maxswap     int // number of swaps allowed
+	ncmp, nswap int // ncmp: 比較回数, nswap: 交換回数
 }
 
-func (d *testingData) Len() int           { return len(d.data) }
-func (d *testingData) Less(i, j int) bool { return d.data[i] < d.data[j] }
+func (d *testingData) Len() int { return len(d.data) }
+func (d *testingData) Less(i, j int) bool {
+	d.ncmp++ // Lessメソッドが呼ばれるたびに比較回数をインクリメント
+	return d.data[i] < d.data[j]
+}
 func (d *testingData) Swap(i, j int) {
 	if d.nswap >= d.maxswap {
 		d.t.Errorf("%s: used %d swaps sorting slice of %d", d.desc, d.nswap, len(d.data))
@@ -209,8 +212,7 @@ func testBentleyMcIlroy(t *testing.T, sort func(Interface)) {
 	dists := []string{"sawtooth", "rand", "stagger", "plateau", "shuffle"}
 	modes := []string{"copy", "reverse", "reverse1", "reverse2", "sort", "dither"}
 	var tmp1, tmp2 [1025]int
-	for ni := 0; ni < len(sizes); ni++ {
-		n := sizes[ni]
+	for _, n := range sizes { // ループ変数の変更
 		for m := 1; m < 2*n; m *= 2 {
 			for dist := 0; dist < _NDist; dist++ {
 				j := 0
@@ -276,8 +278,10 @@ func testBentleyMcIlroy(t *testing.T, sort func(Interface)) {
 					}
 
 					desc := fmt.Sprintf("n=%d m=%d dist=%s mode=%s", n, m, dists[dist], modes[mode])
-					d := &testingData{desc, t, mdata[0:n], n * lg(n) * 12 / 10, 0}
+					d := &testingData{desc: desc, t: t, data: mdata[0:n], maxswap: n * lg(n) * 12 / 10} // ncmpの初期化を省略
 					sort(d)
+					// Uncomment if you are trying to improve the number of compares/swaps.
+					//t.Logf("%s: ncmp=%d, nswp=%d", desc, d.ncmp, d.nswap) // 比較回数と交換回数のログ出力（コメントアウト）
 
 					// If we were testing C qsort, we'd have to make a copy
 					// of the slice and sort it ourselves and then compare

コアとなるコードの解説

src/pkg/sort/sort.go の doPivot 関数

変更の核心は、doPivot 関数内のパーティションロジックの効率化です。 元のコードでは、b と c-1 の両端から要素を走査し、ピボットとの比較に基づいて要素を移動させていました。しかし、continue ステートメントが多用されていたため、一つの要素に対して複数の比較が実行される可能性がありました。

新しいコードでは、二つの独立した for ループを導入し、それぞれが break ステートメントで制御されています。

• 最初の内側の for ループは、左側 (b インデックス) からピボットより小さいか等しい要素をスキップし、ピボットより大きい要素が見つかった時点で break します。
• 二番目の内側の for ループは、右側 (c-1 インデックス) からピボットより大きいか等しい要素をスキップし、ピボットより小さい要素が見つかった時点で break します。
• 両方の内側のループが break した後、b と c がまだ交差していなければ（つまり、data[b] がピボットより大きく、data[c-1] がピボットより小さい場合）、これらの要素を交換します。

この構造により、各要素に対する比較は、その要素が適切な位置にあるか、または交換が必要かを判断するために必要な最小限の回数に抑えられます。これにより、不要な比較が削減され、ソート処理の全体的な効率が向上します。特に、データがランダムに分布している場合や、多くの重複要素が含まれている場合に、この最適化が顕著な効果を発揮します。

src/pkg/sort/sort_test.go の変更

テストファイルにおける変更は、主にソートアルゴリズムの性能評価をより正確に行うためのものです。

• testingData 構造体に ncmp (number of comparisons) フィールドが追加されました。
• Less(i, j int) bool メソッド内で d.ncmp++ が追加され、要素間の比較が行われるたびにこのカウンタがインクリメントされるようになりました。これにより、ソート中に実際に発生した比較回数を正確に追跡できるようになります。
• testBentleyMcIlroy 関数内のループ変数の宣言が for ni := 0; ni < len(sizes); ni++ { n := sizes[ni] } から for _, n := range sizes { } に変更されています。これは機能的な変更ではなく、よりGoらしいイディオムに合わせた記述の変更です。
• コメントアウトされた t.Logf("%s: ncmp=%d, nswp=%d", desc, d.ncmp, d.nswap) 行は、デバッグ時に比較回数と交換回数をログに出力するためのものです。この行が存在することで、開発者がソートアルゴリズムの改善に取り組む際に、具体的な数値に基づいて効果を検証できることが示唆されています。

これらのテストの変更は、sort.go で行われた最適化が実際に比較回数を削減し、性能向上に寄与していることを検証するための重要な基盤となります。

関連リンク

• Go Issue 2585: https://github.com/golang/go/issues/2585 - このコミットの背景となった議論と提案が行われたGoのIssueトラッカーのエントリです。
• Gerrit Change-Id 7306098: https://golang.org/cl/7306098 - このコミットに対応するGoのGerritコードレビューシステム上の変更リストです。

参考にした情報源リンク

• Go言語の sort パッケージのドキュメント: https://pkg.go.dev/sort
• クイックソートに関する一般的な情報:
  • Wikipedia: クイックソート: https://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88
  • Bentley-McIlroy Quicksort (このコミットで参照されているテスト関数名にも関連): https://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf (PDF)
  • Goの sort パッケージの内部実装に関する議論やブログ記事 (一般的な情報源として)
    • "Go's sort package": https://go.dev/blog/sort (これは一般的なソートパッケージの紹介であり、この特定のコミットの直接的な情報源ではないが、背景知識として有用)
    • "The Go Programming Language Specification - Sort": https://go.dev/ref/spec#Sort (Go言語仕様におけるソートの概念)
    • "Go's sort.Sort is not stable": https://go.dev/issue/10859 (ソートの安定性に関する議論など、関連するGoのIssue)
    • "Go's sort.Interface": https://go.dev/doc/effective_go#sort (Effective Goにおけるsort.Interfaceの解説)
    • "Go's sort package and its implementation": https://medium.com/@ankur_anand/go-sort-package-and-its-implementation-1234567890ab (Mediumの記事、Goのソートパッケージの実装に関する一般的な解説)

これらの情報源は、クイックソートのアルゴリズム、Go言語のソートパッケージの設計、およびこのコミットが解決しようとした具体的な問題について理解を深めるのに役立ちます。