[インデックス 1445] ファイルの概要
このコミットは、Go言語の標準ライブラリであるsortパッケージにおけるインターフェースの設計変更に関するものです。具体的には、src/lib/sort.goとsrc/lib/sort_test.goの2つのファイルが変更されています。
src/lib/sort.goは、Go言語におけるソート機能の核心をなすファイルであり、sort.Interfaceの定義や、そのインターフェースを満たす型（IntArray, FloatArray, StringArrayなど）に対するソートアルゴリズムの実装が含まれています。
src/lib/sort_test.goは、sortパッケージの機能が正しく動作するかを検証するためのテストコードです。
コミット
new sort interface - no structs, just slices.
R=rsc
DELTA=37 (0 added, 7 deleted, 30 changed)
OCL=22330
CL=22342
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/ab331f7a7d4d818cf2d37f0767863464f3fac2e2
元コミット内容
このコミットの目的は、「新しいソートインターフェース — 構造体ではなく、スライスのみを使用する」ことです。これは、sortパッケージが提供するソート可能なデータ型（IntArray, FloatArray, StringArray）の定義を、既存の構造体ベースから直接スライス型を基盤とする形へと変更し、それに伴い関連するメソッドのレシーバやソート関数の呼び出し方を修正するものです。
変更の背景
Go言語の初期段階において、型システムや標準ライブラリの設計はまだ進化の途上にありました。このコミットが行われた2009年1月は、Go言語が一般に公開される前の開発初期段階にあたります。
当時のsortパッケージでは、[]intのような組み込みのスライス型をソート可能にするために、IntArrayのような構造体を定義し、その構造体が内部に[]intを保持する形が取られていました。そして、sort.Interface（Len(), Less(i, j int), Swap(i, j int)メソッドを持つインターフェース）をこの構造体に実装していました。
しかし、この設計にはいくつかの課題がありました。
- 冗長性: スライスをソートするためだけに、余分な構造体でラップする必要がありました。これはコードの記述量を増やし、直感性を損ねる可能性がありました。
- 間接性: ソート対象のスライスにアクセスするために、構造体のフィールドを介する必要がありました（例:
p.data[i]）。これはわずかながらパフォーマンスオーバーヘッドを生む可能性があり、またコードの可読性も低下させました。 - Goのイディオムとの乖離: Go言語はスライスを非常に強力で柔軟な組み込み型として扱います。スライス自体にメソッドをアタッチできる機能（基底型がスライスである新しい型を定義し、その型にメソッドを定義する）があるにもかかわらず、ソートのために構造体でラップするのは、Goの設計思想からすると不自然でした。
このコミットは、これらの課題を解決し、sortパッケージのAPIをよりGo言語のイディオムに沿った、シンプルで直接的なものにするために行われました。具体的には、IntArrayなどを直接スライス型として定義し、その型にsort.Interfaceのメソッドを実装することで、構造体によるラップを不要にしました。
前提知識の解説
このコミットを理解するためには、以下のGo言語の基本的な概念を理解しておく必要があります。
-
スライス (Slice): Go言語におけるスライスは、配列の一部を参照する動的なデータ構造です。長さと容量を持ち、基盤となる配列へのポインタ、長さ、容量の3つの要素で構成されます。スライスは組み込み型であり、非常に柔軟に扱えます。
-
構造体 (Struct): 構造体は、異なる型のフィールドをまとめた複合データ型です。C言語の構造体やC++のクラスに似ていますが、Goの構造体はメソッドを持つことができます。
-
インターフェース (Interface): インターフェースは、メソッドのシグネチャの集合を定義する型です。Goのインターフェースは「暗黙的」に満たされます。つまり、ある型がインターフェースで定義されたすべてのメソッドを実装していれば、その型はそのインターフェースを満たしているとみなされます。明示的な
implementsキーワードは不要です。sortパッケージにおけるSortInterface（現在のsort.Interface）は、以下の3つのメソッドを要求します。Len() int: ソート対象の要素数を返します。Less(i, j int) bool: インデックスiの要素がインデックスjの要素より小さい場合にtrueを返します。Swap(i, j int): インデックスiとjの要素を入れ替えます。
-
メソッド (Method): Go言語では、関数を型に関連付けることができます。これをメソッドと呼びます。メソッドはレシーバ引数（
func (p Type) MethodName(...)のp Typeの部分）を持ち、そのレシーバの型に対して操作を行います。レシーバは値型でもポインタ型でも可能です。 -
型定義と基底型: Goでは、既存の型を基底型として新しい型を定義できます。
type MyInt intのように定義すると、MyIntはintとは異なる新しい型ですが、intのすべての操作を継承します。この新しい型に独自のメソッドを定義できます。このコミットでは、type IntArray []intのように、スライス型を基底型とする新しい型を定義しています。
技術的詳細
このコミットの核心は、sortパッケージがソート可能なデータ型を扱う方法の根本的な変更にあります。
変更前:
IntArray、FloatArray、StringArrayは、それぞれ[]int、[]float、[]stringを内部に持つ構造体として定義されていました。
// 変更前のIntArrayの定義例
export type IntArray struct {
data []int;
}
// 変更前のメソッドレシーバ
func (p *IntArray) Len() int { return len(p.data); }
func (p *IntArray) Less(i, j int) bool { return p.data[i] < p.data[j]; }
func (p *IntArray) Swap(i, j int) { p.data[i], p.data[j] = p.data[j], p.data[i]; }
// 変更前のSortIntsの呼び出し方
export func SortInts(a []int) { Sort(&IntArray{a}); }
この場合、Sort関数に渡す際には、[]int型の変数aをIntArray構造体でラップし、そのポインタを渡す必要がありました（例: &IntArray{a}）。
変更後:
IntArray、FloatArray、StringArrayは、それぞれ[]int、[]float、[]stringを基底型とする新しい型として直接定義されるようになりました。
// 変更後のIntArrayの定義例
export type IntArray []int
// 変更後のメソッドレシーバ
func (p IntArray) Len() int { return len(p); }
func (p IntArray) Less(i, j int) bool { return p[i] < p[j]; }
func (p IntArray) Swap(i, j int) { p[i], p[j] = p[j], p[i]; }
// 変更後のSortIntsの呼び出し方
export func SortInts(a []int) { Sort(IntArray(a)); }
この変更により、IntArray型はそれ自体がスライスとして振る舞うことができるようになり、内部にdataフィールドを持つ必要がなくなりました。メソッドのレシーバも、ポインタレシーバ*IntArrayから値レシーバIntArrayに変更されています。これは、スライスが参照型であるため、値レシーバでも元のスライスの内容を変更できるためです（スライスのヘッダ自体はコピーされますが、ヘッダが指す基盤配列は同じです）。
SortIntsなどのヘルパー関数では、[]int型の引数aをIntArray(a)のように型変換することで、直接IntArray型の値としてSort関数に渡せるようになりました。これにより、余分な構造体の生成とポインタのデリファレンスが不要になります。
テストコードsrc/lib/sort_test.goも、この新しいAPIに合わせて、sort.IntArray{data}のような構造体リテラルを使った初期化から、IntArray(data)のような型変換を使った初期化へと変更されています。
コアとなるコードの変更箇所
src/lib/sort.go
--- a/src/lib/sort.go
+++ b/src/lib/sort.go
@@ -34,7 +34,6 @@ func MedianOfThree(data SortInterface, a, b, c int) {
m0 := b;
m1 := a;
m2 := c;
-
// bubble sort on 3 elements
if data.Less(m1, m0) { data.Swap(m1, m0); }
if data.Less(m2, m1) { data.Swap(m2, m1); }
@@ -135,40 +134,34 @@ export func IsSorted(data SortInterface) bool {
// Convenience types for common cases
-export type IntArray struct {
- data []int;
-}
+export type IntArray []int
-func (p *IntArray) Len() int { return len(p.data); }
-func (p *IntArray) Less(i, j int) bool { return p.data[i] < p.data[j]; }
-func (p *IntArray) Swap(i, j int) { p.data[i], p.data[j] = p.data[j], p.data[i]; }
+func (p IntArray) Len() int { return len(p); }
+func (p IntArray) Less(i, j int) bool { return p[i] < p[j]; }
+func (p IntArray) Swap(i, j int) { p[i], p[j] = p[j], p[i]; }
-export type FloatArray struct {
- data []float;
-}
+export type FloatArray []float
-func (p *FloatArray) Len() int { return len(p.data); }
-func (p *FloatArray) Less(i, j int) bool { return p.data[i] < p.data[j]; }
-func (p *FloatArray) Swap(i, j int) { p.data[i], p.data[j] = p.data[j], p.data[i]; }
+func (p FloatArray) Len() int { return len(p); }
+func (p FloatArray) Less(i, j int) bool { return p[i] < p[j]; }
+func (p FloatArray) Swap(i, j int) { p[i], p[j] = p[j], p[i]; }
-export type StringArray struct {
- data []string;
-}
+export type StringArray []string
-func (p *StringArray) Len() int { return len(p.data); }
-func (p *StringArray) Less(i, j int) bool { return p.data[i] < p.data[j]; }
-func (p *StringArray) Swap(i, j int) { p.data[i], p[j] = p[j], p[i]; }
+func (p StringArray) Len() int { return len(p); }
+func (p StringArray) Less(i, j int) bool { return p[i] < p[j]; }
+func (p StringArray) Swap(i, j int) { p[i], p[j] = p[j], p[i]; }
// Convenience wrappers for common cases
-export func SortInts(a []int) { Sort(&IntArray{a}); }
-export func SortFloats(a []float) { Sort(&FloatArray{a}); }
-export func SortStrings(a []string) { Sort(&StringArray{a}); }
+export func SortInts(a []int) { Sort(IntArray(a)); }
+export func SortFloats(a []float) { Sort(FloatArray(a)); }
+export func SortStrings(a []string) { Sort(StringArray(a)); }
-export func IntsAreSorted(a []int) bool { return IsSorted(&IntArray{a}); }
-export func FloatsAreSorted(a []float) bool { return IsSorted(&FloatArray{a}); }
-export func StringsAreSorted(a []string) bool { return IsSorted(&StringArray{a}); }
+export func IntsAreSorted(a []int) bool { return IsSorted(IntArray(a)); }
+export func FloatsAreSorted(a []float) bool { return IsSorted(FloatArray(a)); }
+export func StringsAreSorted(a []string) bool { return IsSorted(StringArray(a)); }
src/lib/sort_test.go
--- a/src/lib/sort_test.go
+++ b/src/lib/sort_test.go
@@ -14,15 +14,15 @@ import (
func BentleyMcIlroyTests();
-var ints = []int{74, 59, 238, -784, 9845, 959, 905, 0, 0, 42, 7586, -5467984, 7586}
-var floats = []float{74.3, 59.0, 238.2, -784.0, 2.3, 9845.768, -959.7485, 905, 7.8, 7.8}
-var strings = []string{"", "Hello", "foo", "bar", "foo", "f00", "%*&^*&^&", "***"}
+var ints = [...]int{74, 59, 238, -784, 9845, 959, 905, 0, 0, 42, 7586, -5467984, 7586}
+var floats = [...]float{74.3, 59.0, 238.2, -784.0, 2.3, 9845.768, -959.7485, 905, 7.8, 7.8}
+var strings = [...]string{"", "Hello", "foo", "bar", "foo", "f00", "%*&^*&^&", "***"}
export func TestSortIntArray(t *testing.T) {
data := ints;
- a := sort.IntArray{data};
- sort.Sort(&a);
- if !sort.IsSorted(&a) {
+ a := IntArray(data);
+ sort.Sort(a);
+ if !sort.IsSorted(a) {
t.Errorf("sorted %v", ints);
t.Errorf(" got %v", data);
}
@@ -30,9 +30,9 @@ export func TestSortIntArray(t *testing.T) {
export func TestSortFloatArray(t *testing.T) {
data := floats;
- a := sort.FloatArray{data};
- sort.Sort(&a);
- if !sort.IsSorted(&a) {
+ a := FloatArray(data);
+ sort.Sort(a);
+ if !sort.IsSorted(a) {
t.Errorf("sorted %v", floats);
t.Errorf(" got %v", data);
}
@@ -40,9 +40,9 @@ export func TestSortFloatArray(t *testing.T) {
export func TestSortStringArray(t *testing.T) {\n \tdata := strings;\n - a := sort.StringArray{data};\n - sort.Sort(&a);\n - if !sort.IsSorted(&a) {\n + a := StringArray(data);\n + sort.Sort(a);\n + if !sort.IsSorted(a) {\n t.Errorf("sorted %v", strings);\n t.Errorf(" got %v", data);\n }\n```
## コアとなるコードの解説
このコミットにおけるコアとなる変更は、Go言語の型システムとインターフェースの利用方法における重要な進化を示しています。
1. **型定義の簡素化**:
`export type IntArray struct { data []int; }` から `export type IntArray []int` への変更は、`IntArray`がもはや`[]int`をラップする構造体ではなく、`[]int`を基底型とする新しい型であることを意味します。これにより、`IntArray`は`[]int`のすべての特性を継承しつつ、独自のメソッドを持つことができるようになります。これはGo言語における「型エイリアス」とは異なり、新しい独立した型を定義するものです。
2. **メソッドレシーバの変更**:
`func (p *IntArray) Len() int { return len(p.data); }` から `func (p IntArray) Len() int { return len(p); }` への変更は、レシーバがポインタ型から値型になったことを示しています。
Goのスライスは参照型であるため、値レシーバであっても、スライスの要素を変更する操作（例: `Swap`メソッド）は元のスライスに反映されます。これは、スライスのヘッダ（ポインタ、長さ、容量）がコピーされるだけで、ヘッダが指す基盤配列は同じであるためです。これにより、コードがより簡潔になり、ポインタのデリファレンスが不要になります。
3. **ソート関数の呼び出し方の変更**:
`Sort(&IntArray{a});` から `Sort(IntArray(a));` への変更は、ソート対象のスライスを`sort.Interface`に適合させるための手順が大幅に簡素化されたことを示します。
変更前は、`[]int`型の変数`a`を`IntArray`構造体でラップし、その構造体のアドレスを`Sort`関数に渡していました。
変更後は、`[]int`型の変数`a`を直接`IntArray`型に型変換するだけでよくなりました。この型変換は、`a`が指す基盤配列を共有する新しい`IntArray`型のスライスヘッダを作成します。これにより、余分なメモリ割り当てや間接参照が削減され、より効率的でGoらしいコードになりました。
これらの変更は、Go言語がスライスをいかに強力で柔軟なデータ構造として扱っているかを示す良い例です。`sort`パッケージのAPIがより直感的で、Goのイディオムに沿ったものになったことで、開発者はより簡単に組み込みのスライス型をソートできるようになりました。
## 関連リンク
* Go言語の公式ドキュメント: [https://go.dev/doc/](https://go.dev/doc/)
* Go言語の`sort`パッケージ: [https://pkg.go.dev/sort](https://pkg.go.dev/sort) (現在のAPI)
* Go言語の初期のコミット履歴 (GitHub): [https://github.com/golang/go/commits/master?after=ab331f7a7d4d818cf2d37f0767863464f3fac2e2+34&branch=master](https://github.com/golang/go/commits/master?after=ab331f7a7d4d818cf2d37f0767863464f3fac2e2+34&branch=master)
## 参考にした情報源リンク
* Go言語の公式ドキュメント (スライス、構造体、インターフェース、メソッドに関する一般的な情報)
* Go言語の`sort`パッケージの現在の実装 (変更後の設計を理解するため)
* GitHubのコミット履歴 (変更内容の確認)
* Go言語の初期の設計に関する議論やブログ記事 (もしあれば、この変更の背景をさらに深く理解するため)