一括表示

　先日から，それほど多くない値の順位づけの必要があって，ソートのアルゴ
リズムなどを『定本 C プログラマのためのアルゴリズムとデータ構造』 から
拾い読みしていました。ですが，どうもぴったりくるものがなかったので何と
も情けないコードになってしまい，もっとよい方法がないか悩み中です。

　今回扱ったデータの数は，わずか 6個。こんなわずかな個数でも，そういう
作業が不得意な人間にとって（わたし個人のことなのか人間一般のことなのか
は一応置いといて…）それなりに時間がかかります。

　アルゴリズムと言えるかどうかわからないほど単純な方法ですが，先頭から
順番にひとつの値を基準にして自分自身を含む 6個の値と比較して，自分より
大きな値がいくつあるか数えるということを 6回繰り返すというもの。

    ; ---- 順位づけ ---- 値はqを先頭アドレスとするバッファにある
    i0~,
 :j j-, k-,
    i++, a=q..i,
    (6){ (a<q..k)?j++, k++, }
    &?("%d",j+1)
    (i<5)?{ #21 >j }

　ソートなどするとデータを入れ替えなければならないのですが，この方法だ
と同じ値が存在する場合は同じ順位のものが複数あって続く順位が飛ぶという
所期の動作になるので，それほど悪くもないと思ったりもするのですが，なに
しろデータの量に比例した計算量，同じ比較を繰り返すというあきれるほどの
愚かさに閉口しています。

　なんかいい方法はないものかな。

私もいろいろと考えてみたのですが。
えと、要件としては、値を並べ替えてはいけないのですよね。
であれば、計算量は多分、O(n^2)にならざるを得ないような気がします。
並べ替えてしまってもよいのであれば、何番目までは並べ替え済みだから、
そこまでの比較は省略、という方法が使えるので計算量を削減が可能なんで
しょうけどね。
計算量が同一のアルゴリズムの中では、提示されたものが一番わかりやすい
のではないかと思います。というか、私が思いついたその他の方法は２つほ
どあるのですが、いずれも、計算量は同じになってしまうようだからです。
もしかしたら、むしろ増えてしまうかもしれない。

ま、６個ぐらいのデータだったらいいのですが、これが仮に８０００個のデ
ータを順位付けしなければならない、ということになれば、並べ替えて順位
づけして並べ戻す、ということを考えたほうがいいかもしれません。
 

> えと、要件としては、値を並べ替えてはいけないのですよね。
> であれば、計算量は多分、O(n^2)にならざるを得ないような気がします。

　挿入ソートと同じ計算量ということですね。まぁ，対象の数が極端に限られ
ているので，単純なアルゴリズムでも十分ということで。

> ま、６個ぐらいのデータだったらいいのですが、これが仮に８０００個のデ
> ータを順位付けしなければならない、ということになれば、並べ替えて順位
> づけして並べ戻す、ということを考えたほうがいいかもしれません。

　これをやろうとすると，データの函の他に，並べ戻す位置のアドレスを示す
函と並べ替えて付与する順位を示す函が必要ということになりますよね。テス
トの点数で言えば，順位と名前が必要なように。


　今回，これの関連で初めて JavaScript を書きました。
文字コードを返す内部関数がなかなか見つけられなくて難儀しましたが，配列
や条件分岐などがきちんと使えるのはずいぶん楽ですよね。しかし肝腎の順位
付けはまだ入れていません。これだけで息切れしてしまったので。

function Calc() {
    mondat = document.hpara.family.value;
    famdata = mondat.split(",");
    apti = famdata[2];
    napti = new Array();
    for (i = 0; i < 6; i++) {
        napti[i] = 69 - apti.charCodeAt(i);
        if (napti[i] < 0 || napti[i] > 5)
            napti[i] = 0;
    }
    document.hpara.mondata.value = mondat;
    with (document.hpara) {
        al.value = apti.charAt(0);
        ap.value = apti.charAt(1);
        aw.value = apti.charAt(2);
        ah.value = apti.charAt(3);
        ad.value = apti.charAt(4);
        as.value = apti.charAt(5);
        hl.value = Math.round(sl.value * napti[0] * 0.5);
        hp.value = Math.round(sp.value * napti[1] * 0.5);
        hw.value = Math.round(sw.value * napti[2] * 0.5);
        hh.value = Math.round(sh.value * napti[3] * 0.5);
        hd.value = Math.round(sd.value * napti[4] * 0.5);
        hs.value = Math.round(ss.value * napti[5] * 0.5);
    }
}

　なんだ，改めて眺めると，サブルーチンもないや。(笑)
　MF2 resources を久々に更新しました。

> 　これをやろうとすると，データの函の他に，並べ戻す位置のアドレスを示す
> 函と並べ替えて付与する順位を示す函が必要ということになりますよね。テス
> トの点数で言えば，順位と名前が必要なように。

そです。
かつて、FGALTSで、これに似たことを教えてもらった記憶があります。確か、
数千行のデータを行頭の値で順位付けするというようなものだったかな。

・まず、awkで行頭数桁分に１カラム増やし、そこに現在が何行目か
　というデータを入れる。
・それを２つめのカラム（元データの行頭の値）でソート。
・その結果をさらにawkにかけて、現在が何行目かというのを行末に
　付加。
・これを今度は行頭の値でソートして、元データの順に並べ戻し。
・最後に、awkまたはsedで行頭の新設カラムを削除。
・結果は、元データの順位が行末に付加されている形。

ただ、この方法のままだと、同じ値の時に同じ順位になりませんね。
これを改善するのなら、３番目の手順のところでちょっと工夫が必要。
 

> ただ、この方法のままだと、同じ値の時に同じ順位になりませんね。
> これを改善するのなら、３番目の手順のところでちょっと工夫が必要。

　どんな工夫をすればよいのか結局想像つきませんでしたが，awk でアレコレ
すればできそうなんでしょうかね。 自分でやるならまた sortf のお世話にな
りそうです。

　その後も，やはり適当なアルゴリズムは思い付かなかったので，マクロでの
手法をそのまま JavaScript にしました。

    for (i = 0; i < 6; i++) {
        j = 1;
        crnt = o1[i];
        for (k = 0; k < 6; k++) {
            if (crnt < o1[k]) j++;
        }
        o2[i] = j;
    }

　順位づけしたら格段にスピードが落ちました。(笑)

> 　どんな工夫をすればよいのか結局想像つきませんでしたが，awk でアレコレ

いや、そんな大層なことではなくて、単純にNR変数を使って行数をカウント
するのではなく、順位用に別途変数を設ける、というだけのことだったりし
ます。


ところで、今気がついたのですが、この個別発言表示というか記事閲覧での
表示、なんか変。どこが、というと、一番上の方の発言ヘッダの部分。

> − 野ざらし言 −
> [2335] Re^4: 順位づけのアルゴリズム - めざら 2007/10/27(Sat) 20:31
>  <mezala@nifty.com> http://homepage3.nifty.com/mezala/index.html 

「2335」ってなんですか？
って言うか、いろいろとみてみたら、どうも、ツリー表示にした時の一つ下
のツリーのルート発言の発言番号のようなんですが。なんかスクリプトを変
に書き換えてしまっていませんか？
 

> 　あう，確かに変ですね。どれを個別表示しても，次のツリーのルート番号に
> なっているようです。どこを弄ったわけでもないので…ヘッダ部分はしばらく
> 前まで表になっていたのを直してますが，あくまでも表示周りなので以前から
> そうだったはず。

発言番号のところで表示している変数って$v_no（だったかな？）ですよね。
これが$noを表示するようになっていると、このような表示がでる可能性が
ありそうです。
どっかで誤って代入とかしていませんか？
 

> 場合によって$_が使われているところもありますが。$v_noは見つかりません。

あ〜、ごめんなさい。
他の項目が全て$v_がついていたので、発言番号もそうなっているとばかり思
い込んでいました。本当のオリジナルでは、そもそも、こんな変数は使って
いないのですね。
ではどうするかというと、他の項目に合わせ、発言番号も$v_noという変数に
代入してそれを表示するか、あるいは、$noのかわりに$in{'no'}を表示する
ようにすればとりあえずは解決すると思います。
とにかく、現在の記事番号表示タイミングで$noという変数を使うかぎり、次
のツリーのルート発言が表示されてしまうというのは避けられないと思いま
す。タイミングはかえられないと思いますので、ならば変数の方を変えるよ
り仕方がないでしょう。
 

> 教えていただいたように別の変数を用意して表示するように直そうと思います。

ついでというか。
できれば、#nnnnでその番号の発言に飛んでくれるルーチンを仕込んでもらえ
るととってもありがたいのですが、ちょっと無理ですかね。基本的にここは
オリジナルから表示しか変えない方針だったかと思うけど、これを導入して
しまうと表示以外の部分が変わってしまいますからねぇ。

そういえば、ＯＦＦの幹事をやってもらえれば掲示板スクリプトの改造を請
け負う、と言ったことがあったような。夏のＯＦＦの幹事をやってもらった
わけだから、可能な範囲で改造のお手伝いはしますよ。もちろん、いきなり
メールで現在の使用中のスクリプトを送りつけていただいてもいいけど。
 

> 　それではお言葉に甘えて，現 CGI を見てもらえたらと思います。 遅くとも
> 今週中にメールさせていただきますので，よろしくお願いします。

は〜い、お待ちしております。
受託内容としては、

・記事閲覧画面に発言番号表示追加
・#nnnnで該当記事への自動リンク

だけでよろしいですかね。
もっとも、発言番号自動リンクを過去ログ対応にするために、今ならもれな
く永続的ＵＲＬ対応がついてきますけど、それは構いませんよね。もちろん、
永続的ＵＲＬ対応は絶対いやだとおっしゃるのであれば、現在ログのみ対応
という形になります。
その他、こんなことはできないかというのがあれば今のうちにおっしゃって
ください。うちで採用している改造であれば組み込めますし、konnoさんのと
ころで採用しているアレ、なんていうのであればコードを取り寄せます。そ
れ以外の内容であっても、言うだけならタダです。

一応、納品物としては、改造済みのコードのほかに、現在使用中のコードと
の差分も添付します。これがあれば、将来のバージョンアップの際にも多少
なりとも参考にできるかと。別に、差分ファイルなんて簡単に作れるのだか
ら、めざらさんご自身で作っていただいても結構なんですが、一応、形だけ
でもサービス精神を発揮しておかなくては。
 

> 考え付かないものですから，便利そうなのをあらかた付けていただければ嬉し

便利そうなもの、ねぇ。
例えば、ツリー表示の変造なんか、私には便利なんですけど、ちょっとここ
に導入するには躊躇してしまうわけです。なんとなくそぐわないような気が
するわけですよ。スレッド表示の新設も同じく。
うちで導入していて無害そうなものといったら、ＲＳＳ配布ぐらいですか。
発言のタイムスタンプ表示は過去ログの書き換えが必要だし、個別ＵＡ対応
なんていうのも不要でしょうし。
HTTPやHTMLのヘッダ回りはちょっと眺めてみますかねぇ。
あとは、可能であれば、スパム除けのルーチンをちょこっと入れてみるくら
い、でしょうか。
 

> 　それではお言葉に甘えて，現 CGI を見てもらえたらと思います。 遅くとも
> 今週中にメールさせていただきますので，よろしくお願いします。

受け取りました。
改造は現在快調に進行中！

今までに組み込んだのは以下の通り。

・ＨＴＴＰヘッダでログ最終更新時明示
・ＨＴＭＬヘッダでfavicon設定
・記事閲覧画面での発言番号表示
・永続的ＵＲＬ対応
・#nnnでの発言番号自動リンク

ここまでは、新規開発というわけではなく、うちのところですでに動いてい
る既存のルーチンをどう組み合わせるかというだけですから、そんなに手間
のかかるものでもありません。

以下、掲示板オーナーに判断を仰ぎたい部分が２点。
１点目は、ＲＳＳ表示を組み込むかどうしようか、ということ。
うちの板塀では、最近はＲＳＳにＣＳＳまでくっつけて、FireFoxなんかで表
示した場合にはそれなりの見栄えも確保できるようになりましたが、必要性
はやはり掲示板オーナーに判断してもらいたいかな、と。

２点目は、過去ログ対応の部分。
小項目の１点目として、#651で私が触れている部分、ええっと、過去ログ送
りになっているので

/mezala/noz/wforum.cgi?mode=allread&no=648&pastlog=0001&act=past

を参照していただきたいのですが、ツリー一括表示の際のＩＤ指定で、オリ
ジナルでは半角「N」が付いていないのを、めざらさんご自身が、現在ログ表
示時だけつけるように改造した部分。ここを、過去ログと現在ログの統一を
図ろうとしているのですが、「N」付で統一するべきか、それとも「N」なし
で統一するべきか。統一さえされていればどちらでもいいのですが。なるべ
くオリジナルに近い方が、ということであれば「N」なしにしますけど、めざ
らさん自身が改造されたという事は何か目的があって改造されたのだろうし、
でも、その目的がさっぱりわからないというのもあって。例えば、id指定時
は数字のみではダメ、みたいなことってあるんでしょうか。
小項目の２点目は、同じツリーの中で議論されている、「▼」の件。
こちらもどうしましょうか。

ということで、以上、よろしくお願いします。
 

ということで、ＲＳＳなしで「N」つきの過去ログ対応ルーチンを組み込んで
みました。
が、まだ、組み込んだだけ。
細かい調整はおろか、デバッグすら済んでいない。
試験実行してみたら、見事にperlがエラーを吐いてくれた。
とりあえず、バグ取りします。
その後に、過去ログの▼マーク付近のタグとかをできるだけ文法にあった形
に調整する作業を行って、今回のお仕事は終了となる予定。が、その細かい
調整が思いのほか難航するかも。だって、どんなタグを吐き出すか、私にも
予想がつかない状況なんだから。

今夜はもう寝ます。
明日、というかもう今日か、通常の日勤なんで、帰宅してから続きにチャレ
ンジします。
 

えぇっと、多分うまく行っていると思います。
うちの板塀のログを使ったサンプルを以下のところに置いておきます。

hpcgi3.nifty.com/~toshiki/noz/wforum.cgi

一応、#nnnで過去ログ0001にはきちんとジャンプする事を確認できたけど、
過去ログ0002以降にもきちんとジャンプするかは不明。なにせ、うちの板塀
ですら実験できていないのだから。一応、それなりにロジックには自信があ
るのだけど、もし本番環境でうまく行かなかったらまたすぐ手直しする、と
いう事で許してください。

一応、チェックしてもらいたい点。

・favicon設定
・現行ログの記事閲覧画面での発言番号表示
・#nnnでの発言番号自動リンク（過去ログ対応）
・過去ログでの個別発言へのジャンプ（「N」つき対応）
・過去ログでの「▼」

そうですねぇ、過去ログのところに限って言えば、
 /~toshiki/noz/wforum.cgi?mode=allread&no=986
あたりのところでいろいろと実験してもらえると嬉しいかも。

ところで、過去ログをAnother HTML-lintでチェックしていて気が付いたこと
があります。
過去ログの同一のツリーでは同一の階層のコメントの時、「Re」を使ってい
ると同一のタイトルになることがあります。ところが、リンク先はそれぞれ
個別の発言番号を指すわけです。すなわち、同一のアンカーに対して別々の
リンク先を指しているといって、Another HTML-lintは文句を言ってくるわけ
です。まぁ、確かに、これは推奨されることではありませんけどね。
これを解決するためには、うちの板塀のように、リンクのアンカーにそれぞ
れの発言番号を含めてしまう、という手があります。こうすれば、発言番号
は一意に定まりますから、決して同一のアンカーは発生しないわけです。
あ、ちなみに、私が自分のところをそうしているのは決して文法的な正しさ
を狙ったわけではありません。単に発言番号が行頭に近い方が私のセンスに
あっているという事であのようにしているだけで、副作用として文法違反が
少なくなってしまっているわけです。

ということで、この点についてはどうしましょう。
御依頼があれば私の方で直しても良いですが、単に表示にかかわるだけの部
分なので、あとでめざらさんご自身で納得のゆくように直されるほうがいい
ような気もしますし。

今後の予定。
数日間寝かせて熟成させて、その間に特にバグ等に気がつかなければ、今週
の水曜日か木曜日にも発送したいと思います。
 

> まって，「お客様がおかけになった電話番号は、現在使われておりません。」。

いやぁ、絶対にコピペでＵＲＬを入力すると思っておりましたもので。
まさか、手入力されるとは予想しておりませんでした。

> 　テスト板で過去ログ番号を記入させてもらって，ジャンプできることを確認
> させていただきました。いや，ほんと素晴らしいです。＼(^_^)／

そう言っていただけるとありがたいです。

> 丸投げのようで申し訳ないのですが，番号を移動してリンクに含めてしまうと
> いう改造もお願いしてよろしいでしょうか。

全然構いません。
早速そのようにしておきました。
同じＵＲＬですので、もう一度ご確認下さい。
表示だけですので、見ておかしくなければＯＫという事で。

もしまだなにか御要望があれば、今のうちにどしどしどうぞ。仕様の追加が
あっても、納期が延びるだけで新たな費用負担は発生しませんから。
一応、私が直接受託しているのはめざらさんからだけですが、その他の方で
も、うまくめざらさんを丸め込めれば御要望はお受けできると思いますので、
やっぱり今のうちに、めざらさんにＧＯ！
 

とりあえず作ってみました。
▼押下時の一括表示の方は特に何ということもないと思います。
記事閲覧時のツリーの方は、うちの板塀でも発言番号を尻尾に回したままに
なっているくらいで、どうしようかと思ったのですが、ま、こんな感じかな、
ということで。番号だけ強調、という方がいいですかね。

ちなみに、ゼロパディング時の数値解析はスクリプトでは行っていないはず。
perlの機能でやっているので、今後、例えばperlがバージョンアップするこ
とによって、うまく機能しなくなる可能性はありますが、いくらなんでもこ
んな基本的なところに変更は加わらないでしょう。
存在しない発言番号へのジャンプ時の挙動は、この機能を発案されたあじゃ
さんのオリジナルバージョンで私が最も不満に思っていた部分ですが、その
割には大したことがないので、改善してこの程度か、と笑われてしまいそう
です。ちなみに、あじゃさんバージョンでは、全く何にも表示されない真っ
白な画面になってしまいます。分母がほぼゼロですから、分子がわずかでも、
改善率としたら無限大に近いのでしょうけど。
もし、戻るボタンだのモロモロなリンクの表示が必要などという事があれば、
今のうちにおっしゃって下さい。