ここしばらく、悩んでいる問題がある。
Fortran には部分配列という機能があって、配列の一部分を表す配列を作れる。この一部分というのは、配列の端を切り落としたものであったり、n個おきに要素を取り出したものであったりする
そういう配列がふたつあったとき、ふたつの配列が同じ要素を指すことがあるかどうかを効率よく判断したい。これは可能だろうか?
ここで、配列のすべての要素についてアドレスを求めて共通なものがあるかどうかを調べれば判断できるのは自明なので、そうではなく、次元数とかそのあたりで計算量が抑えられるアルゴリズムがあるか、というのが問題である。
さて、そういう配列でも、インデックスの各整数に整数の係数を乗じてベースアドレスに加えることによって要素のアドレスを求められるのではないかと思う。
つまり、element_addr = a1 x1 + a2 x2 + ... + an xn + base_addr である。とりあえず配列インデックスは 0 origin で、各次元の要素数は Xi、つまり 0 <= xi < Xi としよう。
そうすると、問題は
a1 x1 + a2 x2 + ... + an xn + a_base_addr = b1 y1 + b2 y2 + ... + bm ym + b_base_addr 0 <= xi < Xi (0 <= i < n) 0 <= yi < Yi (0 <= i < m)
という式を満たす整数解 x1, ... xn, y1, ... ym が存在するかどうか、と形式化できる。
形式化できたのはいいのだが、先人の知恵を調べてみても、どうもちょうどいいやりかたが見つからない。
今日、ちょうど CodeFestWeek で、こじまさんに会ったので尋ねてみたところ、しばらく考えてくれたのだが、やはり簡単にはいかなさそうとのことであった。
無理なのかなぁ。
詳説正規表現第3版が出るのか。
明日は FSIJ 月例会である。
今月は 「ビット演算による最適化の妙味とJITアセンブラ」 で、最近興味のあることと関係ありそう。
Ruby 1.8.7 branch ができたので、chkbuild も対応して増やしておく。
ふと「穴掘り」「趣味」と検索したところ、 Seymour Cray がそういう趣味を持っていたらしい。
cvs.m17n.org を etch にする準備として、(失敗したときのために) kernel を指定してブートする方法とかをいろいろと試して確認する。
なんとかわかったので、明日 upgrade するか。
なんとかだいたい upgrade できたようだ。
OS と anonymous cvs と cvs commit は動く。
cvs-info と svn は動いていない感じだが、後で対処しよう。
svn (を chroot して動かす仕掛け) がうまく動いかなかったのは etch の chrootuid が腐っていたためであった。
getopt を使っていて、コマンドのオプションを chrootuid 自身のオプションとみなしてしまう。
% sudo /usr/bin/chrootuid / root /bin/ls -l /usr/bin/chrootuid: invalid option -- l usage: /usr/bin/chrootuid path user command
sarge の chrootuid は getopt を使っていなかった。
lenny の chrootuid 1.3-5 は getopt を使わないように直っていたので、それをビルドして使うことにする。
cvs-info が動いていないのは気のせいだった、か? ちょっと様子を見てみよう。
[latest]