はじめに

Go言語はパッケージの定義やソースコードをエディタ上で手軽に読むことができ、それを読むことが大変勉強になります。今回はsortパッケージを深掘りすることで、Go言語の説明をしていきたいと思います。

ソースコード

https://github.com/golang/go/blob/master/src/sort/sort.go

基本文法

go言語は非常にシンプルな言語ですが、その分奥が深いです。それでは早速go言語によるsortを分析してみましょう。まずintの配列によるsortを示します。

var intSlice = []int{8, 9, 4, 2, 6, 1}
sort.Ints(intSlice)
fmt.Println(intSlice) // => []int{1, 2, 4, 6, 8, 9}

使い方は見た目でだいたい想像がつきますね。go言語の良いところは、sortの実装をエディタ上で簡単に確認できるところです。早速sort.Intsの中では何が起こっているか確認してみましょう。

sortパッケージ(抜粋)

sort.go

package sort

// A type, typically a collection, that satisfies sort.Interface can be
// sorted by the routines in this package. The methods require that the
// elements of the collection be enumerated by an integer index.
type Interface interface {
	// Len is the number of elements in the collection.
	Len() int
	// Less reports whether the element with
	// index i should sort before the element with index j.
	Less(i, j int) bool
	// Swap swaps the elements with indexes i and j.
	Swap(i, j int)
}

// ~ 中略 ~ 

// Sort sorts data.
// It makes one call to data.Len to determine n, and O(n*log(n)) calls to
// data.Less and data.Swap. The sort is not guaranteed to be stable.
func Sort(data Interface) {
	n := data.Len()
	quickSort(data, 0, n, maxDepth(n))
}

// ~ 中略 ~ 

// Convenience types for common cases

// IntSlice attaches the methods of Interface to []int, sorting in increasing order.
type IntSlice []int

func (p IntSlice) Len() int           { return len(p) }
func (p IntSlice) Less(i, j int) bool { return p[i] < p[j] }
func (p IntSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }

// Sort is a convenience method.
func (p IntSlice) Sort() { Sort(p) }

// ~ 中略 ~ 

// Convenience wrappers for common cases

// Ints sorts a slice of ints in increasing order.
func Ints(a []int) { Sort(IntSlice(a)) }

これを読み解くと、sort対象となる配列/スライス(引数で渡される)は、Len(), Less(), Swap()という3つの関数を持ったInterfaceというinterfaceを実装している必要があるようです。また、基本的な型(intやstringなど)については、あらかじめそのInterfaceを実装した構造体と専用の関数を用意してくれていて、利用時はsort.Ints(intの配列)というシンプルな書き方が可能になります。

自分で定義した構造体をsortしたい場合はInterfaceの実装を満たせば良いので、以下のような形になります。

package main

import (
	"fmt"
	"sort"
)

// People is the slice of Person
type People []Person

// Person is the struct
type Person struct {
	Name string
	Age  int
}

func main() {
	var data People = []Person{
		{"taro", 3},
		{"jiro", 1},
		{"saburo", 2},
	}
	sort.Sort(data)
	fmt.Println(data) // [{jiro 1} {saburo 2} {taro 3}]
}

// People構造体にInterfaceを実装する。
func (p People) Len() int           { return len(p) }
func (p People) Less(i, j int) bool { return p[i].Age < p[j].Age }
func (p People) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }

このLen(), Less(), Swap()の三つの関数の実装はsortパッケージのIntSclieの実装を真似すれば良いです。

降順にsort

実装をよくよく見るとLessの中の不等号の向きを変えることで降順のsortは実現できそうです。しかしそれだと昇順降順どちらも使いたい場合などに非常に不便な実装となってしまいます。

もちろんsortパッケージではそのための方法が用意してあります。

sort.go(Reverse部分)

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}
}

ここでは、reverse構造体にInterfaceを埋め込み、Less()をオーバーライドしています。つまりsort.Sort(sort.Reverse(data))とすれば降順sortを実現できます。よくできていますね。

このやり方を真似すると、例えば名前や、年齢でsortといったのも構造体の埋め込みによって実現することが可能になります。先のPerson構造体の例だと以下のように記述することでsort方法まで可視化してスマートに実装することが可能です。

package main

import (
	"fmt"
	"sort"
)

// People is the slice of Person
type People []Person

// Person is the struct
type Person struct {
	Name string
	Age  int
}

// ByAge is the struct for age sort
type ByAge struct{ People }

// ByName is the struct for name sort
type ByName struct{ People }


func main() {
	var data People = []Person{
		{"jiro", 1},
		{"ichiro", 3},
		{"saburo", 2},
	}
	sort.Sort(ByName{data})
	fmt.Println(data) // [{ichiro 3} {jiro 1} {saburo 2}]
	sort.Sort(ByAge{data})
	fmt.Println(data) // [{jiro 1} {saburo 2} {ichiro 3}]
}
// Len()およびSwap()は共通で用いることができる
func (p People) Len() int      { return len(p) }
func (p People) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
// Less()のレシーバをそれぞれの構造体にし、具体的に実装を定義
func (p ByAge) Less(i, j int) bool  { return p.People[i].Age < p.People[j].Age }
func (p ByName) Less(i, j int) bool { return p.People[i].Name < p.People[j].Name }

Go言語のソースコードを読み解くことで、

自分で書いていると思いつかないような書き方を目にすることで言語の理解が深まる。
スマートな実装方法の参考になる。
Go言語らしい書き方を自然に習得できる。(例：コメントの書き方、型の扱い方など)

といったメリットがあります。ぜひチャレンジしてみてください。

おまけ

埋め込みについて

go言語では埋め込みによって以下のような挙動を示します。

type Person struct {
	Name string
	Age  int
}
type Person2 struct {
	Person
	Age int
}

func main() {
	a := Person2{
		Person: Person{
			Age:  1,
			Name: "Tetsuji",
		},
		Age: 2,
	}
	fmt.Println(a.Person.Age) // 1
	fmt.Println(a.Age)        // 2
	fmt.Println(a.Name)       // Tetsuji
}

sortアルゴリズムについて

sortパッケージの中ではsortのアルゴリズムの実装までわかります。読むとquickSortがベースで、条件によってheapSortやinsertionSortといったアルゴリズムが呼ばれていることに気づきます。sortについて気になった方は以下の記事をどうぞ。

ソートを極める！〜なぜソートを学ぶのか〜