Shimane.go#04 Lightning Talk

配列とスライスとソート

Presented by Spiegel, 2020

Licensed under  

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) //容量は省略可能

このスライスの内部状態は以下の図の通り

Go Slices: usage and internals
Go Slices: usage and internals

スライスの一部を切り取る

s = s[2:4]

切り取ったスライスの内部状態は以下の図の通り

Go Slices: usage and internals
Go Slices: usage and internals

容量いっぱいまでサイズを拡張する

s = s[:cap(s)]

拡張したスライスの内部状態は以下の図の通り

Go Slices: usage and internals
Go Slices: usage and internals

スライスは配列への参照のように振る舞うが
関数にスライスを渡す場合は注意が必要

スライス自体は値渡しであるため
操作結果は関数の呼び出し元に反映されない

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]

スライスのソート(整列)

Gosort パッケージを使えば簡単にスライスのソートを行うことができる。

[]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.SliceStable() で使用)

クイックソートは速いことで有名だが
以下の欠点がある

そこで sort.Slice() 関数では複数のアルゴリズムを組み合わせている

  1. 基本はクイックソート
  2. 要素数が12以下ならシェルソート(gap 6)へ
  3. 要素数が6以下なら挿入ソート
  4. クイックソートの再帰レベルが一定を超えたらヒープソートへ(イントロソート
    • $depth = \lceil\binlog(n+1)\rceil\times 2$

なので以下のデータセットのソートでは

var people = []struct {
    Name string
    Age  int
}{
    {"Elizabeth", 75},
    {"Colin", 35},
    {"Alice", 25},
    {"Bob", 35},
}

sort.Slice()sort.SliceStable() は同じ結果になるし, sort.Slice() のほうが前処理分だけ僅かに遅かったりする orz

以上,ありがとうございました

ネタ元(自ブログより)

以下のスライドには
配列やスライスに関するクイズが多数あります
是非挑戦してみてください

Go理解度チェック - Google スライド

slide.Baldanders.info

Powered by

Hugo and reveal-hugo