HSPTV!掲示板

二分検索で検索する文字列が、自作の辞書データに含まれているかを検索するプログラムを
作ったのですが、とても二分検索とは思えないほど処理が遅いのです。
作った辞書データは914KBで81482行なのですが、
辞書データを簡略化して12KBの1995行にしたら、とても軽快に動作しました。

もしかしたらnotegetが足を引っ張っているのではないかと思うのですが、
命令がどのように動いているかを確かめるという事は出来ないのでしょうか。

title,dialog,logmesあたりで変数の中身を追いかけたり
notegetの実行回数を数えてみたりするなど、
分かりきった方法しか浮かんでこないのがアレですが
一度スクリプトを拝見したいところです。

>命令がどのように動いているかを確かめるという事は出来ないのでしょうか。
一回、HSP3SDKを覗いてみれば分かると思います...

二分探索ということは配列で実装していませんか？
二分探索法を適用するには配列をソート済みに保つ必要がありますから、
バイナリツリーやハッシュテーブルなど、
データ構造そのものを見直してみてはどうでしょうか。

>arctanさん
いえ、配列変数ではなく、外部ファイル(テキストデータ)をnoteloadで読み込んで、
行数を頼りにnotegetで読み込んでいく形を取っています。

ファイルが複数なので、アップローダーに上げました。パスはbinary。
rank.hspを実行してみてください。またrank.hspの23行目(辞書データ)も変えてみてください。
http://gonzo.dip.jp/~gonzo/cgi-bin/uploader2/upload.cgi?mode=dl&file=4396

こちらを参照してください。
http://fs-cgi-basic01.freespace.jp/~hsp/ver3/hsp3.cgi?print+200601/06020038.txt

同じ場所の同じ文字列を何度も検知しているような気がします。
基準となる文字を先頭として、右向き・下向きに向かってだけ検索するようにすれば
それだけで検索量が半分くらいになるのではないでしょうか？

文字列配列に入れてから使う方がいいよ。

sdim buf
notesel buf
noteload dic_filename
sdim dic
repeat notemax
	noteget dic(cnt), cnt
loop
sdim buf

二分検索とは別の話だけど・・・
COMのScripting.Dictionaryを使えば連想配列を利用できますよ

newcom dic, "Scripting.Dictionary"
if( varuse(dic) == 0 ) {  dialog "Scripting.Dictionary の初期化に失敗"   :  end  }
sdim buf
notesel buf
noteload "辞書.txt"  // key=value 形式のファイル
repeat notemax
	noteget s, cnt
	i = instr(s, , "=")
	if( i == -1 ) {  continue  }
	key = strmid(s, 0, i)
	val = strmid(s, i+1, 0x7FFFFFFF)
	dic->"Add" key, val
loop
noteunsel
sdim buf

//-------------------------------------------------------------

key = "hoge"
if( dic("Exists", key) ) {
	mes "「" + key + "」は存在します"
	mes "内容は「" + dic("Item", key) + "」"
}
else {
	mes "「" + key + "」は登録されてない"
}

辞書.txt

hoge=ほげ
fuga=ふが
aaaaa=あああああ

辞書に存在するかだけ判ればいいのなら、
valueには適当なダミーデータ（例えば整数値など）を入れて利用。

>Kpanさん

URL先参考になります。
やはりnotegetは遅くなるようですね。

>Meganeさん
>基準となる文字を先頭として、右向き・下向きに向かってだけ検索するようにすれば
>それだけで検索量が半分くらいになるのではないでしょうか？

二分探索だと下向きではなく上下に動くと思いますが。
下向きだけに検索するにしても、例えば4文字の「し」だけで1197行あるので、
「じーんず」を検索するのに時間が掛かる事になります。

notegetが遅いという話だったのか・・・よく読んでなかった。orz

wsrt.hsp

#const MOJI_MAX 9
#const MOJI_MIN 2

*dictionaly_load
	newcom objDic, "Scripting.Dictionary"
	if( varuse(objDic) == 0 ) {  dialog "Scripting.Dictionary の初期化に失敗"   :  end  }
	sdim buf
	notesel buf
	noteload dic_filename
	n = notemax
	i = 0
	repeat n
		getstr s, buf, i, 0
		i += strsize
		objDic("Item", s) = 1
		if( (cnt \ 1000) == 0 ) {  title ""+cnt  :  await 0  }
	loop
	sdim buf
	return

*word_search
	if( objDic("Exists", search_word) ) {
		word_result = 1
	}
	else {
		word_result = 0
	}
	return

title 命令 も 非常に重くなる原因・・というのはわかってますよね＾＾；

a氏のスクリプトを下のソースで動かしたらエラーが出ます。
使った事が無い命令があるのでデバッグの仕方も分からない…

#Error 37 in line 22 (wsrt.hsp)
-->変数型の変換に失敗しました

>title 命令
重くなる事は分かっていますが、今はデバッグ段階なので。完成したら外しますよ。
どうしても処理に時間が掛かるなら、多少速度を犠牲にしても
進行状況を表示する必要はあるでしょうが。

rank.hsp

goto *init

#include "wsrt.hsp"

*init
	; 辞書データの選択。
	dic_filename="dic_full.txt"
	
	gosub *dictionaly_load
	goto *main_routine
	
*main_routine
	search_word="あい"
	gosub *word_search
	if (word_result==1) {
		print "○: "+search_word
	} else {
		print "×: "+search_word
	}
	stop

自分の環境では、
○: あい
と普通に表示されけど…なんでだろ？
環境はWinXPsp2、HSP3.1です。
Scripting.Dictionaryって、標準じゃ入ってなかったけ？？？？

HSP3.0から3.1にしたら動作しました。すみません。
また、非常に使いやすいスクリプトの提供をして下さいまして、
ありがとうございます。（そのまま使えそうなスクリプトなので解決チェックを入れました）

この期に、COMオブジェクト型変数についても追求してみることにします。