Shimane.go#04 Lightning Talk
配列とスライスとソート
Presented by Spiegel, 2020
C/C++, Java など制御系言語が得意
ただし，現在は無期休業でその日暮らし中
Go 言語は趣味の範囲内で
趣味のプロダクト
gpgpdump
OpenPGP packet visualizer
pa-api
Client Side API for Amazon PA-APIv5
では，本編へ
突然ですが
おさらい（1）
Go の型について
Go 言語の型は大きく3つに分類される
（分類は Spiegel の独断と偏見で）
1. 基本型
| 種別 | 型名 |
|---|---|
| 数値型 | int, float64, byte, … |
| 複素数型 | complex64, complex128 |
| 真偽型 | bool |
| 文字列 | string |
基本型は比較可能（comparable）だが
大小比較できるのは数値型と文字列のみ
2. 構造体型
| 種別 | 型名（例） |
|---|---|
| 配列 | [4]int |
| 構造体 | struct { e int64 } |
構造体型は（型が同一であれば）比較可能
たとえば
struct {e int64} と struct {e float64}
同名要素の型が同一ではない
→ 比較不可
[2]int と [4]int
要素の型は同一だが要素数が同一ではない
→ 比較不可
3. 参照（のように振るまう）型
| 種別 | 型名（例） | 比較 |
|---|---|---|
| チャネル | chan int |
可 |
| インタフェース | interface {} |
可 |
| 関数 | func(int) int |
不可 |
| スライス | []int |
不可 |
| マップ | map[int]int |
不可 |
※ 参照型はどの型も nil とは比較可能
Go 言語において配列は
要素の型および要素数固定のデータ列
「同一の型」であれば比較可能
Go 言語においてスライスは
配列への参照
要素数可変
比較不可
おさらい（2）
Go は値渡し
Go 言語では
関数の引数やメソッド・レシーバは
原則として値渡しである
int の値を渡すコードを考える
func Say(v int) {
fmt.Printf("[%p]: %v\n", &v, v)
}
func main() {
v := 100
fmt.Printf("[%p]: %v\n", &v, v)
Say(v)
}
実行結果は以下の通り
[0x40e020]: 100
[0x40e040]: 100
関数に渡されるインスタンスは
呼び出し元インスタンスのコピーであり
同一のインスタンスではない
渡す型を配列に置き換える
func Say(v [2]int) {
fmt.Printf("&v = %p , [%p]: %v\n", &v, &v[0], v[0])
}
func main() {
v := [2]int{100, 200}
fmt.Printf("&v = %p , [%p]: %v\n", &v, &v[0], v[0])
Say(v)
}
実行結果は以下の通り
&v = 0x40e020 , [0x40e020]: 100
&v = 0x40e038 , [0x40e038]: 100
配列も値渡し
（配列のポインタと要素のポインタを並べた理由は後ほど）
渡す型をスライスに置き換える
func Say(v []int) {
fmt.Printf("&v = %p , [%p]: %v\n", &v, &v[0], v[0])
}
func main() {
v := []int{100, 200}
fmt.Printf("&v = %p , [%p]: %v\n", &v, &v[0], v[0])
Say(v)
}
実行結果は以下の通り
&v = 0x40a0e0 , [0x40e020]: 100
&v = 0x40a0f0 , [0x40e020]: 100
スライスも値渡し
ただし要素のポインタは同じ値を指している
つまり
スライスは配列を参照するオブジェクト
と言える
ここからが本番
スライスは配列への参照
スライスは配列に対する
- ポインタ
- （有効な）サイズ
- 容量
の3つの属性を持つオブジェクトである
s := make([]byte, 5, 5) //容量は省略可能
このスライスの内部状態は以下の図の通り
スライスの一部を切り取る
s = s[2:4]
切り取ったスライスの内部状態は以下の図の通り
容量いっぱいまでサイズを拡張する
s = s[:cap(s)]
拡張したスライスの内部状態は以下の図の通り
スライスは配列への参照のように振る舞うが
関数にスライスを渡す場合は注意が必要
スライス自体は値渡しであるため
操作結果は関数の呼び出し元に反映されない
func main() {
var s1, s2 []int
s1 = []int{1, 2}
s2 = append(s1, 3) //要素の追加
fmt.Printf("ptr=%p len=%d cap=%d %v\n", &s1[0], len(s1), cap(s1), s1)
fmt.Printf("ptr=%p len=%d cap=%d %v\n", &s2[0], len(s2), cap(s2), s2)
}
実行結果は以下の通り
ptr=0x40e020 len=2 cap=2 [1 2]
ptr=0x40e030 len=3 cap=4 [1 2 3]
スライスのソート（整列）
[]float64 のソート例
func main() {
fset := []float64{0.055, 0.815, 1.0, 0.107}
fmt.Println(fset)
sort.Slice(
fset,
func(i, j int) bool {
return fset[i] < fset[j]
},
)
fmt.Println(fset)
}
第2引数で大小比較を評価する関数を指定する
（関数閉包に注意）
実行結果は以下の通り
[0.055 0.815 1 0.107]
[0.055 0.107 0.815 1]
sort.Slice() 関数は
安定ソートではないので注意！
（詳しくは後ほど）
安定ソートも用意されている
func main() {
fset := []float64{0.055, 0.815, 1.0, 0.107}
fmt.Println(fset)
sort.SliceStable(
fset,
func(i, j int) bool {
return fset[i] < fset[j]
},
)
fmt.Println(fset)
}
何らかの方法で大小比較が可能であれば
スライスの要素の型は任意にできる
以下の構造体のスライスに対して
var people = []struct {
Name string
Age int
}{
{"Elizabeth", 75},
{"Colin", 35},
{"Alice", 25},
{"Bob", 35},
}
Age の昇順でソートを行う
func main() {
sort.SliceStable(
people,
func(i, j int) bool {
return people[i].Age < people[j].Age
},
)
fmt.Println(people)
}
実行結果は以下の通り
[{Alice 25} {Colin 35} {Bob 35} {Elizabeth 75}]
【おまけ】
ソートのアルゴリズム
sort パッケージで使われている
アルゴリズムについて
ソート・アルゴリズム毎の計算量
| 名前 | 最良 | 最悪 | 平均 |
|---|---|---|---|
| クイック | $\landau(n \log n)$ | $\landau(n^2)$ | $\landau(n \log n)$ |
| ヒープ | $\landau(n \log n)$ | $\landau(n \log n)$ | $\landau(n \log n)$ |
| シェル | $\landau(n \log^2 n)$ | $\landau(n^2)$ | — |
| 挿入 | $\landau(n)$ | $\landau(n^2)$ | $\landau(n^2)$ |
クイックソートは速いことで有名だが
以下の欠点がある
そこで sort.Slice() 関数では複数のアルゴリズムを組み合わせている
なので以下のデータセットのソートでは
var people = []struct {
Name string
Age int
}{
{"Elizabeth", 75},
{"Colin", 35},
{"Alice", 25},
{"Bob", 35},
}
sort.Slice() と sort.SliceStable() は同じ結果になるし， sort.Slice() のほうが前処理分だけ僅かに遅かったりする orz
以上，ありがとうございました
ネタ元（自ブログより）
以下のスライドには
配列やスライスに関するクイズが多数あります
是非挑戦してみてください
↓
Powered by
Hugo and reveal-hugo
