dblp.xml のパースの続きと Bloom Filter
私の共著者は６人います（20秒/1人）。私の共著者の共著者は３９３人います（2分４０秒/7人）。私の共著者の共著者の共著者は7451人います（２時間/400人）。それ以上は出会えていません。
今回は、std::setが遅いのかなぁ、と思ってちょっと簡単なテストをしてみました。次のことに注目してみました。
- 要素authorの個数は、どれくらいなのか？
- dblp.xml に登録されている著者数は、何人なのか？
結果は、以下の通りです。
全author要素数の4/5が重複部分になっているようです。なので、やっぱり重複部分をフィルタしてあげると処理が簡潔になるような気がします。
std::setの代わりに、ここで公開されいる、Open Bloom Filter を使うと速くなるかなぁと思って利用してみました。（Bloom Filter に関しての覚書は、数式の書き方が分からないので週末に修正しようと思います。）利用した結果です。誤検出が発生しないように、いろいろパラメータを変えてやってみましたが、（22秒→19秒）ぐらいの短縮にしかなりませんでした。std::tr1::unordered_mapやgoogle::sparse_hash_mapとの比較は、これからやってみようと思っています。
距離５までのグラフを１時間くらいでなんとかしたいです。pthreadを何も考えずに使ったら、逆に遅くなりました。キャッシュ効率などを考えてみたいです。また、ストリームアルゴリズムも考える必要があるかもしれないので、次のテキストを再読しようと思います。
