A Tour of Goの練習問題を解説するシリーズ(11/11) – Exercise: Web Crawler

みなさん、こんにちは。人類をGopherにしたいと考えているまるりんです。

A Tour of Goはプログラミング言語Goの入門サイトです。 このシリーズではA Tour of Goの練習問題を解説します。

今回は以下の問題を扱います。

問題
Exercise: Web Crawler
解答
https://go.dev/play/p/lI_m9tDaawy

---

処理の効率化のメリットを測定するために、サンプルコードのFetch()で必ず1秒待つようにします。 これはダウンロードにかかる時間を擬似的に表現しています。

func (f fakeFetcher) Fetch(url string) (string, []string, error) {
    time.Sleep(time.Second)
    if res, ok := f[url]; ok {
        return res.body, res.urls, nil
    }
    return "", nil, fmt.Errorf("not found: %s", url)
}

ソース
https://go.dev/play/p/ysD46_jHCzn

実行結果

$ time go run 1.go
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/
not found: https://golang.org/cmd/
found: https://golang.org/pkg/fmt/ "Package fmt"
found: https://golang.org/ "The Go Programming Language"
found: https://golang.org/pkg/ "Packages"
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/
go run 1.go  0.18s user 0.20s system 2% cpu 13.354 total

全部で13のURLをダウンロードしているので約13秒かかっています。

このプログラムにダウンロード予定のURLをダウンロードしない処理を加えてみます。 ダウンロード処理の前にfetched=trueとしておくことがポイントです。 ダウンロード後に真にしていると追加予定の並行処理にて、ダウンロードに時間がかかった場合に複数回取得しに行く可能性があります。

ソース
https://go.dev/play/p/pVYBZP82JJ2

実行結果

$ time go run 2.go       
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/fmt/ "Package fmt"
found: https://golang.org/pkg/os/ "Package os"
go run 2.go  0.19s user 0.19s system 6% cpu 5.506 total

このプログラムに並行ダウンロードする処理を加えてみます。チャネルでの実現は難しそうなのでsync.WaitGroupを使います。 使用する関数の簡単な説明です。

• wg.Add() - カウンタをインクリメント
• wg.Done() - カウンタをデクリメント
• wg.Wait() - カウンタが0になるまで待つ

メインスレッド内でスレッドを起動する分だけwg.Add()し、起動したスレッド内でwg.Done()します。メインスレッドはすべてのスレッドが終了するまでwg.Wait()で待ちます。

ソース
https://go.dev/play/p/lI_m9tDaawy

実行結果

$ time go run 3.go
found: https://golang.org/ "The Go Programming Language"
not found: https://golang.org/cmd/
found: https://golang.org/pkg/ "Packages"
found: https://golang.org/pkg/os/ "Package os"
found: https://golang.org/pkg/fmt/ "Package fmt"
go run 3.go  0.21s user 0.20s system 12% cpu 3.456 total

並行化することにより、直列してダウンロード処理しなくて良いのでさらに速くなりました。sync.WaitGroupを使えば特に難しくない問題でした。