帰ってきた「しっぽのさきっちょ」

ソートを使う — プログラミング言語 Go

今回はソート(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 を Sorter と呼び,以下のように定義されている。

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

オブジェクトのソート

つまり Sorter インタフェースを持つ型であれば 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 オブジェクトの集合に対する Sorter インタフェースはこんな感じにする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() 関数を使えば Sorter インタフェースを定義しなくてもソートを行うことができる。 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引数の関数の内容を変えれば任意の規則でソートを行うことができる。

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

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

となった。

ブックマーク

参考図書

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 である必要はなく Sorter インタフェースを持つ任意のオブジェクトであればよい。 [return]
  2. つか, Go 言語の関数は全て関数閉包として動作するんだけどね。 [return]