Help us understand the problem. What is going on with this article?

A Tour of Go(Exercise: Web Crawler)をツアーで学習したことだけで解答

目的

A Tour of Goは、Goを始める人なら誰でも通る道かと思うが、Exerciseは初見では結構頭を捻った。
仮に解けなくても、多くの解答がWebにあるので、理解して進めることができる。
ただし、最後の問題だけは、探してもツアーの中で学んだものだけで解かれたものがなかった。# 探し方が悪いだけかもしれないが。。。
今回、ツアーで学んだものだけで解いたので、(スマートではないだろうが)残しておく。

問題内容

A Tour of Go | Exercise: Web Crawler

同じURLを2度取ってくることなく並列してURLを取ってくるように、 Crawl 関数を修正してみてください(注1)。

補足: 工夫すれば Crawl 関数のみの修正で実装できますが、無理に Crawl 関数内部に収める必要はありません。

ひとこと: mapにフェッチしたURLのキャッシュを保持できますが、mapだけでは並行実行時の安全性はありません!

問題となるコード
exercise-web-crawler.go
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 <= 0returnしており、Crawl()関数を呼ぶ度にdepth-1している。
つまり、各URLに対して最大で3回Crawl()関数が呼ばれてる。

次に、fetcherの形と値を照らし合わせて見てみる。

39-44L
type fakeFetcher map[string]*fakeResult

type fakeResult struct {
    body string
    urls []string
}
54-61L
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つ

  1. URL取得の並列化
  2. 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に関しては、和訳してくれた方がいるので、そちらを見ればいいのかなと思います。

参考

hirano00o
SIer。お仕事は弊社グループ向けシステムの開発。SIだと手を動かすことが少ない。 とある案件でgolangを使ってからは勉強中。できればフルスタックで動く会社で働きたい。 golang/goa/C/Python/bash/ansible/docker/AWS/Oracle
https://hirano00o.hateblo.jp/
infra-workshop
インフラ技術を勉強したい人たちのためのオンライン勉強会です
https://wp.infra-workshop.tech/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした