Golang の sort パッケージ

  • 124
    いいね
  • 0
    コメント
この記事は最終更新日から1年以上が経過しています。

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 はまた今度。