現在電車中。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倍速くらいで書ける。…
明日の午後と土曜日、月曜の午後しか時間がない。これは困った。気合いで何とかするしかないな。とりあえず方向性は決まったので頑張ろう。
早大生ならAcademic Writingの授業を取れ。あと、俺の場合、アメリカの英会話学校でTOEFLコースを取ってて、そのとき丁度CBT対策で毎週木曜日にエッセーの授業をやってたのでそれが大きいと思います。こればっかりはやはり人に教わった方が良いかと。(日本の…
ほとんどなんもやってないですサーセンｗｗｗ 前日に日本語の超簡単なTOEFL-iBTスピーキングマニュアルをざっと読んだだけ。でも問題の傾向がわかったのでかなり助かりました。問題の傾向を知る＆Reading, Listening, 休憩, Speakingの解説時間をフル活用し…
英単語学習 Essential Words for the TOEFL 論文＆専門書読み読み たぶんこれだけしかやってない。scanningとかskimmingとかの特殊なテクは勉強してないです(昔少ししましたが)。俺の単語力は自慢じゃないけど東大受験しようとしてる人には全くかなわないで…
実は特に頑張ってないですが、今年の4月から少人数制の英会話の授業を取ってました。Tutorial Englishっつー授業があります。これは早大生なら必ず取るべき。やっぱ、自分で話し始めると一気にlistening力が向上するので良いと思います。
ｋｔｋｒ！あと680ドルほど出費を覚悟してたのでもの凄く助かりまた。 Reading Listening Speaking Writing Total 27 28 17 28 100 これ100点行ってるよね＞＜ 見間違いじゃないよな！やべー超嬉しい！80点くらいだとおもてたよ！Speakingは前日にawakiaに貸…
雰囲気がだんだんわかってきた。普通の家庭用のルータと全く同じだねこれ。とりあえず階段を上ったり降りたりしまくった甲斐がありました。
Linux のネットワーク設定を勉強してるんだけど良くわかりません＞＜ カスですいません＞＜ネットワークの疎通を確認するには？〜ping／traceroute〜：ネットワーク・コマンドでトラブル解決（1） - ＠ITとりあえず学習メモ。1台だけ設定はだいぶわかってき…
この間の模擬予選の上位は、実は半分くらい2年生以下なんじゃ？これからが楽しみすぎる。うちの大学の状態を見る限り本当に羨ましい限りです。つーか早稲田大学は、俺かawakiaが海外に行ってしまえば今年で終了です。後輩に全く動きが見られません。あんなウ…
お疲れさまでした。id:awakiaの到着遅れとプリンタの紙切れなどが重なって開幕から出遅れたけど何とか8位。でもCが解けなかったのが切なすぎる。問題の難易度としてはA 問題A 最初変な順番で計算したせいでWAが出てオワタムードになったけどおｋ。 問題B ソ…
あ、ありのまま今起こったこｔｒｙ 「minkeさんがranhaたんにお勧めしてるのを傍観してたらいつの間にか注文確認メールが届いていた」 な、なにを言ってるのかｒｙ関数型言語で(というかHaskellで)、効率が良く美しいデータ構造の書き方を知りたいなーと丁度…
すいませんでした。 > ghc -package wx HelloWorld.hs > ghc -package wx -optl -mwindows hoge.hs で起動時にコマンドプロンプトがでなくなるそうです(tanakhさんの日記より)こんだけ。なんか -package 付けてwx指定すればおｋらしい。ちなみにできたexeフ…
