Zenn
Open13

Go 初見で A Tour of Go 演習問題 解いてみた

Golang
#
beginner
sifi_bordersifi_border

Exercise: Loops and Functions

ニュートン法で\sqrt{2}を計算します。

10回ループを回す方は省略しています。
pre_zという変数に直前のzを格納しておき、ある程度収束したら無限ループから抜ける、という実装です。

package main

import (
	"fmt"
	"math"
)

func MySqrt(x float64) float64 {
	z := 1.0
	pre_z := z * 2
	for math.Abs(pre_z - z) > 1e-10 {
		pre_z = z
		z -= (z*z - x) / (2 * z)
		fmt.Println(z)
	}
	return z
}

func main() {
	fmt.Printf("My sqrt(2) = %v\n", MySqrt(2))
	fmt.Printf("math.Sqrt(2) = %v\n", math.Sqrt(2))
}

出力は以下の通りです。（意外と収束が早い）

1.5
1.4166666666666667
1.4142156862745099
1.4142135623746899
1.4142135623730951
My sqrt(2) = 1.4142135623730951
math.Sqrt(2) = 1.4142135623730951
sifi_bordersifi_border

Exercise: Slices

sliceの要素にsliceを持つことで二重配列（多重配列）を実現できる。

二重スライスvar res [][]uint8を宣言し、ループ内で行スライスrow := make([]uint8, dx)を作成し格納する、という実装。
sliceの代入はコピーされず参照が渡る(表現が正しくないかも)ので、ループ外でrowを宣言すると全ての行が同じ一つのsliceを参照してしまうことに注意。

グレースケールの整数値はmin(x, y)としている。

package main

import "golang.org/x/tour/pic"
import "math"

func Pic(dx, dy int) [][]uint8 {
	var res [][]uint8
	for i := 0; i < dy; i++ {
		row := make([]uint8, dx)
		res = append(res, row)
	}

	for h := 0; h < dy; h++ {
		for w := 0; w < dx; w++ {
			res[h][w] = uint8(math.Min(float64(h), float64(w)))
		}
	}
	return res
}

func main() {
	pic.Show(Pic)
}

出力された画像は以下の通り。

急にPicを使えと言われて、困っていた。Pic関数に何か引数を渡す必要がありそうだな〜と思っていたが、不要らしい。

sifi_bordersifi_border

Exercise: Maps

WordCountを自前で実装します。

strings.Fieldsを使い文字列をスプリットして、連想配列で単語をカウント。

Fieldsは、1つ以上の連続した空白文字(unicode.IsSpaceで定義)の各インスタンスの周りで文字列sを分割し、sの部分文字列のスライス、またはsが空白のみを含む場合は空のスライスを返します。

package main

import (
	"golang.org/x/tour/wc"
	"strings"
)

func WordCount(s string) map[string]int {
	res := make(map[string]int)
	split_s := strings.Fields(s)
	for i := 0; i < len(split_s); i++ {
		res[split_s[i]]++
	}
	return res
}

func main() {
	wc.Test(WordCount)
}

普通のsplit関数もあるんでしょと思ったら、ありました。

func WordCount(s string) map[string]int {
	res := make(map[string]int)
	split_s := strings.Split(s, " ")
	for i := 0; i < len(split_s); i++ {
		res[split_s[i]]++
	}
	return res
}
sifi_bordersifi_border

Exercise: Fibonacci closure

フィボナッチ数列は F_{i+2} = F_{i+1} + F_{i}という式で計算できます。
つまり直前の二項だけを覚えておけば新しい項が計算できるので、これをクロージャ外の変数として保持しておけば良いです。

変数名がアレでアレですが、pre,latがそれぞれF_{i},F_{i+1}に対応していて、これらを同時に更新しています。

package main

import "fmt"

// fibonacci is a function that returns
// a function that returns an int.
func fibonacci() func() int {
	pre, lat := 0, 1
	return func() int {
		res := pre
		pre, lat = lat, pre + lat
		return res
	}
}

func main() {
	f := fibonacci()
	for i := 0; i < 10; i++ {
		fmt.Println(f())
	}
}

pre, lat = lat, pre + latみたいに書けるの、良いですね。

sifi_bordersifi_border

Exercise: Stringers

fmt.Sprintfを用いた実装です。

Sprintfはフォーマット指定子に従ってフォーマットし、結果の文字列を返す。

package main

import "fmt"

type IPAddr [4]byte

// TODO: Add a "String() string" method to IPAddr.
func (ipaddr IPAddr) String() string {
	return fmt.Sprintf("%d.%d.%d.%d", ipaddr[0], ipaddr[1], ipaddr[2], ipaddr[3])
}

func main() {
	hosts := map[string]IPAddr{
		"loopback":  {127, 0, 0, 1},
		"googleDNS": {8, 8, 8, 8},
	}
	for name, ip := range hosts {
		fmt.Printf("%v: %v\n", name, ip)
	}
}

for文で文字列を連結したかったが、この方が可読性が高そう。

sifi_bordersifi_border

Exercise: Errors

fmt.SprintfでError()を実装すると良いです。

package main

import (
	"fmt"
	"math"
)

type ErrNegativeSqrt float64

func (e ErrNegativeSqrt) Error() string {
	return fmt.Sprintf("cannot Sqrt negative number: %f", float64(e))
}

func Sqrt(x float64) (float64, error) {
	if x < 0 {
		return x, ErrNegativeSqrt(x)
	}
	z := 1.0
	pre_z := z * 2
	for math.Abs(pre_z-z) > 1e-10 {
		pre_z = z
		z -= (z*z - x) / (2 * z)
	}
	return z, nil
}

func main() {
	fmt.Println(Sqrt(2))
	fmt.Println(Sqrt(-2))
}

x < 0の時、float64として何を返すのが適切なのでしょうか。
Result型みたいなものはgoには無いっぽいので、うーんという感じだ。

sifi_bordersifi_border

Exercise: Readers

この前項にRead関数について以下のような説明があります。

Read は、データを与えられたバイトスライスへ入れ、入れたバイトのサイズとエラーの値を返します。 ストリームの終端は、 io.EOF のエラーで返します。

今回実装するのは'A'の無限ストリームなので、引数のバイトスライスの要素を全て'A'として埋めれば良いです。io.EOFエラーは返しません（無限なので）。

package main

import "golang.org/x/tour/reader"

type MyReader struct{}

// TODO: Add a Read([]byte) (int, error) method to MyReader.
func (MyReader) Read(b []byte) (int, error) {
	for i := 0; i < len(b); i++ {
		b[i] = 'A'
	}
	return len(b), nil
}

func main() {
	reader.Validate(MyReader{})
}

このコードをサイト上で実行するとOK!と表示されるのですが、無限であることをその振る舞いだけで（つまり実装を見ずに）どうやって判断しているのでしょうか。
例えば1e10000文字読んだらEOFが返る、みたいな実装でもOK!と表示される気がしていて...

こういうことを考えてしまうのを止めたい。

sifi_bordersifi_border

Exercise: rot13Reader

既存のio.readerをラップしてrot13を実装します。
Readしたバイト列を一文字ずつ見ていって、アルファベットであればROT13して書き換えています。

package main

import (
	"io"
	"os"
	"strings"
)

type rot13Reader struct {
	r io.Reader
}

func (rot13 rot13Reader) Read(b []byte) (int, error) {
	n, err := rot13.r.Read(b)
	for i := 0; i < n; i++ {
		if 'A' <= b[i] && b[i] <= 'Z' {
			p := b[i] - 'A'
			p = (p + 13) % 26
			b[i] = 'A' + p
		}
		if 'a' <= b[i] && b[i] <= 'z' {
			p := b[i] - 'a'
			p = (p + 13) % 26
			b[i] = 'a' + p
		}
	}
	return n, err
}

func main() {
	s := strings.NewReader("Lbh penpxrq gur pbqr!")
	r := rot13Reader{s}
	io.Copy(os.Stdout, &r)
}

ROT13の処理ですが、大文字のケースについて説明すると、

p := b[i] - 'A'

でb[i]がAから何文字離れたアルファベットであるかを計算し、

p = (p + 13) % 26

それを13文字後ろにずらしています。
0-indexedで25番目以降（Z以降）はAに戻るので、26で割っています。

b[i] = 'A' + p

最後にアルファベットに復元しています。

大文字/小文字であるかを判定する関数がstringに見当たらなかったので、原始的な分岐で判定しています。

sifi_bordersifi_border

Exercise: Images

適宜ドキュメントを参照しながら、Imageインターフェースを満たすようにメソッドを追加します。
color.Model等で必要なcolorモジュールは"image/color"にあるため、このパスを指定してimportする必要があります。

package main

import "golang.org/x/tour/pic"
import "image"
import "image/color"

type Image struct{}

func (Image) ColorModel() color.Model {
	return color.RGBAModel
}

func (Image) Bounds() image.Rectangle {
	return image.Rect(0, 0, 255, 255)
}

func (Image) At(x, y int) color.Color {
	v := uint8(x) ^ uint8(y)
	return color.RGBA{v, v, 255, 255}
}

func main() {
	m := Image{}
	pic.ShowImage(m)
}

colorモジュールがimage直下にあることがわかった後、image.color.Modelのように参照できると思ったらコンパイラに怒られて困惑していました。

sifi_bordersifi_border

Exercise: Equivalent Binary Trees

Walk, Sameという関数を実装していきます。

まずはTree（二分木）についての前提知識を確認します。
ドキュメントを見ると、実装としてはノード（頂点）にValueと左右の子へのポインター(Left, Right)を持つシンプルなものです。

type Tree struct {
    Left  *Tree
    Value int
    Right *Tree
}

func (t *Tree) String() stringが実装されているようなので、k = 1の場合を試しに出力してみます。（乱数を用いて生成されているため、Runの度に結果が変わることに注意。）
main関数は以下の通りです。

func main() {
    g := tree.New(1) // graph の g
    fmt.Println(g)
}

今回得られた出力((1 (2)) 3 ((4) 5 (((6) 7 ((8) 9)) 10)))に対応するグラフを図示すると以下のようになると思います。（手動で作成したので、間違っていたらすみません）

二分木の重要な性質として、各ノードの左のTreeに含まれるノードのValueは自身より小さく、右のTreeに含まれるノードのValueは自身より大きい、というのがあります。

本題に戻ります。

コメントに説明がありますが、Walk関数はTree上の全ての頂点を訪れながら、各頂点のValueを小さい順にチャネルに送信する関数です。
上記で述べたい二分木の性質を踏まえると、Walk関数は以下のように書けそうです。

// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
	if t.Left != nil {
		Walk(t.Left, ch)
	}
	ch <- t.Value
	if t.Right != nil {
		Walk(t.Right, ch)
	}
}

今見ている頂点について、左のTreeがあれば（自分より小さい頂点が存在するため）先にそちらへWalkします。左のTreeの探索が終わった時にチャネルchにValueを送信し、右のTreeがあればそちらを探索します。
右のTreeには自分より大きなものしかないため、この処理順で大丈夫です。

続いてSame関数ですが、これは二つのTreeが同じValueを保持しているかを判定する関数のようです。
Walk関数を用いて以下のように書けます。

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
	ch1 := make(chan int)
	ch2 := make(chan int)
	go Walk(t1, ch1)
	go Walk(t2, ch2)
	for i := 1; i <= 10; i++ {
		val1, val2 := <-ch1, <-ch2
		if val1 != val2 {
			return false
		}
	}
	return true
}

WalkはValueを小さい順に返すので、それぞれの木についてWalkを呼び、チャネルから受信した値が全て等しくなっているかを判定しています。

テストも含めた最終的なコードは以下の通りです。

package main

import "golang.org/x/tour/tree"
import "fmt"

// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
	if t.Left != nil {
		Walk(t.Left, ch)
	}
	ch <- t.Value
	if t.Right != nil {
		Walk(t.Right, ch)
	}
}

func TestWalk() bool {
	k := 2
	graph := tree.New(k)
	ch := make(chan int)
	go Walk(graph, ch)
	for i := 1; i <= 10; i++ {
		val := <-ch
		if val != i*k {
			return false
		}
	}
	return true
}

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
	ch1 := make(chan int)
	ch2 := make(chan int)
	go Walk(t1, ch1)
	go Walk(t2, ch2)
	for i := 1; i <= 10; i++ {
		val1, val2 := <-ch1, <-ch2
		if val1 != val2 {
			return false
		}
	}
	return true
}

func main() {
	g := tree.New(1)
	fmt.Println(g)
	ch := make(chan int)
	go Walk(g, ch)
	for i := 0; i < 10; i++ {
		fmt.Println(<-ch)
	}
	fmt.Println(TestWalk())
	// test Same
	fmt.Println(Same(tree.New(1), tree.New(1)))
	fmt.Println(Same(tree.New(1), tree.New(2)))
}

for i := range chのように書くとデッドロックが発生したので、要素数分のループを回しています。

何の脈絡もなく二分木が出てきて驚きました。
余談ですが、上記のWalk関数の実装は深さ優先探索(DFS)になっています。

sifi_bordersifi_border

Exercise: Web Crawler

同じURLを二度クロールしないように排他制御します。

前項のSafeCounterのアイデアを流用し、以下のようなurlCheckerを用いる方針で進めます。

// URL is already crawled?
type urlChecker struct {
	mu sync.Mutex
	v  map[string]bool
}

Crawl関数内でfetcher.Fetch(url)を呼ぶ前に、そのURLが既にクロールされているかを確認します。
されていなければ続行し、既にされていればクロールの必要はないので、returnします。
関連箇所を抜き出すと以下のような感じです。

func Crawl(url string, depth int, fetcher Fetcher, checker *urlChecker) {
    if !checker.check(url) {
        return
    }
    body, urls, err := fetcher.Fetch(url)
    ...
}

このcheckメソッドに排他制御が必要なので、適切に実装します。

func (checker *urlChecker) check(url string) bool {
	checker.mu.Lock()
	defer checker.mu.Unlock()

	if checker.v[url] {
		return false
	}
	checker.v[url] = true
	return true
}

該当URLがクロールされていなければ、URLをkeyとする連想配列のvalueをtrueに更新し、クロールしていいよ〜と知らせるためtrueを返します。
既にクロールされていればクロールしなくていいよ〜と知らせるためfalseを返します。

以上で本質的な実装は完了しており、全貌は以下の通りです。

package main

import (
	"fmt"
	"time"
	"sync"
)

// URL is already crawled?
type urlChecker struct {
	mu sync.Mutex
	v  map[string]bool
}

func (checker *urlChecker) check(url string) bool {
	checker.mu.Lock()
	defer checker.mu.Unlock()

	if checker.v[url] {
		return false
	}
	checker.v[url] = true
	return true
}

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)
}

// Crawl uses fetcher to recursively crawl
// pages starting with url, to a maximum of depth.
func Crawl(url string, depth int, fetcher Fetcher, checker *urlChecker) {
	// TODO: Fetch URLs in parallel.
	// TODO: Don't fetch the same URL twice.
	// This implementation doesn't do either:
	if depth <= 0 {
		return
	}
	if !checker.check(url) {
		return
	}
	body, urls, err := fetcher.Fetch(url)
	if err != nil {
		fmt.Println(err)
		return
	}
	fmt.Printf("found: %s %q\n", url, body)
	for _, u := range urls {
		go Crawl(u, depth-1, fetcher, checker)
	}
	return
}

func main() {
	checker := &urlChecker{v: make(map[string]bool)}
	go Crawl("https://golang.org/", 4, fetcher, checker)
	time.Sleep(time.Second)
}

// 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/",
		},
	},
}

main関数のtime.Sleep(time.Second)については、これがないとクロールの終了を待たずにプログラムが終了してしまう（え？）ため置いています。

出力見るとTODO: Don't fetch the same URL twice.に関しては達成できているのが確認できます。
ただ、TODO: Fetch URLs in parallel.に関しては確認ができておらず、うーむという感じです。

sifi_bordersifi_border

以上で全ての演習問題の解説が終了です。
完走した感想ですが、入門者向け演習問題としてはなかなか歯応えがありました。
golangに対する感想としては、CとRustの中間みたいな感じだな〜と感じました。

動機としては「ISUCONに出るならgoやらないとな〜」という気持ちでザーッと取り組んでみました。来年出るかはわかりませんが。

Zennに記事（スクラップ？）を投稿するのは初めてなので、こういう運用方法でいいのか謎なんですが、訂正や質問コメント等歓迎です。