A Tour of Go メモ ~Concurrency~

# A Tour of Go メモ ~Concurrency~

## はじめに

Go の勉強のため、[A Tour of Go](https://go-tour-jp.appspot.com/concurrency/1)に取り組んでいる
今回は`Concurrency`章について、学んだことを記していく

まとめ記事は[こちら](https://qiita.com/eyuta/items/77ac58e4d9141898c733)

## 使えそうなスニペット

※筆者は VSCode を使用

### `ch`

`type`にカーソルが移動する

```go
chan type
```

### `sel`

`condition`、case のスコープ内にカーソルが移動する
switch 文同様、`cs`で vase を追加可能

```go
select {
case condition:

}

```

### `tyi`

```go
type name interface {

}
```

## ページごとの補足

### Buffered Channels

チャネルを make で作成する際、第二引数にバッファを指定できる
バッファを超えて値を格納しようとすると、以下のエラーが発生する

```go
ch := make(chan int, 1)
	c <- 1
	c <- 1 // fatal error: all goroutines are asleep - deadlock!
	fmt.Println(<-c)
	fmt.Println(<-c)
```

### Range and Close

```go
for i := range c {
  fmt.Println(i)
}
// for文で書くと...
for i, ok := <-c; ok; {
  fmt.Println(i)
  i, ok = <-c
}
```

### Select

Select については[こちらの記事が詳しい](https://qiita.com/najeira/items/71a0bcd079c9066347b4)
`A Tour of Go`には`select は、複数ある case のいずれかが準備できるようになるまでブロックし、`とあるが、ここでいう準備とは、送信時と受診時で異なる

- 送信時: チャネルのキャパシティに空きがある状態
- 受診時: チャネルに値が入っている状態

これらを満たさない場合、`default`句が存在すれば実行し、存在しなければ処理をブロック(中断)する

### Default Selection

上述したように、select は default 句の有無によって挙動が大きく異なるので、注意する

#### 送信時の select の挙動

select 実行時、`time.Sleep`によって受信側が準備できていないため、`default`が出力される

```go
c := make(chan int)
go func() {
	time.Sleep(1000 * time.Millisecond)
	fmt.Println(<-c)
}()

select {
case c <- 0:
	fmt.Println("send")
default:
	fmt.Println("default")
}
```

デフォルト句が存在しない場合、1 秒後に`send`が出力される(その間、処理がブロックされる)

また、チャネルを以下のように定義した場合も、バッファに格納できるため、`send`が出力される
ただし、そのまま main スレッドが終了するため、goroutine 内の`fmt.Println(<-c)`は実行されない

```go
c := make(chan int, 1)
```

#### 受信時の select の挙動

こちらも同様で、

- default 句がある
  - `default`が出力される
- default 句がない
  - 一秒待機後、`receive`が出力される

```go
c := make(chan int)

go func() {
	time.Sleep(1000 * time.Millisecond)
	c <- 0
}()

select {
case <-c:
	fmt.Println("receive")
default:
	fmt.Println("default")
}
```

### Exercise: Equivalent Binary Trees

#### ソートされた二分木とは

`A Tour of Go`には以下のようにある

```
関数 tree.New(k) は、値( k, 2k, 3k, ..., 10k )をもつ、
ランダムに構造化 (しかし常にソートされています) した二分木を生成します。
```

これは、[二分探索木](https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%9C%A8#%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E6%9C%A8)と呼ばれるものらしい
(上のリンクには簡単なロジックも書いてあるので、ネタバレが嫌な人は見ないほうが吉)

#### テスト方法について

テストの作成も Exercise のうちに含まれる
そのため、試しに testing パッケージを使用してテストを作成してみた
テスト、アサーションの導入については[こちら](https://swet.dena.com/entry/2018/01/16/211035)を、vscode 上でのテストの実行については[こちら](https://qiita.com/momotaro98/items/10ae87b21903dd54601c)を参考にした
具体的には、

1. 任意で` go get github.com/stretchr/testify/assert`パッケージをインストール
   - Go のテストパッケージにはデフォルトでアサーションが備わっていないため
   - 自前で作成しても可
2. `${テストしたいファイル名}_test.go`ファイルを作成
   - お作法
3. package 名はテストしたいファイルと同じにする
   - こうすると、プライベートメソッドも呼び出せる
4. `testing` パッケージを import
5. - テストを書く
6. launch.json にテスト用の`configurations`を追加
7. Run サイドバーで 6.で作成した`configurations`を指定後、実行

#### コード

```main.go
package main

import (
	"golang.org/x/tour/tree"
)

func walk(t *tree.Tree, c chan int) {
	if t.Left != nil {
		walk(t.Left, c)
	}
	c <- t.Value
	if t.Right != nil {
		walk(t.Right, c)
	}
}

func Walk(t *tree.Tree, c chan int) {
	walk(t, c)
	close(c)
}

func Same(t1, t2 *tree.Tree) bool {
	c1, c2 := make(chan int), make(chan int)

	go Walk(t1, c1)
	go Walk(t2, c2)

	for {
		v1, ok1 := <-c1
		v2, ok2 := <-c2

		if !ok1 || !ok2 {
			break
		}

		if v1 != v2 {
			return false
		}
	}
	return true
}

func main() {
}
```

#### テストコード

```main_test.go
package main

import (
	"testing"
	"github.com/stretchr/testify/assert"
	"golang.org/x/tour/tree"
)

func createdExpectedSlice(k int) (result []int) {
	expected := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
	for _, v := range expected {
		result = append(result, v*k)
	}
	return
}

func TestWalk(t *testing.T) {
	t.Run("Double", func(t *testing.T) {
		k := 2
		expected := createdExpectedSlice(k)
		c := make(chan int)
		go Walk(tree.New(k), c)
		for _, e := range expected {
			v, ok := <-c
			if ok {
				assert.Equal(t, e, v)
			}
		}
	})
	t.Run("Triple", func(t *testing.T) {
		k := 3
		expected := createdExpectedSlice(k)
		c := make(chan int)
		go Walk(tree.New(k), c)
		for _, e := range expected {
			v, ok := <-c
			if ok {
				assert.Equal(t, e, v)
			}
		}
	})
}

func TestSame(t *testing.T) {
	t.Run("Same tree", func(t *testing.T) {
		t1 := tree.New(1)
		t2 := tree.New(1)
		assert.True(t, Same(t1, t2))
	})

	t.Run("Different tree", func(t *testing.T) {
		t1 := tree.New(1)
		t2 := tree.New(2)
		assert.False(t, Same(t1, t2))
	})
}
```

参考までに、テスト結果も載せておく

```log
=== RUN   TestWalk
=== RUN   TestWalk/Double
=== RUN   TestWalk/Triple
--- PASS: TestWalk (0.00s)
    --- PASS: TestWalk/Double (0.00s)
    --- PASS: TestWalk/Triple (0.00s)
=== RUN   TestSame
=== RUN   TestSame/Same_tree
=== RUN   TestSame/Different_tree
--- PASS: TestSame (0.00s)
    --- PASS: TestSame/Same_tree (0.00s)
    --- PASS: TestSame/Different_tree (0.00s)
PASS
```

### sync.Mutex

Inc メソッドから`Lock`を取ると、`fatal error: concurrent map writes`が発生する
処理が Lock されていた場合は一旦処理が中断され、Unlock 後に処理が再開される

### Exercise: Web Crawler

`A Tour of Go`では、goroutine 内の処理の終了待つために`time.Sleep(time.Second)`を使っている
しかし、[sync.WaitGroup](https://golang.org/pkg/sync/#WaitGroup)を使うことで、goroutine 内の処理の終了をキャッチできるようになる
`WaitGroup`の使い方は[こちら](https://qiita.com/ruiu/items/dba58f7b03a9a2ffad65)が詳しかった

```go
package main

import (
	"fmt"
	"sync"
)

type Fetcher interface {
	// Fetch returns the body of URL and
	// a slice of URLs found on that page.
	Fetch(url string) (body string, urls []string, err error)
}

func Crawl(url string, depth int, fetcher Fetcher) {
	fetched := make(map[string]bool, 0)
	var mu sync.Mutex
	wg := sync.WaitGroup{}
	wg.Add(1)
	go crawl(url, depth, fetcher, fetched, &mu, &wg)
	wg.Wait()
	fmt.Println(fetched)
}

// Crawl uses fetcher to recursively crawl
// pages starting with url, to a maximum of depth.
func crawl(url string, depth int, fetcher Fetcher, fetched map[string]bool, mu *sync.Mutex, wg *sync.WaitGroup) {
	mu.Lock()

	defer mu.Unlock()
	defer wg.Done()

	// This implementation doesn't do either:
	if depth <= 0 {
		return
	}
	body, urls, err := fetcher.Fetch(url)
	if err != nil {
		fmt.Println(err)
		return
	}
	fmt.Printf("found: %s %q\n", url, body)

	fetched[url] = true

	for _, u := range urls {
		if _, ok := (fetched)[u]; !ok {
			wg.Add(1)
			go crawl(u, depth-1, fetcher, fetched, mu, wg)
		}
	}
	return
}

func main() {
	Crawl("https://golang.org/", 4, fetcher)
}

// fakeFetcher is Fetcher that returns canned results.
type fakeFetcher map[string]*fakeResult

type fakeResult struct {
	body string
	urls []string
}

func (f fakeFetcher) Fetch(url string) (string, []string, error) {
	if res, ok := f[url]; ok {
		return res.body, res.urls, nil
	}
	return "", nil, fmt.Errorf("not found: %s", url)
}

// fetcher is a populated fakeFetcher.
var fetcher = fakeFetcher{
	"https://golang.org/": &fakeResult{
		"The Go Programming Language",
		[]string{
			"https://golang.org/pkg/",
			"https://golang.org/cmd/",
		},
	},
	"https://golang.org/pkg/": &fakeResult{
		"Packages",
		[]string{
			"https://golang.org/",
			"https://golang.org/cmd/",
			"https://golang.org/pkg/fmt/",
			"https://golang.org/pkg/os/",
		},
	},
	"https://golang.org/pkg/fmt/": &fakeResult{
		"Package fmt",
		[]string{
			"https://golang.org/",
			"https://golang.org/pkg/",
		},
	},
	"https://golang.org/pkg/os/": &fakeResult{
		"Package os",
		[]string{
			"https://golang.org/",
			"https://golang.org/pkg/",
		},
	},
}

```

### 所感

Go 言語というより、アルゴリズム周りの知識不足により、苦戦した印象