ソートを使う

今回はソート(sort)のお話。

プログラマでソートを知らない人はいないだろうが,一応説明しておくと,あるデータの集合を一定の規則に従って並べ替えることを指す。 日本語では「整列」と呼んだりするらしい。 ソートをアルゴリズムまで言及すると非常に深いテーマになるのだが,今回は標準の sort パッケージの使い方に絞って「こんな感じ」で説明していく。

なお,この記事で紹介するコードは sort パッケージのドキュメントに書かれているものを流用している。 Go 言語のコンパイラ・コードは MIT ライセンスで提供されているのでご注意を。

基本型データ列のソート

sort パッケージでは基本型の int, float64, string についてはソート関数が用意されている。

たとえば {0.055, 0.815, 1.0, 0.107} というデータ列があるとしよう。 これを昇順(小さい値から大きい値へ順に並べること)で並べることを考える。 この場合は sort.Float64s() 関数を使えば簡単である。 コードにするとこんな感じ。

package main

import (
    "fmt"
    "sort"
)

func main() {
    fset := []float64{0.055, 0.815, 1.0, 0.107}
    for _, f := range fset {
        fmt.Printf("%f ", f)
    }
    fmt.Print("\n")
    sort.Float64s(fset)
    for _, f := range fset {
        fmt.Printf("%f ", f)
    }
}

結果はこんな感じになる。

$ go run sort1.go
0.055000 0.815000 1.000000 0.107000
0.055000 0.107000 0.815000 1.000000

では,降順(大きい値から小さい値へ順に並べること)で並べるにはどうすればいいだろう。 これはちょっとだけ面倒くさくなる。

package main

import (
    "fmt"
    "sort"
)

func main() {
    fset := []float64{0.055, 0.815, 1.0, 0.107}
    for _, f := range fset {
        fmt.Printf("%f ", f)
    }
    fmt.Print("\n")
    sort.Sort(sort.Reverse(sort.Float64Slice(fset)))
    for _, f := range fset {
        fmt.Printf("%f ", f)
    }
}

まず sort.Float64Slice[]float64 を示す型である。

type Float64Slice []float64

この型が示すデータ集合を sort.Sort() 関数で並べ替えるのだが,並べ替えの規則を sort.Reverse() 関数で反転させている。 実行結果はこんな感じでちゃんと降順になっているのが分かるだろう。

$ go run sort2.go
0.055000 0.815000 1.000000 0.107000
1.000000 0.815000 0.107000 0.055000

実は最初に出た sort.Float64s() 関数は内部で sort.Sort() 関数を呼んでいる。

// Float64s sorts a slice of float64s in increasing order.
func Float64s(a []float64) { Sort(Float64Slice(a)) }

で, sort.Sort() 関数の内部では sort.Float64Slice に紐付く Len(), Less(), Swap() 各メソッドが呼ばれている。 Len(), Less(), Swap() 各メソッドを持つ interface は以下のように定義されている。

// 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.interface インタフェースを持つ型であれば sort.Sort() 関数でソート可能ということになる。 たとえば以下のオブジェクト集合を考える。

// A Planet defines the properties of a solar system object.
type Planet struct {
    Name     string
    Mass     float64
    Distance float64
}

var planets = []Planet{
    {"Mercury", 0.055, 0.4},
    {"Venus", 0.815, 0.7},
    {"Earth", 1.0, 1.0},
    {"Mars", 0.107, 1.5},
}

Planet オブジェクトの集合に対する sort.interface インタフェースはこんな感じにする1

// ByMass implements sort.Interface for []Planet based on the Mass field.
type ByMass []Planet

func (a ByMass) Len() int           { return len(a) }
func (a ByMass) Less(i, j int) bool { return a[i].Mass < a[j].Mass }
func (a ByMass) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

つまり Mass フィールド値の昇順に並べるわけだ。

全体ではこんな感じになるだろう。

package main

import (
    "fmt"
    "sort"
)

// A Planet defines the properties of a solar system object.
type Planet struct {
    Name     string
    Mass     float64
    Distance float64
}

func (p Planet) String() string {
    return p.Name
}

// ByMass implements sort.Interface for []Planet based on the Mass field.
type ByMass []Planet

func (a ByMass) Len() int           { return len(a) }
func (a ByMass) Less(i, j int) bool { return a[i].Mass < a[j].Mass }
func (a ByMass) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

func main() {
    planets := []Planet{
        {"Mercury", 0.055, 0.4},
        {"Venus", 0.815, 0.7},
        {"Earth", 1.0, 1.0},
        {"Mars", 0.107, 1.5},
    }

    for _, p := range planets {
        fmt.Printf("%v ", p)
    }
    fmt.Print("\n")
    sort.Sort(ByMass(planets))
    for _, p := range planets {
        fmt.Printf("%v ", p)
    }
}

結果は以下の通りで意図通りの動作になっているのが分かるだろう。

$ go run sort3.go
Mercury Venus Earth Mars
Mercury Mars Venus Earth

sort.Slice() 関数を使う場合

slice 限定であるが, sort.Slice() 関数を使えば sort.interface インタフェースを定義しなくてもソートを行うことができる。 sort.Slice() 関数の定義は以下の通り。

func Slice(slice interface{}, less func(i, j int) bool)

実際のコードはこんな感じになる。

package main

import (
    "fmt"
    "sort"
)

// A Planet defines the properties of a solar system object.
type Planet struct {
    Name     string
    Mass     float64
    Distance float64
}

func (p Planet) String() string {
    return p.Name
}

func main() {
    planets := []Planet{
        {"Mercury", 0.055, 0.4},
        {"Venus", 0.815, 0.7},
        {"Earth", 1.0, 1.0},
        {"Mars", 0.107, 1.5},
    }

    for _, p := range planets {
        fmt.Printf("%v ", p)
    }
    fmt.Print("\n")
    sort.Slice(planets, func(i, j int) bool {
        return planets[i].Mass < planets[j].Mass
    })
    for _, p := range planets {
        fmt.Printf("%v ", p)
    }
}

sort.Slice() 関数の第2引数が関数閉包(closure)になっている点に注意2。 これなら第2引数の関数の内容を変えれば任意の規則でソートを行うことができる。

結果は sort.interface インタフェースがある場合と同じく

$ go run sort4.go
Mercury Venus Earth Mars
Mercury Mars Venus Earth

となった。

さて,実際に sort.Slice() 関数を覗いてみよう。

// maxDepth returns a threshold at which quicksort should switch
// to heapsort. It returns 2*ceil(lg(n+1)).
func maxDepth(n int) int {
    var depth int
    for i := n; i > 0; i >>= 1 {
        depth++
    }
    return depth * 2
}

// lessSwap is a pair of Less and Swap function for use with the
// auto-generated func-optimized variant of sort.go in
// zfuncversion.go.
type lessSwap struct {
    Less func(i, j int) bool
    Swap func(i, j int)
}

// Slice sorts the provided slice given the provided less function.
//
// The sort is not guaranteed to be stable. For a stable sort, use
// SliceStable.
//
// The function panics if the provided interface is not a slice.
func Slice(slice interface{}, less func(i, j int) bool) {
    rv := reflect.ValueOf(slice)
    swap := reflect.Swapper(slice)
    length := rv.Len()
    quickSort_func(lessSwap{less, swap}, 0, length, maxDepth(length))
}

reflect.ValueOf() 関数は reflect.Value を取得する関数だ3。 その次の reflect.Swapper() 関数がポイント。 この関数は先程の sort.interface インタフェースでいうところの Swap() 関数に相当するものを返す4。 なのでこんなこともできる。

package main

import (
    "fmt"
    "reflect"
)

func main() {
    s := []int{1, 2, 3}
    fmt.Println(s) // [1 2 3]
    reflect.Swapper(s)(0, 2)
    fmt.Println(s) // [3 2 1]
}

残りの Len() 関数に相当するものは reflect.Value で用意されているし, Less() 関数に相当するものは sort.Slice() 関数の引数として与えられる。 これでソートに必要な3つの関数が揃うわけだ。

ちなみに quickSort_func() 関数は,名前の通り,クイックソートである。 ただしクイックソートでは安定ソートにならないため,安定ソートを実行するための sort.SliceStable() 関数も用意されている。 sort.SliceStable() 関数ではアルゴリズムに挿入ソートを用いる5

ブックマーク

参考図書

photo
プログラミング言語Go (ADDISON-WESLEY PROFESSIONAL COMPUTING SERIES)
Alan A.A. Donovan Brian W. Kernighan 柴田 芳樹
丸善出版 2016-06-20
評価

スターティングGo言語 (CodeZine BOOKS) Go言語によるWebアプリケーション開発 Kotlinスタートブック -新しいAndroidプログラミング Docker実戦活用ガイド グッド・マス ギークのための数・論理・計算機科学

著者のひとりは(あの「バイブル」とも呼ばれる)通称 “K&R” の K のほうである。

reviewed by Spiegel on 2016-07-13 (powered by G-Tools)

photo
数学ガール/乱択アルゴリズム
結城 浩
SBクリエイティブ株式会社 2014-02-14
評価

数学ガール/ゲーデルの不完全性定理 数学ガール/フェルマーの最終定理 数学ガール/ガロア理論 数学ガール 数学ガールの秘密ノート/式とグラフ

工学ガール,リサちゃん登場!

reviewed by Spiegel on 2015/04/19 (powered by G-Tools)


  1. 今回は簡単のため slice を使っているが,データ集合は slice である必要はなく sort.interface インタフェースを持つ任意のオブジェクトであればよい。 [return]
  2. つか, Go 言語の関数は全て関数閉包として動作するんだけどね。 [return]
  3. reflect パッケージについての詳細は割愛する。簡単に言うと, Go 言語において interface 型のインスタンスは型情報と値への参照の2つを保持していて,これに対応するのが reflect.Typereflect.Value である(参考: research!rsc: Go Data Structures: Interfaces)。 [return]
  4. reflect.Swapper() 関数は引数の型が slice であることを前提にしていて, slice でない場合は panic が返る。 [return]
  5. sort.Sort() 関数も同じくクイックソートである。これの安定ソート版が sort.Stable() 関数で同じく挿入ソートを用いている。 [return]