intro
sort パッケージは slice などをソートするデフォルト実装や、独自の比較ロジックを定めるインタフェースなどが提供されています。
Go のインタフェース、継承による拡張などの考え方的にも面白いので解説メモ。
Sort function
sort パッケージには Sort 関数が定義されている。
そのシグネチャは以下。
func Sort(data Interface)
つまり、ここに sort.Interface インタフェースを満たしたものを渡すと、中で Quick Sort, Heap Sort, Insertion Sort を、条件に応じて使い分け、いい感じに並べ替えてくれる。
Sort Interface
sort.Interface のインタフェースは以下。
(Go では、メソッドを持っていればインタフェースは満たされる)
type Interface interface {
// Len is the number of elements in the collection.
Len() int
// Less returns 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)
}
簡単なソート
自分で作った構造体のソートなんかは、上記メソッドを実装すれば終わる。
package main
import (
"log"
"sort"
)
// 独自の構造体
type Person struct {
Name string
Age uint8
}
// 構造体のスライス
type People []Person
// 以下インタフェースを満たす
func (p People) Len() int {
return len(p)
}
func (p People) Swap(i, j int) {
p[i], p[j] = p[j], p[i]
}
func (p People) Less(i, j int) bool {
return p[i].Name < p[j].Name
}
func main() {
var people People = []Person{
{"John", 22},
{"Tom", 20},
{"Emily", 18},
}
// sort.Sort に渡すだけ
sort.Sort(people) // return はされない点には注意
log.Println(people) // [{Emily 18} {Tom 22} {John 20}]
}
ソート条件が複数欲しい
名前と年齢でそれぞれソートできるようにする。
ソート条件のための型を用意し、もとの構造体を継承させる。
Swap, Len は継承したものを、 Less は子で実装すれば良い。
package main
import (
"log"
"sort"
)
type Person struct {
Name string
Age uint8
}
type People []Person
func (p People) Len() int {
return len(p)
}
func (p People) Swap(i, j int) {
p[i], p[j] = p[j], p[i]
}
// Name でソートするための型
type ByName struct {
People // 継承にあたるもの
// ちなみに
// people People
// などとすると継承にはならない
}
func (b ByName) Less(i, j int) bool {
return b.People[i].Name < b.People[j].Name
}
// Age でソートするための型
type ByAge struct {
People
}
func (b ByAge) Less(i, j int) bool {
return b.People[i].Age < b.People[j].Age
}
func main() {
var people People = []Person{
{"John", 22},
{"Tom", 20},
{"Emily", 18},
}
// 条件に継承させてからソート
sort.Sort(ByName{people})
log.Println(people) // [{Emily 18} {John 22} {Tom 20}]
sort.Sort(ByAge{people})
log.Println(people) // [{Emily 18} {Tom 20} {John 22}]
}
basic sort
int, string, float64 の slice のためには、デフォルトの実装が提供されている。
sort.Interface を満たすための型が提供され、それを継承してソートするラッパー関数も提供されている。
package main
import (
"log"
"sort"
)
func main() {
i := []int{5, 2, 6, 3, 1, 4}
// sort.IntSlice に型変換している
// sort.Interface が満たされる
sort.Sort(sort.IntSlice(i))
log.Println(i) // [1 2 3 4 5 6]
s := []string{"cd", "bc", "ab", "aa"}
// 継承と Sort を両方やってくれる
sort.Strings(s)
log.Println(s) // [aa ab bc cd]
// 同様に sort.Float64s もある。
}
Reverse
sort.Interface を満たしていれば、 Reverse() が使える。
sort.Sort(people)
log.Println(people) // [{Emily 18} {John 20} {Tom 22}]
sort.Sort(sort.Reverse(people)) // reverse
log.Println(people) // [{Tom 22} {John 20} {Emily 18}]
なぜなら、 Reverse の実装は Less を盗んでるだけだから。
package sort
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}
}
Less をユーザランドで決める
http://golang.org/pkg/sort/#example__sortKeys に紹介されているテク。
Less() にあたるものを型の定義から外しておけると便利、みたいなの。
動的に Less を定義することはできないので、内部にもう一つ Struct を作って、
その初期化時に渡した func を、 Less() で使うようなテクニック。
package main
import (
"log"
"sort"
)
type Person struct {
Name string
Age uint8
}
type People []Person
// Less() の型
type By func(p1, p2 Person) bool
func (by By) Sort(people People) {
// ここで struct にメンバとして渡す
ps := PeopleSorter{
people: people,
by: by,
}
sort.Sort(ps)
}
type PeopleSorter struct {
people People
by By
}
func (p PeopleSorter) Len() int {
return len(p.people)
}
func (p PeopleSorter) Swap(i, j int) {
p.people[i], p.people[j] = p.people[j], p.people[i]
}
func (p PeopleSorter) Less(i, j int) bool {
// ここで渡された Less が使う
return p.by(p.people[i], p.people[j])
}
func main() {
var people People = []Person{
{"John", 22},
{"Tom", 20},
{"Emily", 18},
}
// Less() を別途定義
name := func(p1, p2 Person) bool {
return p1.Name < p2.Name
}
age := func(p1, p2 Person) bool {
return p1.Age < p2.Age
}
// ここで渡す
By(name).Sort(people)
log.Println(people)
By(age).Sort(people)
log.Println(people)
}
Sort(people).By(name) だろ JK
できるかどうかやってみた。
Sort() では People の情報しか無いから、
By() の中でもう一つ struct が必要だと思う。実装は汚い。(もっと綺麗になるかも)
package main
import (
"log"
"sort"
)
type Person struct {
Name string
Age uint8
}
type People []Person
func Sort(people People) PeopleSorter {
return PeopleSorter{
people,
}
}
type PeopleSorter struct {
people People
}
func (p PeopleSorter) By(by By) {
s := Sorter{
p,
by,
}
s.sort()
}
type Sorter struct {
PeopleSorter
By
}
func (s Sorter) Len() int {
return len(s.people)
}
func (s Sorter) Swap(i, j int) {
s.people[i], s.people[j] = s.people[j], s.people[i]
}
func (s Sorter) Less(i, j int) bool {
return s.By(s.people[i], s.people[j])
}
func (s Sorter) sort() {
sort.Sort(s)
}
type By func(p1, p2 Person) bool
func main() {
var people People = []Person{
{"John", 22},
{"Tom", 20},
{"Emily", 18},
}
name := func(p1, p2 Person) bool {
return p1.Name < p2.Name
}
age := func(p1, p2 Person) bool {
return p1.Age < p2.Age
}
Sort(people).By(name)
log.Println(people)
Sort(people).By(age)
log.Println(people)
}
一応置いておく
いいかどうかは別として、Sort(people, name) で書いてみた。
package main
import (
"log"
"sort"
)
type Person struct {
Name string
Age uint8
}
type People []Person
type By func(p1, p2 Person) bool
func Sort(people People, by By) {
p := PeopleSorter{
people,
by,
}
sort.Sort(p)
}
type PeopleSorter struct {
People
By
}
func (s PeopleSorter) Len() int {
return len(s.People)
}
func (s PeopleSorter) Swap(i, j int) {
s.People[i], s.People[j] = s.People[j], s.People[i]
}
func (s PeopleSorter) Less(i, j int) bool {
return s.By(s.People[i], s.People[j])
}
func main() {
var people People = []Person{
{"John", 22},
{"Tom", 20},
{"Emily", 18},
}
name := func(p1, p2 Person) bool {
return p1.Name < p2.Name
}
age := func(p1, p2 Person) bool {
return p1.Age < p2.Age
}
Sort(people, name)
log.Println(people)
Sort(people, age)
log.Println(people)
}
力尽きたので Search はまた今度。