リンク通知のメールの効果。配列を単位行列にするアルゴリズム。 前回は「らんだむCGりんく」のページのリンク数が500程度になったと書いたのだが、さらに調子に乗って集めたら1000リンクを突破した。「リンクしました」というE-mailも適当に出しているのだが、一度だけ「リンクのページが違う」というご指摘をいただいた。リンク先に指定してあるトップページではなく、途中のページをリンクしてしまったのだ。
これは結構重大な問題を含んでいる。トップページではなく途中のページをリンクした原因がよく分らないのだ。該当ページを開いた時点でNetscapeの「ブックマークに追加」のコマンドを実行すると、bookmark.htmファイルの内容が更新される。「らんだむCGりんく」のリンクは、基本的にこれを参照することによって生成している。もちろん、このコマンドを実行するタイミングを誤ったのかもしれない。トップページにあるEnterボタンを押した後でブックマークを追加してしたような場合だ。しかし、この作業はリンクの数が1000になる程繰り返しているので、かなり習慣として身に付いてきている。基本的な所でミスをする可能性も否定しないが、そういう可能性は低いような気がする。
一つの可能性としては、別のページからその途中ページへリンクが既に張ってあることが考えられる。ページによっては、実はトップではないのだが、一見トップページ、という所が結構あるので、誤解したままブックマークに登録してしまったのかもしれない。特にフレームの中身を直接参照してしまうと、なかなか気が付かないことがある。このことに気付いてからは、うかつにブックマークに登録しないように気を付けるようにしているのだが、何しろ私のやることだから、うっかりしたらハイそれまで、である。やはりe-mailで連絡するのが堅い手段で、確認してもらえる点では一利あるから、e-mailはなくても構わないというページでも一応連絡はしておくものである、と、これが得られた教訓。
Web pageのバナーも結構いろいろデザインが工夫されていて面白い。特にCG系のページだと「ドット絵なら任せろ」という感じの人もいて、完成度も高いようだ。現在普及しているバナーのサイズは、日本のCG系ページに限れば、200×40ドットというサイズが標準のようである。これは割と絶妙のサイズで、かなりの情報を突っ込めるのである。人の顔の絵を縦40ドットに収めてしまうというのは、まさに職人芸としか言いようがない。
88×31というサイズもある。これはバナーではなくボタンと呼ばれることもあるが、このサイズだと200×40のサイズのバナーに比べると、約1/3程度の面積になり、データ量をコンパクトに出来る点では有利かもしれないが、表現できる情報量としてはやや厳しい感じがする。バナーを見るのは人間だから、人間が識別することを前提とした情報を用意しなければならない。そこで重要なのは、バナーとページとの関連性が一目で分るということである。そのバナーを一瞥した時点で、あっここだ、という連想が出来るようなデザインがいい。となると、これはユーザーインタフェースの問題である。CG系のページの作者の皆さんは、流石にデザインのセンスがあるから、秀逸なデザインも多いのだが、意外なことに、見て何だか分りにくいというのもたまにある。特に、色の使い方がまずくて、書いてある字が読み辛いとか、基本的な所で失敗しているものが気になる。
全然関係ない話だが、バナーのデザインにバナナを使っているのがあるかと思ったのだが、希にはあるみたいだ。バーナーのデザインというのが驚いた。いやすごいページだと思ったのだが、試しに見に行ったら、期待を裏切らない恐ろしい出来で完全に負けたという感じだった。やはりバナーはページを表すようだ。
プログラマーズフォーラムで行うと予言していた“最悪のプログラムコンテスト”は、いろいろな壁があってなかなかスタートできなかったが、とにかく何とか勢いを付けて始めた所だ。予想通り最悪の結果になっているというか、最悪のプログラムがたくさん集まってしまって、どれが最悪か分らないという状況である。ってことは最高の状況なのか。いやともかく、問題は、果たして最悪のプログラムとは何であろうか、という所に尽きる。
プログラムには実行時の性質とソースを眺めたり保守した時の性質を兼ねるという特徴がある。読みにくいプログラムのコンテストというのはUSENETで有名なのがあって、そちらのコンテストはreadabilty(可読性)を評するのだが、価今回プログラマーズフォーラムで行おうとしたのは、むしろ実行時に最悪となるようなものである。アルゴリズムは単純で明快、しかし、実行すると無茶苦茶、というのが理想なのだ。何が理想なんだか。
プレ問題として、a[100][100] というような配列を単位行列にする、という割と古典的に有名な問題を選んだ。これはプログラマーズフォーラムの別会議室、「プログラミング入門」の方で最初に出した例題と同じなのである。考え方としては、list 1のような誰でも思い付く発想がなぜ良くないかという話だ。
| ---- list 1 (単純だがよくない例) ---- |
for (i = 0; i < 100; i++) {
for (j = 0; j < 100; j++) {
if (i == j) {
a[i][j] = 1;
} else {
a[i][j] = 0;
}
}
}
|
list 1は100×100の配列を初期化するために10,000回の比較を行うのだが、この場合は、list 2 のように書くことによって比較を略し、そのかわりにa[i][i]には0を一回入れておいて後で1を入れるという無駄な代入を追加するのが定石である。無駄といっても、100回の代入のコストは、10,000回の比較に比べると無視できる程度なのだ。
| ---- list 2 (比較回数を減らす) ---- |
for (i = 0; i < 100; i++) {
for (j = 0; j < 100; j++) {
a[i][j] = 0;
}
a[i][i] = 1;
}
|
入門会議室でこの例を出したのは、プログラムの性能評価を大雑把に見積りながら書けるようにという期待があったわけだが、さて、最悪のプログラムコンテストとしては話が逆である。list 1の処理を一体どうすれば非効率的に修正できるか、ということになるのだ。結構難しい。
極めて単純な発想として、乱数を使ったアルゴリズムがある。適当に初期化して、たまたま期待通りの結果になったら処理を終了するわけだ。
| ---- list 3 (乱数による初期化) ---- |
do {
i = r(); /* r() は 0〜99の値を戻す乱数 */
j = r();
a[i][j] = (i == j);
} while (check(a)); /* チェックする関数があることを想定している */
|
list 3は、インデックスを乱数で選択して、それに対応する配列要素を期待している値で初期化している。初期化する値を乱数にしたら、さらに効率は悪くなるのだが、現実的には無茶苦茶な差が生じるとはいえ、アルゴリズムの点ではあまり本質的な差ではない。
このプログラムの最も大きな欠点は、有限時間内でこの処理が完了する保証がどこにもないということである。確率的には乱数が十分乱れているという条件がある限り、完了することはまず間違いないはずだが、プログラムが正しいかどうかという点において、やはり有限時間内で終了するという必然性は欲しい。簡単な修正としては、乱数で選択した要素が既に初期化された所を指したら次の要素を初期化する、というような処理を追加することが考えられる。例がlist 3である。gotoが出てくるのがいまいちかもしれないが、checkの関数を呼び出さずに済むようになった所が効率的である。しまった、効率的にしてはいけないのだった。ともあれ、これはこれでランダムに初期化するという作用があって、使い方によっては面白いかもしれない。
| ---- list 3 (乱数による初期化) ---- |
for (;;) {
i1 = i2 = r(); /* r() は 0〜99の値を戻す乱数 */
j1 = j2 = r();
again:
if (a[i1][j1] != (i1 == j1)) {
a[i1][j1] = (i1 == j1);
} else {
j1 = (j1 + 1) % 100;
if (j1 == 0)
i1 = (i1 + 1) % 100;
if (i1 == i2 && j1 == j2)
break; /* 一周した */
goto again;
}
}
|
さて、「らんだむCGりんく」のページは乱数を使っているが、実は乱数を使わなくてもいいのだ。CGIを呼び出している間に他の人がリクエストすれば、単に順番に出すだけでも結果的にはランダムに近くなるからだ。それに、本当にランダムかどうかは、見ただけでは分らない。とはいえ、順に出すというのも結構難しいというのでそうなっているというのが真相である。順に出すには前回の番号は覚えておかなければならないし、そのためのファイルをロックしたり何かで面倒だから、乱数を使って1ページ選択するのがこの場合は案外効率的かもしれない。
※らんだむCGりんくのURLは、http://www.st.rim.or.jp/~phinloda/cgi-bin/randcg.cgi
(フィンローダ ニフティサーブ FPROG SYSOP)
(C) 1998 Phinloda, All rights reserved
無断でこのページへのリンクを貼ることを承諾します。問い合わせは不要です。
内容は予告なく変更することがあります。