見出し画像

Exercise: Web Crawler

bkc

とうとうA Tour Of Go最後のエクササイズになりました。

内容

In this exercise you'll use Go's concurrency features to parallelize a web crawler.
Modify the Crawl function to fetch URLs in parallel without fetching the same URL twice.
Hint: you can keep a cache of the URLs that have been fetched on a map, but maps alone are not safe for concurrent use!

予め与えられているコード

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

簡単にいうと上記のコードでも目的通りの動作をしますがこれをゴルーチンで並行処理するように、また同じURLは取得しないようにCrawl関数を書き換えてくれという問題です。
もちろんCrawl関数以外に関数を定義してもいいということです。

下の方にあるfakeFetcherは実際のウェブサイトをクロールすると問題があるので擬似の取得情報を表して、プログラムを実行するとここから情報をFetchしてくることになります。

私のコード

正直今回は自分では書けませんでした。修行がたりませんね。ゴルーチンで並行処理を行いURLが重複している部分は除外するように出来たのですが、デッドロックを解消出来ませんでした。

type Fetcher interface {
	Fetch(url string) (body string, urls []string, err error)
}
type Result struct {
	r    string
	url  string
	body string
}
func isInclude(rs []Result, r Result) bool {
	for _, temp := range rs {
		if temp.url == r.url {
			return true
		}
	}
	return false
}
func Crawl(url string, depth int, fetcher Fetcher) {
	rslt := make(chan Result)
	var rslts []Result
	go crawl(url, depth, fetcher, rslt)
	for {
		select {
		case v := <-rslt:
			if !isInclude(rslts, v) {
				rslts = append(rslts, v)
			}
			fmt.Println(rslts)
		}
	}
}
func crawl(url string, depth int, fetcher Fetcher, rslt chan Result) {
	if depth <= 0 {
		return
	}
	body, urls, err := fetcher.Fetch(url)
	if err != nil {
		rslt <- Result{"not found", url, ""}
		return
	}
	rslt <- Result{"found", url, body}
	for _, u := range urls {
		go crawl(u, depth-1, fetcher, rslt)
	}
}
func main() {
	Crawl("https://golang.org/", 4, fetcher)
}

fakeFetcherなどの部分は割愛しています。

実行結果

$ ./web_crawler 
[{found https://golang.org/ The Go Programming Language}]
[{found https://golang.org/ The Go Programming Language} {found https://golang.org/pkg/ Packages}]
[{found https://golang.org/ The Go Programming Language} {found https://golang.org/pkg/ Packages} {not found https://golang.org/cmd/ }]
[{found https://golang.org/ The Go Programming Language} {found https://golang.org/pkg/ Packages} {not found https://golang.org/cmd/ } {found https://golang.org/pkg/os/ Package os}]
[{found https://golang.org/ The Go Programming Language} {found https://golang.org/pkg/ Packages} {not found https://golang.org/cmd/ } {found https://golang.org/pkg/os/ Package os}]
[{found https://golang.org/ The Go Programming Language} {found https://golang.org/pkg/ Packages} {not found https://golang.org/cmd/ } {found https://golang.org/pkg/os/ Package os}]
[{found https://golang.org/ The Go Programming Language} {found https://golang.org/pkg/ Packages} {not found https://golang.org/cmd/ } {found https://golang.org/pkg/os/ Package os}]
[{found https://golang.org/ The Go Programming Language} {found https://golang.org/pkg/ Packages} {not found https://golang.org/cmd/ } {found https://golang.org/pkg/os/ Package os} {found https://golang.org/pkg/fmt/ Package fmt}]
[{found https://golang.org/ The Go Programming Language} {found https://golang.org/pkg/ Packages} {not found https://golang.org/cmd/ } {found https://golang.org/pkg/os/ Package os} {found https://golang.org/pkg/fmt/ Package fmt}]
[{found https://golang.org/ The Go Programming Language} {found https://golang.org/pkg/ Packages} {not found https://golang.org/cmd/ } {found https://golang.org/pkg/os/ Package os} {found https://golang.org/pkg/fmt/ Package fmt}]
[{found https://golang.org/ The Go Programming Language} {found https://golang.org/pkg/ Packages} {not found https://golang.org/cmd/ } {found https://golang.org/pkg/os/ Package os} {found https://golang.org/pkg/fmt/ Package fmt}]
[{found https://golang.org/ The Go Programming Language} {found https://golang.org/pkg/ Packages} {not found https://golang.org/cmd/ } {found https://golang.org/pkg/os/ Package os} {found https://golang.org/pkg/fmt/ Package fmt}]
[{found https://golang.org/ The Go Programming Language} {found https://golang.org/pkg/ Packages} {not found https://golang.org/cmd/ } {found https://golang.org/pkg/os/ Package os} {found https://golang.org/pkg/fmt/ Package fmt}]
fatal error: all goroutines are asleep - deadlock!

少し調べて出した答え

正直もう上のコード以上のことは思いつかなかったので、少しネットで調べました。簡単に調べたところa tour of goで出てきたことのみでは初心者にはレベルが高そうで、ほとんどの人がsyncパッケージのwaitGroupなどで同期処理を行っていました。
※sync.Mutexでも出来るみたいなので厳密にはa tour of goで学んだことだけで出来ますが上手くコードが組めなかったのでwaitGroupを使っています。

あと、mapを使っていますが、エクササイズの文章にもあるようにmapは並行処理での安全性は保証されていません。この安全性が何を指しているのかはわかりませんが、今回のエクササイズは何度実行しても順序は変化するものの必ず５つのデータを取得しているので問題ないかと思います。

コード

package main
import (
	"fmt"
	"sync"
)
// Fetcher is fetch interface
type Fetcher interface {
	Fetch(url string) (body string, urls []string, err error)
}
// FetchResult is structure
type FetchResult struct {
	result string
	url    string
	body   string
}
// Crawl is fake web Crawler
func Crawl(url string, depth int, fetcher Fetcher) {
	results := make(map[string]FetchResult)
	var w sync.WaitGroup
	w.Add(1)
	go crawl(url, depth, fetcher, results, &w)
	w.Wait()
	for _, result := range results {
		fmt.Println(result.result, ":", result.url, result.body)
	}
}
func crawl(url string, depth int, fetcher Fetcher, rslt map[string]FetchResult, w *sync.WaitGroup) {
	if depth <= 0 {
		w.Done()
		return
	}
	body, urls, err := fetcher.Fetch(url)
	if err != nil {
		rslt[url] = FetchResult{"not found", url, ""}
		w.Done()
		return
	}
	rslt[url] = FetchResult{"found", url, body}
	for _, u := range urls {
		w.Add(1)
		go crawl(u, depth-1, fetcher, rslt, w)
	}
	w.Done()
}
func main() {
	Crawl("https://golang.org/", 4, fetcher)
}
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)
}
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/",
		},
	},
}

実行結果

found : https://golang.org/pkg/ Packages
found : https://golang.org/pkg/os/ Package os
found : https://golang.org/pkg/fmt/ Package fmt
found : https://golang.org/ The Go Programming Language
not found : https://golang.org/cmd/

感想

長かったA Tour of Goもこれで終了です。これまでのエクササイズは私のGitHubにまとめています。noteでは取り上げなかったところも含めてREADMEmdにまとめていますが、私があとで見返した時にわかるように最適化している部分もあるのでみなさんの参考になるかはわかりません。しかし、プログラミング経験が浅い人間が書いたものなので、初心者目線で書いているつもりですので特に初心者で、いろいろ調べたけど納得いく答えが見つからずワラをもすがる思いの方は少しでも読んでみて頂ければと思います。


これまでにJavaScriptやPythonなどのリッチな言語しか使ったことがありませんでした。これらのリッチな言語はいろいろなAPIが用意してありそれを叩くだけで大抵のことが出来てしまいます。
一方でGo言語はfor文やif文を駆使して自分でAPIを作っている感覚でした。イメージとしては道具を組み合わせて製品を作るJavaScriptやPythonに対してGoは道具そのものを作っている感覚です。
もちろんJavaScriptやPythonなどのリッチな言語でも自分でAPIから作って作り上げることもあるでしょうし、Goも用意されているパッケージのAPIを叩くことで簡単にプログラムを組むことも出来るでしょう。しかしA Tour of Goで行った一連の学習の中では、順番はどうするかとかどこで分岐させるのかとか、そのようなプリミティブな操作に気を配るパズル的な力が試されていた気がしました。クイズとか割と好きなので苦戦しつつストレスも溜まりつつなんだかんだで楽しめたのではないかと思います。

さてこれからGoで何作ろっかなって感じです。以上。

この記事が気に入ったらサポートをしてみませんか？