ブログっ...!

自分についてのメモしかないので、見る価値がないよ。(人に説明する思いやりが皆無に近いよ。)

同前2

1) ブルームフィルタのお話。

サーバsに問い合わせたいファイル名のリストxがある。
このリストxに含まれる任意のファイル名のファイルfが、サーバsに全てあるわけではないらしい。
全てのfを実際に一気にリクエストすると通信負荷が大きいので、
「実体がsにあるf」のみだけにしたいところ。
sの管理するファイル数がほどほどに小さいなら、その全ファイル名リストをとってきて、それにfが含まれるなら、実際にお問い合わせする
という手でもいいが、まあ、そんな手で回るような世の中ではない。。

そこで現れるブルームフィルタ。詳しくは以下。
 

ブルームフィルタ - Wikipedia
 

この技術により、「fの実体がsにあるか」が確認でき、実際に通信するものを篩にかけることができる。
篩に通ったら、通信する。。
しかし、この篩は100%正確なわけではなく、
fの実体がsにないにもかかわらず篩に通してしまうことがある。
(小麦粉のダマとか普通に通す荒い篩あるよね。。)

・フィルタが「ないよ」って言ったら、ないことは確実 (本当はありました〜ということは起き得ない)
・フィルタが「あるよ」って言ったら、たまにないことがあるが大体はある


第一種過誤と第二種過誤 - Wikipedia

これ数理統計学の授業でやっていたけど、形式的に問題を解くゲーにしてしまったため、ほとんど記憶に残っていなかった。
帰無仮説については、その単語を聞く度に頭の中に「氷室京介」という固有名詞が浮かび、(語感が似ているからか?)
ほとんど内容が入ってこなかったことが印象ぶかい。

統計学の文章は、今全く読む気分じゃないので、搔い摘んで読んだ。超適当に説明することにする。

偽陽性(False Positive)は帰無仮説が実際には真であるのに棄却してしまう過誤
偽陰性(False Negative)は対立仮説が実際には真であるのに帰無仮説を採用してしまう過誤


ここで、ブルームフィルタの話に戻ってみる。
対立仮説 = 「ファイルがある」
帰無仮説 = 「ファイルがない」


ファイルfについて、サーバsのフィルタに問い質してみる。

i) フィルタ「ねえです」
a) fの実体がsにある場合
起き得ない。
b) fの実体がsにない場合
10割

ii) フィルタ「あるよ」
a) fの実体がsにある場合
8割くらい(例えば)
b) fの実体がsにない場合
2割くらい

偽陽性(False Positive)は帰無仮説が実際には真であるのに棄却してしまう過誤
ii)b)のケースにあたる。
もっていないファイルに対して、「もっている」と判定してしまうケース
偽陰性(False Negative)は対立仮説が実際には真であるのに帰無仮説を採用してしまう過誤
i)a)のケースにあたるが、ブルームフィルタでは起きえない。

もっているファイルに対して、「ない」と判定してしまうケース
 

2) コルーチン in C言語
以下、そのメカニズムをわかりやすく記録するために自己満足スライドを作成。
(もちろん、自分のためのメモなので、リンク先は自分だけしか見れない設定になっているし、そのURLも載せるつもりはない。)

アセンブリを読みたい気分になった。
以下の記事を読んだり。

Super Technique 講座〜longjmpと例外

(あと上記の記事を読んでる最中、気になるリンクがあった
Deep Side of Java〜Java 言語再入門 第2回 〜 例外
Super Technique 講座〜シグナルとコールバック)