2011年09月29日

自分が著者に入っている論文が参考文献に入っているのに自分の名前が著者名から抜けているとき～

ま，2番目以降なのでどうでもよいのだけど．

とりあえず今後論文書くときには参考文献により気を付けることにしよう．

閑話休題．

正規表現マッチングを並列化するのにSSFAというオートマトンを作るとマッチングの計算量には状態数が現れなくなって嬉しいよねという発表を聞いた．「並列化＝状態間の写像の合成を分割して計算」でよいのだけど，どうせ現れる写像は限られているので，毎回写像の合成を計算する代わりに一文字読んだ時の写像との合成結果を文字をキーにしてテーブルで引けるようにしましょうよと．まあ，NFAをDFAに変換するのと同じ．

で，NFAをDFAに変換するのと同じなので，そこでの問題が再発するんじゃないのかなぁとか疑問に思った．通常，テーブル（DFA）を作っておけばテーブル引くのは写像の合成を毎回計算する（NFAの合成では状態数の3乗の計算量）よか速い．けど，最悪テーブルはNFAの状態数の指数の大きさになるので，その時にはキャッシュミスの効果も出てきて写像の合成計算したほうが速かったりしないのだろうか，という疑問．アルファベットを {a, b} にして，.*a.*a.{20} とか（aが2回出てきて，かつ，後ろから21文字目はaであるべし）．NFAの状態数は22だけど，SSFAの状態数は大きいんじゃないかなと．まあ，実験してみないと分からん．

閑話休題．

何となく，足の薬指が中指に微妙に押しつぶされるような歩き方になっているような気がする．なので長距離（10キロ）歩くとそこにマメができると．よく考えたら西沢渓谷の時も富士山の時も（別の靴だけど）ここにマメができていたっけね．去年靴を変えるまではもっと長距離を歩いてもこんなことなかったので，ここんとこ履いている靴達が微妙に合っていないのかも知れない．とりあえず次に靴を買うとき考えよう．