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

このコミットは、Go言語の標準ライブラリである sort パッケージに、ソート順序を反転させる Reverse 関数を追加するものです。これにより、既存の sort.Sort 関数と組み合わせて、任意の sort.Interface を実装するデータ構造を逆順にソートする機能が提供されます。

コミット

commit d4cfe28885317c16a4db0ffde30f30a79b063da8
Author: Miek Gieben <miek@miek.nl>
Date:   Fri Feb 1 08:44:45 2013 -0800

    sort: add Reverse as a function
    
    This updates: https://golang.org/cl/6909059/
    Fixes #4511.
    
    R=minux.ma, rsc
    CC=golang-dev
    https://golang.org/cl/6932054

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

https://github.com/golang/go/commit/d4cfe28885317c16a4db0ffde30f30a79b063da8

元コミット内容

このコミットは、Go言語の sort パッケージに Reverse 関数を追加し、ソート可能なデータ構造を逆順にソートする機能を提供します。具体的には、sort.Interface をラップして Less メソッドの比較ロジックを反転させる reverse 型を導入しています。これにより、sort.Sort(sort.Reverse(data)) のように記述することで、昇順ソートの代わりに降順ソートを実行できるようになります。

変更は以下のファイルに及びます。

• src/pkg/sort/example_test.go: Reverse 関数の使用例が追加されました。
• src/pkg/sort/sort.go: reverse 型と Reverse 関数の実装が追加されました。
• src/pkg/sort/sort_test.go: Reverse 関数のテストケースが追加されました。

変更の背景

この変更は、Go言語のIssue #4511「sort.Reverse function」に対応するものです。このIssueでは、Goの sort パッケージに逆順ソートを容易に行うためのヘルパー関数 Reverse を追加することが提案されていました。

Goの sort パッケージは、sort.Interface インターフェース（Len(), Less(i, j int), Swap(i, j int) の3つのメソッドを持つ）を実装する任意の型をソートできるように設計されています。しかし、逆順にソートしたい場合、ユーザーは Less メソッドを自分で実装し直すか、ソート後に手動で要素を反転させる必要がありました。これは冗長であり、エラーの原因となる可能性がありました。

Reverse 関数を導入することで、既存の sort.Interface 実装を再利用しつつ、簡単に逆順ソートを実現できるようになります。これは、Goの標準ライブラリが提供するユーティリティ関数を充実させ、開発者の利便性を向上させるための典型的な改善です。

前提知識の解説

Go言語の sort パッケージ

Go言語の sort パッケージは、スライスやユーザー定義のコレクションをソートするための機能を提供します。ソートの対象となるデータ型は、sort.Interface インターフェースを実装する必要があります。

sort.Interface は以下の3つのメソッドを定義します。

• Len() int: コレクションの要素数を返します。
• Less(i, j int) bool: インデックス i の要素がインデックス j の要素よりも小さい（ソート順で前にある）場合に true を返します。
• Swap(i, j int): インデックス i と j の要素を入れ替えます。

例えば、整数のスライス []int をソートする場合、sort.IntSlice 型が sort.Interface を実装しており、これを sort.Sort 関数に渡すことでソートが実行されます。

package main

import (
	"fmt"
	"sort"
)

func main() {
	s := []int{5, 2, 6, 3, 1, 4}
	sort.Sort(sort.IntSlice(s)) // 昇順ソート
	fmt.Println(s) // 出力: [1 2 3 4 5 6]
}

インターフェースの埋め込み (Embedded Interfaces)

Go言語では、構造体内にインターフェースを埋め込むことができます。これにより、埋め込まれたインターフェースのメソッドを、その構造体が直接実装しているかのように呼び出すことができます。これは、既存のインターフェースの動作を拡張したり、ラップしたりする際に非常に便利です。

このコミットでは、reverse 構造体が sort.Interface を埋め込んでいます。

type reverse struct {
	Interface // sort.Interface を埋め込み
}

これにより、reverse 型のインスタンスは、埋め込まれた Interface の Len() と Swap() メソッドを自動的に「継承」します。Less() メソッドだけを独自に実装し直すことで、ソートロジックを反転させることができます。

技術的詳細

このコミットの核となるのは、sort.Interface をラップして Less メソッドの動作を反転させる新しい型 reverse と、そのインスタンスを生成する Reverse 関数です。

reverse 型の定義

type reverse struct {
	// This embedded Interface permits Reverse to use the methods of
	// another Interface implementation.
	Interface
}

reverse 型は、sort.Interface を匿名フィールドとして埋め込んでいます。これにより、reverse 型のインスタンスは、埋め込まれた Interface の Len() と Swap() メソッドを自動的に満たします。つまり、reverse 型自体も sort.Interface を実装していることになります。

Less メソッドの実装

// Less returns the opposite of the embedded implementation's Less method.
func (r reverse) Less(i, j int) bool {
	return r.Interface.Less(j, i)
}

reverse 型の Less メソッドは、埋め込まれた Interface の Less メソッドを呼び出しますが、引数の i と j を入れ替えて渡します。 通常の Less(i, j) は「i が j より小さいか？」を判定します。 Less(j, i) は「j が i より小さいか？」を判定します。 例えば、昇順ソートでは a < b なら true を返しますが、降順ソートでは a > b なら true を返したい。Less(j, i) は実質的に !(Less(i, j)) と同じ効果を持ち、比較結果を反転させます。これにより、ソートアルゴリズムは逆順に要素を配置するようになります。

Reverse 関数の実装

// Reverse returns the reverse order for data.
func Reverse(data Interface) Interface {
	return &reverse{data}
}

Reverse 関数は、引数として sort.Interface を受け取り、その Interface を埋め込んだ reverse 型のポインタを返します。この返された *reverse 型も sort.Interface を満たしているため、sort.Sort 関数に直接渡すことができます。

使用例

s := []int{5, 2, 6, 3, 1, 4} // unsorted
sort.Sort(sort.Reverse(sort.IntSlice(s)))
fmt.Println(s) // Output: [6 5 4 3 2 1]

この例では、まず []int スライスを sort.IntSlice にキャストして sort.Interface を満たすようにします。次に、sort.Reverse 関数でこれをラップし、Less メソッドの比較ロジックを反転させた新しい sort.Interface を生成します。最後に、この新しいインターフェースを sort.Sort 関数に渡すことで、スライスが降順にソートされます。

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

src/pkg/sort/sort.go

--- a/src/pkg/sort/sort.go
+++ b/src/pkg/sort/sort.go
@@ -197,6 +197,22 @@ func Sort(data Interface) {
 	quickSort(data, 0, n, maxDepth)
 }
 
+type reverse struct {
+	// This embedded Interface permits Reverse to use the methods of
+	// another Interface implementation.
+	Interface
+}
+
+// Less returns the opposite of the embedded implementation's Less method.
+func (r reverse) Less(i, j int) bool {
+	return r.Interface.Less(j, i)
+}
+
+// Reverse returns the reverse order for data.
+func Reverse(data Interface) Interface {
+	return &reverse{data}
+}
+
 // IsSorted reports whether data is sorted.
 func IsSorted(data Interface) bool {
 	n := data.Len()

src/pkg/sort/example_test.go

--- a/src/pkg/sort/example_test.go
+++ b/src/pkg/sort/example_test.go
@@ -15,3 +15,10 @@ func ExampleInts() {
 	fmt.Println(s)
 	// Output: [1 2 3 4 5 6]
 }
+
+func ExampleReverse() {
+	s := []int{5, 2, 6, 3, 1, 4} // unsorted
+	sort.Sort(sort.Reverse(sort.IntSlice(s)))
+	fmt.Println(s)
+	// Output: [6 5 4 3 2 1]
+}

src/pkg/sort/sort_test.go

--- a/src/pkg/sort/sort_test.go
+++ b/src/pkg/sort/sort_test.go
@@ -92,6 +92,23 @@ func TestSortLarge_Random(t *testing.T) {
 	}
 }
 
+func TestReverseSortIntSlice(t *testing.T) {
+	data := ints
+	data1 := ints
+	a := IntSlice(data[0:])
+	Sort(a)
+	r := IntSlice(data1[0:])
+	Sort(Reverse(r))
+	for i := 0; i < len(data); i++ {
+		if a[i] != r[len(data)-1-i] {
+			t.Errorf("reverse sort didn't sort")
+		}
+		if i > len(data)/2 {
+			break
+		}
+	}
+}
+
 func BenchmarkSortString1K(b *testing.B) {
 	b.StopTimer()
 	for i := 0; i < b.N; i++ {

コアとなるコードの解説

sort.go の変更

• reverse 構造体: sort.Interface を埋め込むことで、Len() と Swap() メソッドを自動的に継承し、sort.Interface を満たすようにします。
• reverse.Less(i, j int) bool メソッド: このメソッドが reverse 型のソートロジックの核心です。埋め込まれた Interface の Less メソッドを Less(j, i) の形で呼び出すことで、元の比較結果を論理的に反転させます。これにより、ソートアルゴリズムは「大きいものが小さいものより前にある」と解釈し、結果として降順ソートが実現されます。
• Reverse(data Interface) Interface 関数: このヘルパー関数は、ユーザーが sort.Interface を渡すだけで、reverse 型のインスタンスを生成し、それを sort.Interface として返す役割を担います。これにより、sort.Sort(sort.Reverse(mySlice)) のような簡潔な記述が可能になります。

example_test.go の変更

• ExampleReverse() 関数: Reverse 関数の典型的な使用方法を示す例が追加されました。sort.IntSlice を sort.Reverse でラップし、sort.Sort に渡すことで、整数スライスが降順にソートされることを示しています。これはドキュメントとしても機能し、ユーザーが新しい機能の使い方を理解するのに役立ちます。

sort_test.go の変更

• TestReverseSortIntSlice() 関数: Reverse 関数の機能が正しく動作するかを確認するための単体テストが追加されました。このテストでは、まず通常の昇順ソートを行い、その結果と Reverse 関数を使った降順ソートの結果を比較しています。具体的には、昇順ソートされた配列の i 番目の要素が、降順ソートされた配列の len(data)-1-i 番目の要素と等しいことを確認しています。これにより、逆順ソートが期待通りに行われていることを検証しています。

これらの変更により、Go言語の sort パッケージはより柔軟になり、逆順ソートのニーズに効率的に対応できるようになりました。

関連リンク

• Go Issue #4511: sort.Reverse function - https://github.com/golang/go/issues/4511
• Gerrit Change 6909059: sort: add Reverse as a function (最初の提案) - https://golang.org/cl/6909059/
• Gerrit Change 6932054: sort: add Reverse as a function (最終的なコミット) - https://golang.org/cl/6932054

参考にした情報源リンク

• Go言語 sort パッケージのドキュメント: https://pkg.go.dev/sort
• Go言語のインターフェースに関する公式ドキュメントやチュートリアル (一般的な知識として)
• Go言語のテストに関する公式ドキュメントやチュートリアル (一般的な知識として)
• Gitのコミットログと差分表示の一般的な理解
• GitHubのコミットページ構造の一般的な理解
• Gerrit Code Review の一般的な理解
• Go言語の標準ライブラリの設計原則に関する一般的な知識