現在電車中。64bitのハッシュ関数を使うと、どれも似たような結果になった。106億個URLがあると、大体全体の0.4%が衝突する。ちなみに、64bitの乱数を100億回生成しても大体6個しか衝突しない。シミュレート値と理論値が一致したので間違いないと思う。ハッ…

http://blog.clawpaws.net/post/2007/04/22/Good-Hash-Functions http://en.wikipedia.org/wiki/Hash_table と言っても、一回3時間以上かかる処理なのであと3回くらいしかできないお。速さ重視でSuperFastHashとMurmurHash2を組み合わせた64bitのハッシュ関…

Googleの中の人の論文、Detecting Near-duplicate for Web Crawling(PDF)に書かれているハッシュ値の圧縮アルゴリズムを実装、テストしてみた。この論文ではsimhashと言うアルゴリズムによって生成される64bitのハッシュ値を使用して、かなり効率的に、内容…

参加したいし飲みにも行きたい！黄さんやコーヒーの人達とも話したい！んだけど、なんかまだ予定がはっきりせず！うぜー。参加しても大丈夫なのかなぁ。なんで今年夏休みが合計で8日しかないの？

64bit版。 inline int nlz(unsigned long long x) { x = x | (x >> 1); x = x | (x >> 2); x = x | (x >> 4); x = x | (x >> 8); x = x | (x >> 16); x = x | (x >> 32); return __builtin_popcountll(~x); }tbb::parallel_reduceで4億個に対して統計を取っ…

O( (N/M)log(N/M) )をM回やるのでO(Nlog(N/M))で良いんだろけ。そうなると分割数を増やせばそれだけ速くなるという事になるね。ただその後にM個のファイルを同時に読んでいくことになるので、その辺の事も考慮しつつ色々やてみよう。とりあえずソートはお手…

100億個もできるのでどうしようかという話。めも:100億B=9.31GB。ハッシュ値は64bitなので、バイナリで保管しても74.48GBとなる。メモリ上でやるとかっこよす！なのだが、今は分散環境がないので難しい。なので、ハッシュ値を全部はき出してsort&uniqueする…

64bitのもの: そのまま使う 32bitのもの: 単体で分布を調査。その後全部の組み合わせで64bitのハッシュ値を生成しテスト 128bit以上のもの: 32bit単位で分布チェック。その後全部の組み合わせで〃 100億のURLをそれらしく生成する方法のめどはついたので、後…

http://www.cryptopp.com/ http://tanjent.livejournal.com/756623.html http://www.azillionmonkeys.com/qed/hash.html

意味があるのかどうかわからないけど、32bit単位でのハッシュ値の衝突をチェック中。そんで、分布をどうやって出力しようかと。32bitくらいだと、3億個のURLでもかなり衝突が発生してしまう。そして、そこそこ数が多いので、出てくるデータ量が半端ない。な…

32bitのハッシュ値の分布調査と、128bit以上のハッシュ値を32bit単位で切り出したときの分布調査。後は64bitのハッシュ関数調査。64bitのハッシュ関数って少ないよなぁ。。なんでだろ。

URLは使われている文字がものすごく限られてしまっているので、ハッシュ値が均等に分布するのかどうかが良くわからない。なので、その辺の調査もやってみる必要がありそう。逆に文字列に特化したハッシュ関数みたいなものも使ってみると良いかもしれない(こ…

Webクローラを作る際に重複URLを除去しつつ幅優先っぽい探索をしていく問題があるわけですが、今はそのときのURLの重複判定をどうやって効率よくやろうかという話を勉強中。その前処理として、URLに対するハッシュ関数を考え中。とりあえずURLの数が数なので…

諸事情で、本気でクローラ制作モードに移行することになりそうです。つか、あと2ヶ月の様子次第ではかなり人生計画を変更した方が良さそうな気がしなくもない。とりあえず今月はURLのsetみたいなものを効率よく作る感じの話に意識を集中させる事になりそうな…

らしい。URLの重複判定を1台で高速にやっちゃうお、というお話。なんか今まで使っていたクローラが色んな意味で好ましくないので、自分たちでクローラを作れると良いなーみたいな事になってて、その一環として調査ちう。なんかベストペーパー取っちゃったら…

ので頑張って調べてみようと思います。幸い Tomo’s HotLine のところで色々素晴らしい情報を公開してくださっており、 P2P研究者にお勧めするRFCとドラフト: Tomo’s HotLine ヘタレはまずこれを読むと良いぽいですね＞＜って訳で読んでます。あとはSkip grap…

なにが問題だったのか考察してみる。問題に対する考察ではなく、チームの行動に対する考察。うちのチームは(今年もそうなのかわからないけど)1位のにゃあさんのチームやtanakhさんのチームのようにコーダー(俺)+アルゴリズムな人2名で構成されている。アルゴ…

14位とか。非常に残念な結果となってしまいました。この一年は一体何だったんでしょうね。俺はなにをしてきたんでしょうか。自分に腹が立ちます。とは言え、コーディング速度は確実に向上しているのが分かった。大体以前の予測よりも2.5倍速くらいで書ける。…

明日の午後と土曜日、月曜の午後しか時間がない。これは困った。気合いで何とかするしかないな。とりあえず方向性は決まったので頑張ろう。