はじめまして
愛知県で働く、ソフトウェアエンジニアのflipfrogといいます。
Go言語を知ろうと思い、A Tour of Goを一通りやってみました。
A Tour of Goをやっただけなので、他にも知らない機能があると思いますが、Go言語はシンプルで言語仕様が頭の中に入りやすかったです。
説明を読みながら課題をこなして、最後までたどり着きました。
最後の課題は、明確に正解が提示されていないので、どのような実装にしたかを記録しておこうと思います。
この課題は、並列処理と排他制御を使った疑似Webクローラーの実装でした。
修正後のコードは、GitHubのリポジトリに保存してあります。
課題で提示された実装からの修正差分は、コミットを参照して下さい。
課題の指示
- ウェブクローラ( web crawler )の並列化
- 同じURLを2度取ってくることなく並列してURLを取ってくる
ベースのコードは提供されているので、この課題ではそれを修正します。
２つめの「同じURLを2度取ってくることなく並列してURLを取ってくる」という指示には、URLを重複して結果に含めないのと、並列で実行するスレッドから重複を管理するデータへのアクセスに排他制御をかけるということが含まれていると考えました。
どのように実装を修正したか
- ウェブクローラ( web crawler )の並列化
Crawl関数は、与えられた１つのurlから再帰的にリソースに含まれる下位のurlを探索します。 下位urlの探索には、再帰呼びをしているので、その処理を別スレッドで実行するように修正しました。
上位のurlから下位のurlを呼び出しますが、上位側では下位urlの探索が終わるまで待ってから制御を上位に戻すようにしました。
+ var wg sync.WaitGroup for _, u := range urls { - Crawl(u, depth-1, fetcher) + wg.Add(1) + go func(u string) { + defer wg.Done() + Crawl(u, depth-1, fetcher, c) + }(u) } + wg.Wait() return }
並列化の制御のために、Crawl関数の呼び出しにクロージャをはさみました。
wg.Add(1)を呼び出したあとにgoroutineを起動、クロージャの処理が終了した時点でwg.Done()が呼び出されるようにしています。 呼び出し元では、全てのスレッドが終了するのをwg.Wait()を使って待ちます。
また、この記事を書いている時点で、main関数でsync.WaitGroupを作成して、Crawl関数の引数渡しで持ち回った方がより並列度が上がるかもしれないと思いました。
- 同じURLを2度取ってくることなく並列してURLを取ってくる
重複しないURLを作成するために、mapを使うことにしました。
更に、排他制御も必要なので、前の課題で作成したSafeCounterを使うことにしました。
SafeCounterオブジェクトへのアドレスを、Crawl関数に渡します。
c := SafeCounter{v: make(map[string]int)}
Crawl("https://golang.org/", 4, fetcher, &c)
Crawl関数では、SafeCounterをロック後、渡されたurlが未登録の場合、そのurlをmapに登録しロックを解除します。 既に登録されている場合は、ロックを解除して制御を呼び元に戻します。 これにより、テストしてセットする処理をアトミックに処理できるようになりました。
c.mu.Lock()
if c.v[url] > 0 {
c.mu.Unlock()
return
}
c.v[url]++
c.mu.Unlock()
全てのスレッドの処理が終わったら、SafeCounterオブジェクトに格納されたurlを表示してmain関数の処理が終わります。
for url, _ := range c.v { fmt.Println("*** ", url) }
以下は、このプログラムをコンソールで実行したときの出力です。
$ ./exercise found: https://golang.org/ "The Go Programming Language" not found: https://golang.org/cmd/ 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" *** https://golang.org/ *** https://golang.org/pkg/ *** https://golang.org/pkg/os/ *** https://golang.org/pkg/fmt/ $
***が先頭に付いた行が、収集されたurlの一覧です。
IDEを使うメリット
この課題を実装する過程で、処理結果が想定どおりにならなくて困っていたときがありました。 原因は、ループ変数を、クロージャ内部で使っていたことでした。 そして、ループ変数をクロージャ関数の引数として渡すことで問題を解消しました。
そのとき、たまたまコードをIDEで編集してみようと思い、コードを開いたところ下記のようなワーニングが表示されて気づくことができました。 IDEを使っていなければ、更に余計な時間を使ったと思います。
