Go to Qiita Advent Calendar 2024 Top
LoginSignup
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

Go 5Advent Calendar 2020

Day 11
@eyuta(さとう ゆうた)in株式会社Works Human Intelligence

A Tour of Go メモ ~Concurrency~

Posted at

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 上でのテストの実行についてはこちらを参考にした
具体的には、

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

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

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

2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?