A Tour of Go メモ ~Concurrency~

はじめに

Go の勉強のため、A Tour of Goに取り組んでいる
今回はConcurrency章について、学んだことを記していく

まとめ記事はこちら

使えそうなスニペット

※筆者は VSCode を使用

`ch`

typeにカーソルが移動する

chan type

`sel`

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

select {
case condition:

}

`tyi`

type name interface {

}

ページごとの補足

Buffered Channels

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

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

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

Select

Select についてはこちらの記事が詳しい
A Tour of Goにはselect は、複数ある case のいずれかが準備できるようになるまでブロックし、とあるが、ここでいう準備とは、送信時と受診時で異なる

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

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

Default Selection

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

送信時の select の挙動

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

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)は実行されない

c := make(chan int, 1)

受信時の select の挙動

こちらも同様で、

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

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 )をもつ、
ランダムに構造化 (しかし常にソートされています) した二分木を生成します。

これは、二分探索木と呼ばれるものらしい
(上のリンクには簡単なロジックも書いてあるので、ネタバレが嫌な人は見ないほうが吉)

テスト方法について

テストの作成も Exercise のうちに含まれる
そのため、試しに testing パッケージを使用してテストを作成してみた
テスト、アサーションの導入についてはこちらを、vscode 上でのテストの実行についてはこちらを参考にした
具体的には、

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

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

=== 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を使うことで、goroutine 内の処理の終了をキャッチできるようになる
WaitGroupの使い方はこちらが詳しかった

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 言語というより、アルゴリズム周りの知識不足により、苦戦した印象