目的
A Tour of Goは、Goを始める人なら誰でも通る道かと思うが、Exerciseは初見では結構頭を捻った。
仮に解けなくても、多くの解答がWebにあるので、理解して進めることができる。
ただし、最後の問題だけは、探してもツアーの中で学んだものだけで解かれたものがなかった。# 探し方が悪いだけかもしれないが。。。
今回、ツアーで学んだものだけで解いたので、(スマートではないだろうが)残しておく。
問題内容
A Tour of Go | Exercise: Web Crawler
同じURLを2度取ってくることなく並列してURLを取ってくるように、 Crawl 関数を修正してみてください(注1)。
補足: 工夫すれば Crawl 関数のみの修正で実装できますが、無理に Crawl 関数内部に収める必要はありません。
ひとこと: mapにフェッチしたURLのキャッシュを保持できますが、mapだけでは並行実行時の安全性はありません!
問題となるコード
package main
import (
"fmt"
)
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) {
// TODO: Fetch URLs in parallel.
// TODO: Don't fetch the same URL twice.
// 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)
for _, u := range urls {
Crawl(u, depth-1, fetcher)
}
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/",
},
},
}
このコードは何をやっているのか
まずmail()では、Crawl("https://golang.org/", 4, fetcher)を呼んでいる。
また、fetcher.Fetch(url)で取得した複数のURLに対して、Crawl(u, depth-1, fetcher)を呼んでいることがわかる。
Crawl()関数を見てみると、depth <= 0でreturnしており、Crawl()関数を呼ぶ度にdepth-1している。
つまり、各URLに対して最大で3回Crawl()関数が呼ばれてる。
次に、fetcherの形と値を照らし合わせて見てみる。
type fakeFetcher map[string]*fakeResult
type fakeResult struct {
body string
urls []string
}
var fetcher = fakeFetcher{
"https://golang.org/": &fakeResult{
"The Go Programming Language",
[]string{
"https://golang.org/pkg/",
"https://golang.org/cmd/",
},
},
1つ目を見るとfetcherは、map[key]{ body, urls[XXX, YYY] }の形をしてることがわかる。
fetcher["https://golang.org/"].bodyを呼ぶと、The Go Programming Language
fetcher["https://golang.org/"].urlsを呼ぶと、[https://golang.org/pkg/ https://golang.org/cmd/]
が出力される。
ここまで分かると、fetcher.Fetch(url)はつまるところ、上記を返しているに過ぎないことがわかる。
そして、urlsの各々に対して、同じことを最大3回、もしくはmapのkey(url)が存在しない(=not found)と分かるまで繰り返している。
解答までの道のり
問題内容から、やることとしては大きく2つ
- URL取得の並列化
- URLを1度しか呼ばない
1.に関しては、goroutineを使えば可能。また、同期を取るためにchanelを使えばよさそう。
2.に関しては、ひとことに書いてあるとおり、mapを使えばできそう。
ただし、並列実行するので排他制御mutex(Lock(),Unlock())する必要がありそう。
まずはmain()で呼ばれているCrawl()を見てみる。
func Crawl(url string, depth int, fetcher Fetcher) {
// TODO: Fetch URLs in parallel.
// TODO: Don't fetch the same URL twice.
// 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)
for _, u := range urls {
Crawl(u, depth-1, fetcher)
}
return
}
再帰呼び出しとなっているが、chanelを使うとなると、もう1つ関数を中で作ればよさそう。
元の処理をまるっとcrawlChild()に入れてみた。
func Crawl(url string, depth int, fetcher Fetcher) {
// TODO: Fetch URLs in parallel.
// TODO: Don't fetch the same URL twice.
// This implementation doesn't do either:
var crawlChild func(string, int)
crawlChild = func(url string, depth int) {
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)
for _, u := range urls {
go crawlChild(u, depth-1)
}
}
crawlChild(url, depth)
return
}
これで実行すると、1つしか出力されない。他のgoroutineを待たずして終わってしまうから。
found: https://golang.org/ "The Go Programming Language"
chanelを使うように修正してみる。
func Crawl(url string, depth int, fetcher Fetcher) {
// TODO: Fetch URLs in parallel.
// TODO: Don't fetch the same URL twice.
// This implementation doesn't do either:
// 追加
ch := make(chan string, depth*depth)
var prev int
var crawlChild func(string, int)
crawlChild = func(url string, depth int) {
if depth <= 0 {
return
}
// 追加
ch <- url
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 crawlChild(u, depth-1)
}
}
crawlChild(url, depth)
// 追加
for {
if len(ch) != prev {
prev = len(ch)
} else {
break
}
time.Sleep(time.Millisecond)
}
return
}
make()でサイズを指定しないと、deadlockとなるので指定してますが、適したサイズがわからないので、depth*depthとしてみた。
そして、return前に、本来の使い方ではないけど、chanel数がこれ以上増えないと分かるまで無限ループで待つようにする。
この状態で実行すると、ようやっと最初と同じ結果が得られた。
あとは、URLを1度しか呼ばないようにするだけ。URLをkeyとした、map[string]boolで、URLを呼ぶ前にT/F判定させればよさそう。
func Crawl(url string, depth int, fetcher Fetcher) {
// TODO: Fetch URLs in parallel.
// TODO: Don't fetch the same URL twice.
// This implementation doesn't do either:
// 追加
ch := make(chan string, depth*depth)
var prev int
// 追加
cache := make(map[string]bool)
var mutex sync.Mutex
var crawlChild func(string, int)
crawlChild = func(url string, depth int) {
if depth <= 0 {
return
}
// 追加
if cache[url] == true {
return
}
mutex.Lock()
defer mutex.Unlock()
cache[url] = true
// 追加
ch <- url
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 crawlChild(u, depth-1)
}
}
crawlChild(url, depth)
// 追加
for {
if len(ch) != prev {
prev = len(ch)
} else {
break
}
time.Sleep(time.Millisecond)
}
return
}
実行すると、見事に1度しか呼ばれないようになった。
found: https://golang.org/ "The Go Programming Language"
found: https://golang.org/pkg/ "Packages"
found: https://golang.org/pkg/os/ "Package os"
not found: https://golang.org/cmd/
found: https://golang.org/pkg/fmt/ "Package fmt"
Program exited.
全体のコードは、下記にあります。
a-tour-of-go/exercise-web-crawler.go at master · hirano00o/a-tour-of-go
最後に
A Tour of Goは、中々に長い道のりですが、一通り基本は身につくので、やったほうが良いかと思います。
これが終わったら、実際になにか作るか、go Wiki(英語)、CodeReviewCommentsを見てくかですかね。
CodeReviewCommentに関しては、和訳してくれた方がいるので、そちらを見ればいいのかなと思います。