--------------------- 第２話 もう一つのバイナリサーチ --------------------------
はじまり、はじまり～。
＜では続きやるよ～～。 「そこがミソ」をおせーて？＞
元気だな。
＜醤油やソースじゃダメなの？＞
ソコの続きかよ！ やっぱ味噌でなきゃダメだね。
＜どーして？＞
昔、日本の各家庭では、独自に工夫して特徴的な味噌を作っていた。
まさに家庭の味、ステータス・ポイントだった訳だね。
＜なるほど。で、コレのポイントは？＞
通常のバイナリサーチでは完全一致のみ抽出するが、命題は最大の近似値だ。
コレが中々厄介で、一つずつ比較するので遅くなりがちだ。都合の悪いことに一度に長い
文字列を読み込んで処理しているので、最悪のケースになる。
＜どうゆうこと？＞
長い文字列の改行を毎回最初から数えている。コレは文字列が長くなると指数関数的に
遅くなる。今回の例では、2000件と5000件では、5000件の方が10倍以上遅い。
2000件でも実用的でないのにコレは致命的だ。バイナリサーチの特徴はデータが増えても
ほとんど検索時間が変わらない。しかし今回は完全一致でない。
＜使えないジャン！＞
普通ならそう思うね。でも良く考えると、2分割する時にちゃんと大小比較はしているんだ。
むしろ完全一致を後でチェックしている。要はコレを外せばいいだけ。返って短くなる。
＜へっ？ なにソレ？ 逆に簡単になっちゃうの？ ホントだ～！ 何のマジック？＞
＜？？ 単に超高速だけじゃなくって、簡単になる？？ 一体ど～なってんの？？＞
＜ったくぅ～。毎回毎回驚かせてくれるわね。＞
そういえば、質問者も驚いていたなぁ。
＜なに何？ソレ初耳よ。ん？！ へっ？ ＞
「空ファイルをメモリー上に作って、tokenで一発書き込み。すごいです。」
＜おやまぁ。スクリプト物語で言う所の仮想ファイルね。＞
＜こんなの、アンタにとっては普通の処理ってワケね。＞
急にタメ口になったね？
＜最初にLiners様って呼んだこと？コレね先輩がそう呼んだほうが良いって言うもんだから＞
ピンポントで律儀だな。
＜もう呼んであげないんだからね。アンタって言うんだからね。＞
すでに、そう呼ばれていて念を押されても説得力ゼロなワケだが・・・
＜２話目ですでに 高速・簡単・驚きのトリプル・アタック？ やるわね。＞
別に攻撃している訳じゃないんだけど。
＜そう言えば、先輩色々話してくれたな～・・アンタまだ武器持っているでしょ！＞
オイオイ！ 確かにスクリプト物語では戦闘的部分もあったけど、ソレは精神的な部分で
スクリプトが武器化するわけじゃ・・・
----------------------------------------------------------------------
提供は： トリプル・アタックの、Linersでした。
----------------------------------------------------------------------
以下(Linersスクリプト)
// もう一つのバイナリサーチ.uws(by Liners) bsrch()として関数化
// 当方のテストではデータが2000件で検索時間は 1.02ミリ秒 速度比 約16万倍速だった。(もうぅ、どんだけ速いんだよ！！)
dim a[10]
fid = fopen(null, F_READ or F_WRITE)
str = replace(vn銘柄辞書, chr(10), "")
while str <> ""; fput(fid, token("<#cr>", str)); wend
resize(a, fget(fid, -1) + 1) // 行と添え字と一致させる為 １増やす。
for i = 1 to fget(fid, -1); a[i] = fget(fid, i, 1); next // 検索フィールドを配列へ
検索文字 = 225
old = gettime()*1000+G_TIME_ZZ
n = bsrch(検索文字, a)
検索時間 = gettime()*1000+G_TIME_ZZ - old // ループで回さないと検出不可
msgbox("検索文字： "+ 検索文字 + " 検索時間： "+ 検索時間 + " ミリ秒<#cr>" + fget(fid, n))
Function bsrch(x, a[]) // bsrch(検索値, 配列[])：返値[マッチ又は近接最大値(添え字)]
dim l = 1, r = length(a)-1
While l < r
m = Int((l + r) / 2)
If a[m] < x Then l = m + 1 Else r = m
Wend
// If a[l] = x Then result = l Else result = -1 //通常の一致した場合
result = l // マッチ又は近接最大値
FEnd
TEXTBLOCK vn銘柄辞書 // 実際には2000行
10,ABT,v0010,ベンチェー水産㈱ ,食料品,ｖ3ホーチミン,Bentre Aqua Prod
140,BPC,v0140,ビムソン・パッキング㈱ ,梱包・包装,ｖ3ホーチミン,Bim Son Packing
220,CYC,v0220,チャンイー・セラミック㈱ ,建材,ｖ3ホーチミン,Chang Yih Cerami
230,DCC,v0230,デスコン工業建設㈱ ,建設,ｖ3ホーチミン,Descon Construct
ENDTEXTBLOCK