moratorium

Tx: Succinct Trie Data Structure

数千万件の要素(URL)のmapを作りたかったので、Txを試してみた。C++のstd::mapは元データの数倍ものメモリを食ったのに対して、Txは元データの40.5%程のメモリしか必要としなかった。元データの量は大体数Gだったので、十分メモリに保持できてしまう。

検索時間はstd::map等に比べて落ちはするようだが、10msで終わるなら十分すぎるほどなので採用決定。

もっと馬鹿でかいデータを入れたりしても落ちたり、データが壊れたりする事も無かったので安心して使えそう。他のアプリケーションにも色々適用できそうなので、書いてみた。

1億件とかそれ以上になると、ディスクを併用しないと無理臭いなぁ。となると流石に処理速度のほうが気になる。そうなって来ると、STXXL: Standard Template Library for Extra Large Data Setsが気になり出す。

flock(2)ではなくlockf(3)だとメールを頂いた。

確かにlockf(3)に変えてみると(lenは0)、排他してくれない。なんで挙動が違うんだ・・・。

２つの違いが分かったらまた書きます。

以下の論文を渡されたので読んでました。

• A Maximum Entropy Approach to Natural Language Processing
• MEによる日本語係り受け解析
• 相対的な係りやすさを考慮した日本語係り受け解析モデル [pdf]

統計的言語モデル(北 研二,辻井 潤一)も参考にしました。MEについては最初の奴よりこの本の方が分かりやすかったです。

来週から実装の予定ですが、どうしたものか。3つ目は精度は出てるけど学習の所でIterative Scalingをしないといけない。この方法を完全に理解してないのと、実装が大変そうというのがある。後2週間しかないので、週明けにその辺を辻井研の人に相談しよう。

しかし工藤さんや岡野原大先生には僕には見えてないものが見えているようにしか思えないなー。

P.S
IterativeScalingも一応理解した。

んでこれはMapReduceっぽく実装出来そう。で、それをやると分散並列化出来て、大規模な素性を持つような学習が可能になりそう。これ絶対ごっごるでやってるなー。

以前人づてに、flock(2)がプロセス間排他はするけどスレッド間排他はしないという話を聞いた。

これが本当だと、今まで自分が書いたマルチスレッドアプリケーションのファイルを扱う部分の根幹が揺らいでしまう。特にファイルが壊れたりするような現象は見られなかったので今まで放置してきたが、非常に心配になってきたので調べてみた。

辻井研で係り受け解析をやることになりました。

1期の人も2期の同じ人も係り受け解析みたいです。何故か人気。MEやSVMといった機械学習系の知識を仕入れるのが目的です。

ただ、水曜日まで五十嵐先生のUIの課題のデスマです。こういうの、いまいち気乗りがしないんだよなぁ・・・。なんというかシステムコールを叩いてる方が楽しい。

金曜日、新入生歓迎飲み。ちょっと人数少なめだったなー。

土曜日、新卒の人たちと飲み。金融系とか保険系は大変だなぁと思った。物理学科から某大手メーカーに就職した人が、某G社新卒の人を知ってて、結構盛り上がった。

帰ってから、こんな記事が出てたので、blogWatcherの論文を一通り読んだ。

今週一週間は不眠が続いて、体調が崩壊。胃の辺りがぶっこわれてる気がする。

Linux 2.6.17より導入された新しいシステムコールである「splice(2)」を使ったファイルコピープログラムを作ってみました。

参考: C言語: UNIX最速ファイルコピー
参考: splice(2) - splice data to/from a pipe

各研究室を巡回する演習３ですが、今日一期目の石川研が終了しました。

google.co.jpの検索結果の左側の空白が気持ち悪い。自分だけ？

参考: google.com

まぁ英単語に対して日本語サイト出してくるので、デフォルトは.comの方ですが。

Google Tech Talk Showcase

Google Tech Talksって今まで検索結果でしか一覧が無かったので、こういう風にジャンル毎に整理されてると非常に見やすくてよいなぁ。

といっても、個人的にはomoさんのブログでかいつまませて頂いているのと、「Building Large Systems at Google」を見たぐらい。