A Tour of Go Exercise

September 25, 2020

概要

Go言語の学習としてA Tour of Goをやりました。
こちらは演習の備忘録です。
オンライン¹で解いたので、ファイル化してgit管理するのが面倒臭くて、ブログで保管することにしました。
そのうちgit管理しようと思います。

環境

Macbook Pro 13inch, 2016
macOS Catalina version 10.15.6
Brave Browser v 1.14.81

Exercise: Loops and Functions

平方根の計算の実装です。
もっといい実装の方法があるみたいですね。
他の演習でもそうなのですが、変数名がすごく適当です。

package main

import (
	"fmt"
	"math"
)

func Sqrt(x float64) float64 {
	z := 1.0
	for i := 0; i < 10; i++ {
		var moto = z
		z -= (z*z - x) / (2 * z)
		fmt.Println(z)
		if math.Abs(z - moto) < 1e-15 {
			fmt.Println()
			return moto
		}
	}
	fmt.Println()
	return z
}

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

Exercise: Slices

スライスを使ったPic関数の実装です。
最初、何からすればいいのかさっぱり分かりませんでした。

package main

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

func Pic(dx, dy int) [][]uint8 {
	ret := make([][]uint8, dy)
	for y := 0; y < dy; y++ {
		ret[y] = make([]uint8, dx)
		for x := 0; x < dx; x++ {
			//ret[y][x] = uint8(x ^ y)
			ret[y][x] = uint8(x * y)
			//ret[y][x] = uint8((x + y) / 2)
		}
	}
	return ret
}

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

Exercise: Fibonacci closure

フィボナッチ数列です。
フィボナッチ数列を覚えていなくて、ウィキペディアで調べるところからはじめました。

$$ F_0 = 0, \newline F_1 = 1, \newline F_{n+2} = F_n + F_{n+1} (n \geq 0) $$

package main

import "fmt"

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

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

Exercise: Stringers

fmt.Stringerインタフェースの実装です。
IPアドレスをドットで4つに区切った表現で出力します。

package main

import "fmt"

type IPAddr [4]byte

// TODO: Add a "String() string" method to IPAddr.
func (ip IPAddr) String() string {
	return fmt.Sprintf("%d.%d.%d.%d",
					   ip[0], ip[1], ip[2], ip[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)
	}
}

Exercise: Errors

エラーインターフェースの実装です。
平方根の処理にエラー処理を追加します。

package main

import (
	"fmt"
	"math"
)

type ErrNegativeSqrt float64

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

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

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

Exercise: Readers

ストリーム処理の実装です。
「OK！」という結果が返ってきたので正しくできていると思うのですがよく分かりません。

package main

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

type MyReader struct{}

// TODO: Add a Read([]byte) (int, error) method to MyReader.
func (r MyReader) Read(rb []byte) (int, error) {
	for i, _ := range rb {
		rb[i] = 'A'
	}
	return len(rb), nil
}

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

Exercise: rot13Reader

ROT13換字式暗号の実装です。
これもウィキペディアで調べましたが、概要だけ読んで公式に気づかなかったのでいい勉強になりました。

暗号化: $E_n(x) = (x + n) mod 26$
複合化: $D_n(x) = (x - n) mod 26$

今回は $n=13$ を求めます。

package main

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

type rot13Reader struct {
	r io.Reader
}

func (r13 *rot13Reader) Read(rb []byte) (int, error) {
	n, err := r13.r.Read(rb)
	if err != nil {
		return 0, err
	}
	for i, v := range rb {
		switch {
			case v >= 'A' && v <= 'Z':
				rb[i] = (v - 'A' + 13) % 26 + 'A'
			case v >= 'a' && v <= 'z':
				rb[i] = (v - 'a' + 13) % 26 + 'a'
		}
	}
	return n, nil
}

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

Exercise: Images

image.Imageインターフェースを実装した画像ジェネレータです。

package main

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

type Image struct{}

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

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

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

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

Exercise: Equivalent Binary Trees

Goroutineを使った二分木の実装です。
deadlock地獄でした。
Walk関数の実装で疲れ果て、Same関数の実装が面倒になった結果、refrect.DeepEqualを使用して手抜きしました。

package main

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

// 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 == nil {
		return
	}
	Walk(t.Left, ch)
	ch<-t.Value
	Walk(t.Right, ch)
}

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
	ch1 := make(chan int, 10)
	ch2 := make(chan int, 10)
	var str1, str2 []int
	
	go Walk(t1, ch1)
	for i := 0; i < cap(ch1); i++ {
		str1 = append(str1, <-ch1)
	}
	
	go Walk(t2, ch2)
	for i := 0; i < cap(ch2); i++ {
		str2 = append(str2, <-ch2)
	}
	return reflect.DeepEqual(str1, str2)
}

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

Exercise: Web Crawler

ウェブクローラの並列化です。
相変わらずdeadlock地獄で、最終的にStack Overflowの記事を参考にしました。

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

// Crawl uses fetcher to recursively crawl
// pages starting with url, to a maximum of depth.
func Crawl(url string, depth int, fetcher Fetcher, ret chan string, list map[string]bool, mutex sync.Mutex) {
	// TODO: Fetch URLs in parallel.
	// TODO: Don't fetch the same URL twice.
	// This implementation doesn't do either:
	
	defer close(ret)
	
	if depth <= 0 {
		return
	}
	
	body, urls, err := fetcher.Fetch(url)
	
	if list[url] {
		return
	}
	
	mutex.Lock()
	list[url] = true
	mutex.Unlock()
	
	if err != nil {
		ret <-err.Error()
		return
	}
	
	ret <- fmt.Sprintf("found: %s %q", url, body)
	
	ch := make([]chan string, len(urls))
	for i, u := range urls {
		ch[i] = make(chan string)
		go Crawl(u, depth-1, fetcher, ch[i], list, mutex)
	}
	
	for i := range ch {
        for s := range ch[i] {
            ret <- s
        }
    }
	return
}

func main() {
	ret := make(chan string)
	list := make(map[string]bool)
	var mutex sync.Mutex
	go Crawl("https://golang.org/", 4, fetcher, ret, list, mutex)
	for s:= range ret {
		fmt.Println(s)
	}
}

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

まとめ

A Tour of Goを学習しました。

演習は全体的に難しくて、最初から最後まで苦労しました。
ROT13換字式暗号あたりからヤバイです。
アルゴリズムで苦労したということも一因で、普段使わないからといってサボり過ぎました。
時間を見つけて復習しようと思います。

3日くらい使って終わらせたのですが、時間としてはのべ16時間くらいだったと思います。後半の演習で頭を抱えている時間が長かったです。
ポインタや並列処理がいまいち使いこなせていません。

プログラミング言語Goという書籍²が次のステップとしていいらしいので、苦手部分も補いつつ学習しようと思います。

オフライン版もありますが、僕の環境では日本語版がうまく動作しませんでした。 ↩︎
めっちゃ高い！ ↩︎