2018年01月24日 (水) 00:51 | 編集
HSPでハッシュテーブルを作ることとのその2。
まず、ハッシュ値の衝突回避の対策について実装。
* 衝突したら手前に手前にと空いている配列要素に探して入れる。
* ハッシュ関数をに微妙に線形合同法を混ぜてみる。
* ハッシュテーブルの空席率が2割以下になったらハッシュの拡張(サイズを2倍に)を行うように設定。
今回特筆する仕組みとしては、登録した順序を保証するべく、キーと値を普通に配列に保存するようにした。ハッシュテーブルには何を登録するかというとキーと値を引き出すための添字のみ格納する。そのため、ハッシュ拡張時でもキーと値は触れず、添字の配列のみ再ハッシュすれば良いようになった。
多分もうそろそろ以前作ったDictionaryに統合しても良い頃合いだと思うので、次はそれを進める。
ソースコードは追記にすべて載せます。
まず、ハッシュ値の衝突回避の対策について実装。
* 衝突したら手前に手前にと空いている配列要素に探して入れる。
* ハッシュ関数をに微妙に線形合同法を混ぜてみる。
* ハッシュテーブルの空席率が2割以下になったらハッシュの拡張(サイズを2倍に)を行うように設定。
今回特筆する仕組みとしては、登録した順序を保証するべく、キーと値を普通に配列に保存するようにした。ハッシュテーブルには何を登録するかというとキーと値を引き出すための添字のみ格納する。そのため、ハッシュ拡張時でもキーと値は触れず、添字の配列のみ再ハッシュすれば良いようになった。
多分もうそろそろ以前作ったDictionaryに統合しても良い頃合いだと思うので、次はそれを進める。
ソースコードは追記にすべて載せます。
2018年01月20日 (土) 23:49 | 編集
以前HSPで連想配列モジュールの実装を行った。
ただし、それは不完全な方法で線形探索を行うため、データ数が増えるほど時間がかかってしまう。
そこで、連想配列でよく使用されるアルゴリズムのハッシュテーブルを調べてみたら、
以外に簡単に実装できそうなことが判明したのでHSPでかなり簡単な実装を行ってみた。
ちなみに現状ではハッシュの衝突やキー同一性までのチェックは行えていないけど、これば追々実装する。
ともかく、この時点でも最低限の連想配列としての機能を果たせるということは知ることができた。
なお、ハッシュ関数の仕様としてはwpeekした値に文字の位置をかけただけの簡単なものとしている。
ただし、それは不完全な方法で線形探索を行うため、データ数が増えるほど時間がかかってしまう。
そこで、連想配列でよく使用されるアルゴリズムのハッシュテーブルを調べてみたら、
以外に簡単に実装できそうなことが判明したのでHSPでかなり簡単な実装を行ってみた。
ちなみに現状ではハッシュの衝突やキー同一性までのチェックは行えていないけど、これば追々実装する。
ともかく、この時点でも最低限の連想配列としての機能を果たせるということは知ることができた。
なお、ハッシュ関数の仕様としてはwpeekした値に文字の位置をかけただけの簡単なものとしている。
hashMax=100
sdim keys,,hashMax
dim items,hashMax
keys(hash("一二三"))="一二三"
keys(hash("二三一"))="二三一"
keys(hash("三二一"))="三二一"
items(hash("一二三"))=100
items(hash("二三一"))=500
items(hash("三二一"))=1000
mes "一二三"
mes hash("一二三")
mes items(hash("一二三"))
mes "二三一"
mes hash("二三一")
mes items(hash("二三一"))
mes "三二一"
mes hash("三二一")
mes items(hash("三二一"))
mes "ハッシュ衝突の例"
mes "abcd"
mes hash("abcd")
mes items(hash("abcd"))
stop
#defcfunc hash str _h
hstr=_h
hmax=strlen(hstr)
href=0
repeat hmax,1
href+=wpeek(hstr,cnt)*powf(cnt,2)
loop
return href\hashMax
2018年01月01日 (月) 00:00 | 編集
新年あけましておめでとうございます。
今年もよろしくお願いいたします。
とくにいうこともありませんのでこの辺で。
MHWのためにPS4買おうかどうしようか。
今年もよろしくお願いいたします。
とくにいうこともありませんのでこの辺で。
MHWのためにPS4買おうかどうしようか。
