天泣記

2004/06/01

cvs import の引数には release tag を複数指定できることに気がつく。

うぅむ。何に使うんだ?

IRC でわたなべさんがいっていた、commit mail に MD5 を載せる、というのをやってみる。これがあれば、各 revision が commit 後に書き換えられたら、確認できるはずである。 (commit mail を subscribe している全員のマシンを crack でもしないかぎり)

cvs.m17n.org では、commit mail に自作の cvs-info というのを使っているので、これを改造する。

... あいかわらず loginfo のインターフェースは腐っていることを再認識しつつも、なんとか実装できた。

2004/06/03

#1

ここまでくると、diff が欲しくなる。

が、chroot 下には rcsdiff,cvs,diff などというコマンドはないので、自分で実装しないといけないか。

いや、RCS file に入っている delta を変換するという手はあるかも知れない。でも、それだと default branch が外れるときを扱えないか。

2004/06/04

#1

GNU diff の --minimal が意味を持つ例を見つける。

% ruby -e '512.times { puts "abcde".split(//) }' > a 
% ruby -e '512.times { puts "bdece".split(//) }' > b 
% /bin/diff a b | grep '[<>]' |wc -l
    2048
% /usr/local/bin/diff a b | grep '[<>]' |wc -l 
    2556
% /usr/local/bin/diff --minimal a b| grep '[<>]' |wc -l         
    2048

/bin/diff が SunOS 5.8 の diff で、 /usr/local/bin/diff が diffutils 2.7 なのだが、 --minimal をつけない場合、diffutils のほうが、行の追加、削除の数が多くなっている。

これが実際に起きることを認識したのははじめてな気がする。

2004/06/05

#1

東京に出かける。

最近、寝ても醒めても LCS について考えているのだが、移動している最中に、 Sun Wu の O(NP) アルゴリズムの意味を正確に理解した感じがする。

あのアルゴリズムは、先頭から特定の場所までの距離だけでなく、その特定の場所から最後までの距離(の最小)を考慮して探索する。これは、かなり前に習った覚えのある、A* search をやっていると解釈できる。

さて、Claus Rick のアルゴリズムも、そのようにできないだろうか?

2004/06/07

#1

O(NP) のを実装して、visualize してみる。

うぅむ。2次元空間が探索範囲なのだが、実際に探索を行う状態がなんとなく思っていたよりもずっと少ない。これが(LCS が長いときに)速いというのはうなずける。これで LCS が短いときも速ければ文句はないのだが。

ふむ。LCS が短いときに Claus Rick とかのが速い理由の closest を Sun Wu のに導入することを考えたほうがいいだろうか。

2004/06/10

#1

cvs を update する。

せっかくなので、cvs-info の MD5 でリポジトリの内容を検査する。

やってみると、メールに含まれていた 1150個の revision の MD5 について、現在 co できる revision が同じ MD5 をもつことが確認された。

ふむ。メールに含まれていない revision が存在しないことを確認する必要があるな。

#2

また、やっと、pserver は anonymous 専用のユーザで動かすようにする。

ローカルパッチを当てていると、version up がおっくうになるので、 anonymous cvs 用のバイナリはローカルパッチを当てないで運用することにする。

このため、cvs のバイナリは chroot の中に置くことになった。

ただ、かわりというわけではないけれど、 anonymous cvs server に要らないものは configure で disable し、またテンポラリディレクトリを anonymous cvs 専用のディレクトリを指定してみた。

それで、/tmp は committer しか書き込めないようにした... つもりだったが、committer さえも書き込めないという設定になっていて指摘されてしまった。

2004/06/11

#1

つらつらと考えていると、時間は O(p(m-p)) ですむんじゃないかという結論に達する。 (m は短いほうの列の長さで、p は LCS の長さ)

あとは空間が linear ですむかどうかか。

これらの問題を避ける一番確実な方法は Time#utc_offset である。が、これは Ruby 1.6.7 以降にしかないので使えないのかもしれない。その場合は「世界標準時と地方時で同じ年月日時分秒になる時刻の間の時間」ではなく、「ある時刻における世界標準時と地方時の年月日時分秒の差」を求めるようにすればよい。実際、utc_offset の実装では、(struct tm の tm_gmtoff が使えない場合には) そうやって求めている。

さて、そうやって正しい時差が求められたとしても、次に sprintf( "%+03d:%02d", tz / 3600, tz % 3600 / 60 ) というところも問題がある。まぁ、時差が時間単位であるかあるいは(日本を含む)東半球であれば問題ないのだが、西半球で分単位の時差があると、/ は負の∞への丸めであって 0への丸めではないので、負の方向にずれる。

% zdump -v /usr/share/zoneinfo/Canada/Newfoundland|grep 2004
/usr/share/zoneinfo/Canada/Newfoundland  Sun Apr  4 03:30:59 2004 UTC = Sun Apr  4 00:00:59 2004 NST isdst=0 gmtoff=-12600
/usr/share/zoneinfo/Canada/Newfoundland  Sun Apr  4 03:31:00 2004 UTC = Sun Apr  4 01:01:00 2004 NDT isdst=1 gmtoff=-9000
/usr/share/zoneinfo/Canada/Newfoundland  Sun Oct 31 02:30:59 2004 UTC = Sun Oct 31 00:00:59 2004 NDT isdst=1 gmtoff=-9000
/usr/share/zoneinfo/Canada/Newfoundland  Sun Oct 31 02:31:00 2004 UTC = Sat Oct 30 23:01:00 2004 NST isdst=0 gmtoff=-12600
% TZ=Canada/Newfoundland ruby -e '
def zone(t)
  g = t.dup.gmtime
  l = Time::local( g.year, g.month, g.day, g.hour, g.min, g.sec )
  tz = (g.to_i - l.to_i)
  p tz                                              
  sprintf( "%+03d:%02d", tz / 3600, tz % 3600 / 60 )
end                          
p zone(Time.gm(2004, 6, 16))'
-9000
"-03:30"

-9000 というのは zdump の結果と正しく一致しているのだが、これを時分表示にすると -02:30 であって、悲しいかな -03:30 ではないのである。

#2

レシピブックにはこのへんのことは書いてないのだろうか、と思いついて (買ってからぜんぜん開いていない) レシピブックの 7章を眺めてみるとない模様。

ただ、p.306 に typo 発見。最後から 2行目に「data ライブラリ」とあるが、これは「date ライブラリ」であろう。

正誤表には... 載ってないか。

2004/06/17

#1

西半球で分単位の時差があるというだけでなく、その分単位の条件が30分でない場合には、 / だけでなく % でも問題が生じるはずである。

でも、現在の時差をざっと探したところそういう例が見つからなかったので、そのことには触れなかった。

でも、過去も調べてみることにすると...

% ruby -rtzfile -e 'TZFile.each {|name, tz|
  next if /\A(right|posix)/ =~ name
  tz.each_closed_range {|t1, tt, t2|
    next if t2.year < 1970
    p [t1,t2] if tt.gmtoff % 1800 != 0 && tt.gmtoff < 0
  }
}
'
[Thu May 26 00:00:00 GYT 1966 (-113688900+0 -03:45 America/Guyana), Thu Jul 31 00:45:00 GYT 1975 (176010300+0 -03:00 America/Guyana)]
[Fri Feb 28 23:58:38 LRT 1919 (-1604359012+0 -00:44:30 Africa/Monrovia), Mon May 01 00:44:30 GMT 1972 (73529070+0 +00:00 Africa/Monrovia)]

うぅむ。いちおう存在するか。まぁ、1970年以前にはけっこう存在するようではあるのだが。

% zdump -v America/Guyana|grep 197 
America/Guyana  Thu Jul 31 03:44:59 1975 UTC = Wed Jul 30 23:59:59 1975 GYT isdst=0 gmtoff=-13500
America/Guyana  Thu Jul 31 03:45:00 1975 UTC = Thu Jul 31 00:45:00 1975 GYT isdst=0 gmtoff=-10800
% TZ=America/Guyana ruby -rtime -e '
def zone(t)
  g = t.dup.gmtime
  l = Time::local( g.year, g.month, g.day, g.hour, g.min, g.sec )
  tz = (g.to_i - l.to_i)
  p tz
  sprintf( "%+03d:%02d", tz / 3600, tz % 3600 / 60 )
end
t = Time.gm(1971, 6, 16)
p zone(t)
p t.localtime.xmlschema
'
-13500
"-04:15"
"1971-06-15T20:15:00-03:45"

やはり、-03:45 になるべきところが -04:15 になっている。まぁ、Time#xmlschema なら -03:45 になるのであるが。