% factor 2003 2003: 2003 % factor 2004 2004: 2 2 3 167
XML Base を調べる。
ふむ。html の base 要素と違って、相対 URI が使えるのか。
リモートのログファイルを継続的に転送してみる。
% ssh remote-host ruby > local-log <<'End'
f = open("remote-log")
loop {
unless line = f.gets
STDOUT.flush
sleep 1
next
end
print line
}
End
なんとなく IoC が気になる。
PicoContainer には Ruby 実装もあるのだが、 静的な型がないからあまり自然にはいかないだろうと思いつつサンプルを眺めてみると やはり明示的に指定する模様。
どっちかっていうと、attr_writer でクラス名を指定するという慣習にすれば Type 2 IoC で自然になるような。
wildcard のマッチングをデータ量に対して線形時間で済ますのがなぜ簡単なのかを考える。
もちろん、wildcard は regular expression のサブセットみたいなものだから、 regular expression と思って DFA に変換すればデータは一回なめれば済むわけで、 それを考えれば線形時間で済ますのが可能なことは当然である。
問題は、wildmat という実装 - 今は INN に入ってるのが最新か? - が DFA という概念を使用せずに線形時間での処理を実装しており、 なぜあんな簡単な実装で済むのかがいまひとつ納得できない、ということである。
wildmat のコメントには * が一度に 2つ以上有効になることがないから、 とか書いてある。 これは A*B*C をマッチさせるときに、最初の * の長さを伸ばしながら後続の B*C を試して行くのだが、 B のマッチが成功して次の * にたどり着いた場合には最初の * を伸ばすのはやめてしまうということである。 たしかに、最初の * をもっと伸ばすと次の B を見つかるというケースは、 最初の B を見つけた後に次の * を適切な長さだけ伸ばしたケースと同じになるので、 伸ばすのをやめてもマッチするかどうかの判断はとくに問題なさそうである。
しかし、これは、オートマトンの世界で考えるとなにをやっているのだろう?
... 考える .... しばらく考える ... そーか。wildcard の * というのは regular expression の .* で、 これは NFA で考えると任意の文字を受け取ると自分自身に遷移する状態になる。 また、wildcard は一般に A1*A2*A3*...*An という形をしているので、 NFA もそれと同じような形の、 左に進むには * に対応する状態を通らなければならない形になる。
そして、NFA を状態を分岐させながら一度に (DFA 的に) 動かすと、 * の左の状態に初めて到達したときに ε遷移でつながっている * の状態とその右の状態に同時にに到達する。 ここで、* の状態はいったんそこに到達したらそれ以後はずっと到達しっぱなしになる。 そのため、* の左の状態がどう変わろうが * の右の状態に影響を及ぼすことはない。
だから、A1, ... An のどこまで到達しているかと、 到達した先頭での状態を記録しておけばよく、 それよりも左の状態は管理しなくて良い。
また、wildcard の * 以外の要素は文字と ? と [...] で、 すべて長さは固定なので、 (素朴にやれば)だいたい固定文字列の探索と同じようなかんじで済む。
というわけで、一度に記録しておかなければいけないのは A1, ... An のどこまで到達したかと、到達した先頭の中での状態だけで済む。 なるほどこれなら簡単に済むというのは納得できる。 というか、wildmat よりもさらに簡単に出来てもおかしくないかもしれない。
さて、wildmat と glob ではちょっと状況が異なる。 原理的に線形時間で済むというのは同じであるが、 簡単に済むかというところは話が変わって来る。
これは * が / にマッチしないので、 regular expression は [^/]* になって、 [^/]* だと / を受け取ったときに自身に遷移できないので、 「* の状態はいったんそこに到達したらそれ以後はずっと到達しっぱなしになる」という性質が成り立たないのである。
ただし、**/ は ([^/]*/)* で、これは / を含む任意の文字を受け取ったときに 自身に遷移する状態になる。 とすると、おそらく **/ については wildmat と同様の簡略化が可能で、 **/ で区切られた間を / で区切ってからどうにかすればどうにかなるのかもしれない。
とある素朴らしき実装の測定:
% ruby -e '300.times {|n|
t1 = Time.now
File.fnmatch("*x*x*x*z", "x" * n)
t2 = Time.now
puts "#{n} #{t2 - t1}"
}
'
gnuplot で fit させてみると、n**3.7 くらいで増えていく。
もうひとつの素朴らしき実装の測定:
% mkdir -p a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a
% ruby -e '6.times {|n|
t1 = Time.now
Dir.glob("a/**/" * n + "b")
t2 = Time.now
puts "#{n} #{t2 - t1}"
}
'
というか、素朴さを感じるにはどのくらい open しているかを調べればいいか。
% strace -e open ruby -e 'Dir.glob("a/**/" * 3 + "b")'
同じディレクトリを繰り返し open する様がよくわかる。 なんとも素朴なものだ。
そーいや、wildmat のソースには XLFD な例があるんだよな。 ということは、X にもつかわれているのだろうか。
というわけで、調べてみると、 xc/config/util/mkshadow/wildmat.c というのが見つかる。 ふむ。これはこれでそうなのだが、サーバ本体で使っているわけではないのか。
むしろ / は区切りであって、シンボルではないと考えるべきか。 / で区切られた間の文字列を単一のシンボルと考えれば、 ** はそういうシンボルの並びに対する * と考えられるか。
論文に飽きる。 現実逃避に以前からいつか作り直そうと思っていた make like なものを作る。 そういえば論文用に latex を起動する Makefile もぼろくてだめなんだよなということで 作ったので書き直す。 でも、latex は不動点になるまで繰り返さないといけないから結局のところ あまりきれいには書けない。 それはそれとしてどこがぼろかったんだっけと記憶を探ると 確か bibtex まわりだったはずだが、 今書いている論文にはまだ bib を用意していないことに気がつく。 しょうがないので用意する。
% google-count {一,二,三,四,五,六,七,八,九}の鳥居
6740 一の鳥居
2410 二の鳥居
823 三の鳥居
23 四の鳥居
5 五の鳥居
0 六の鳥居
0 七の鳥居
1 八の鳥居
0 九の鳥居
昨日から今日にかけて、core が 3つも採れた。大漁である。
% head bugs/2004011[56]*/backtrace
==> bugs/20040115-131605/backtrace <==
Core was generated by `ruby ./main.rb -v'.
Program terminated with signal 11, Segmentation fault.
#0 0x0809991b in rb_reg_prepare_re (re=1088459584) at re.c:849
849 RREGEXP(re)->ptr->fastmap_accurate = 0;
#0 0x0809991b in rb_reg_prepare_re (re=1088459584) at re.c:849
#1 0x08099a31 in rb_reg_search (re=1088459584, str=1087528064, pos=0, reverse=0) at re.c:899
#2 0x0809a4d3 in rb_reg_match (re=1088459584, str=1087528064) at re.c:1510
#3 0x08055d96 in rb_eval (self=1076920776, n=0x40371fd8) at eval.c:2720
#4 0x08055f8e in rb_eval (self=1076920776, n=0x40371e48) at eval.c:2783
#5 0x0805c669 in rb_call0 (klass=1076920696, recv=1076920776, id=10289, oid=10289, argc=0, argv=0xbffef4f4,
==> bugs/20040115-172026/backtrace <==
Core was generated by `ruby ./main.rb -v'.
Program terminated with signal 11, Segmentation fault.
#0 0x0809992b in rb_reg_prepare_re (re=1079837296) at re.c:849
849 RREGEXP(re)->ptr->fastmap_accurate = 0;
#0 0x0809992b in rb_reg_prepare_re (re=1079837296) at re.c:849
#1 0x08099a41 in rb_reg_search (re=1079837296, str=1079894636, pos=0,
reverse=0) at re.c:899
#2 0x0809a4e3 in rb_reg_match (re=1079837296, str=1079894636) at re.c:1510
#3 0x08055d96 in rb_eval (self=1079844916, n=0x402994dc) at eval.c:2720
#4 0x08055f8e in rb_eval (self=1079844916, n=0x40298a64) at eval.c:2783
==> bugs/20040116-002056/backtrace <==
Core was generated by `ruby ./main.rb -v'.
Program terminated with signal 11, Segmentation fault.
#0 0x0809992b in rb_reg_prepare_re (re=1079765836) at re.c:849
849 RREGEXP(re)->ptr->fastmap_accurate = 0;
#0 0x0809992b in rb_reg_prepare_re (re=1079765836) at re.c:849
#1 0x08099a41 in rb_reg_search (re=1079765836, str=1079816996, pos=0,
reverse=0) at re.c:899
#2 0x0809a4e3 in rb_reg_match (re=1079765836, str=1079816996) at re.c:1510
#3 0x08055d96 in rb_eval (self=1079786536, n=0x402994dc) at eval.c:2720
#4 0x08055f8e in rb_eval (self=1079786536, n=0x40298a64) at eval.c:2783
しかも、いつもの delete_if じゃなくて rb_reg_prepare_re のほうである。 これはいい機会というわけで、ちょっと調べてみる。
#0 0x0809992b in rb_reg_prepare_re (re=1079765836) at re.c:849
849 RREGEXP(re)->ptr->fastmap_accurate = 0;
(gdb) rp re
T_STRING(0x405beb4c): "\A(?-mix:[\r\n\t ]+)?((?-mix:[^\x00- ()<>@,;:\\"\/\[\]?={}\x7f]+))(?-mix:[\r\n\t ]+)?/((?-mix:[^\x00- ()<>@,;:\\"\/\[\]?={}\x7f]+))(?-mix:[\r\n\t ]+)?((?-mix:(?:;(?-mix:[\r\n\t ]+)?(?-mix:[^\x00- ()<>@,;:\\"\/\[\]?={}\x7f]+)(?-mix:[\r\n\t ]+)?=(?-mix:[\r\n\t ]+)?(?:(?-mix:[^\x00- ()<>@,;:\\"\/\[\]?={}\x7f]+)|(?-mix:"(?:[\r\n\t !#-\[\]-~\x80-\xff]|\\[\x00-\x7f])"))(?-mix:[\r\n\t ]+)?)*))\z"
(gdb) p *(struct RRegexp *)re
$1 = {basic = {flags = 4103, klass = 1075628116}, ptr = 0x187, len = 143765344, str = 0x1fe <Address 0x1fe out of bounds>}
(gdb) rp 1075628116
T_CLASS(0x401cc854)
(gdb) rp rb_cRegexp
T_CLASS(0x401c598c)
(gdb) rp rb_cString
T_CLASS(0x401cc854)
(gdb)
ふむ。Regexp が String にすり変わっているらしい。
とりあえず rb_reg_match に Check_Type をいれておくか。
「採る」より「捕る」のほうが適切か?
... (goo の大辞林で)調べてみると、 もちろん core に関する用例は載っていないが、 「採る」は「集める。採集する。収穫する。」で、 「捕る」は「捕らえる。つかまえる。捕獲する。」ということで、 後者の対象のほうがより動物というか動き回っている感じである。
さて、ここで問題は core は動き回っている感じがするかどうかである。 あんまり動いていない気がするから「採る」かなぁとも思うが、 core はプロセスの死体で、生前のプロセスなわけであきらかに動いてるから、 死体が動かないからといって「採る」とするのは不適切かとも思う。
あるいは、bug と表現すれば捕るのほうが適切か。 でも「昆虫など小さな動物の場合は「採る」とも書く」とあるしなぁ。
almake で --clean オプションを実装する。
生成したファイルは全部管理しているため 消すべきファイルはわかるわけで、 ユーザが clean ターゲットを書く必要はない。
... というのは最初から分かっていたのだが、予想外に悩んでしまった。 ファイルというのは大域変数だからかもしれない。
そういえば、同様に .cvsignore も生成してもいいかもしれないな。
% ruby -rsnippet/float -e '
s = "4294967295.999990"
10.times {
p [s, s.to_f.decode]
s.succ!
}'
["4294967295.999990", ["0 (+)", "10000011110 (p31)", "(1.)1111111111111111111111111111111111111111111111101011"]]
["4294967295.999991", ["0 (+)", "10000011110 (p31)", "(1.)1111111111111111111111111111111111111111111111101101"]]
["4294967295.999992", ["0 (+)", "10000011110 (p31)", "(1.)1111111111111111111111111111111111111111111111101111"]]
["4294967295.999993", ["0 (+)", "10000011110 (p31)", "(1.)1111111111111111111111111111111111111111111111110001"]]
["4294967295.999994", ["0 (+)", "10000011110 (p31)", "(1.)1111111111111111111111111111111111111111111111110011"]]
["4294967295.999995", ["0 (+)", "10000011110 (p31)", "(1.)1111111111111111111111111111111111111111111111110110"]]
["4294967295.999996", ["0 (+)", "10000011110 (p31)", "(1.)1111111111111111111111111111111111111111111111111000"]]
["4294967295.999997", ["0 (+)", "10000011110 (p31)", "(1.)1111111111111111111111111111111111111111111111111010"]]
["4294967295.999998", ["0 (+)", "10000011110 (p31)", "(1.)1111111111111111111111111111111111111111111111111100"]]
["4294967295.999999", ["0 (+)", "10000011110 (p31)", "(1.)1111111111111111111111111111111111111111111111111110"]]
区別できないはめにはなりそうにないか。つまらん。
% for c in {ガ,ギ,グ,ゲ,ゴ,ザ,ジ,ズ,ゼ,ゾ,ダ,ヂ,ヅ,デ,ド,バ,ビ,ブ,ベ,ボ}
do
google-count $c${c}虫
done
1 ガガ虫
0 ギギ虫
0 ググ虫
1 ゲゲ虫
0 ゴゴ虫
448 ザザ虫
2 ジジ虫
0 ズズ虫
0 ゼゼ虫
7 ゾゾ虫
3 ダダ虫
1 ヂヂ虫
0 ヅヅ虫
7 デデ虫
0 ドド虫
12 ババ虫
0 ビビ虫
2 ブブ虫
0 ベベ虫
0 ボボ虫
[latest]