YOS G-specの適当なブログ
ゲームやネットが大好きな人のブログ。毎日更新を目指してました。
2018年01月24日 (水) 00:51 | 編集
HSPでハッシュテーブルを作ることとのその2。
まず、ハッシュ値の衝突回避の対策について実装。

* 衝突したら手前に手前にと空いている配列要素に探して入れる。
* ハッシュ関数をに微妙に線形合同法を混ぜてみる。
* ハッシュテーブルの空席率が2割以下になったらハッシュの拡張(サイズを2倍に)を行うように設定。

今回特筆する仕組みとしては、登録した順序を保証するべく、キーと値を普通に配列に保存するようにした。ハッシュテーブルには何を登録するかというとキーと値を引き出すための添字のみ格納する。そのため、ハッシュ拡張時でもキーと値は触れず、添字の配列のみ再ハッシュすれば良いようになった。

多分もうそろそろ以前作ったDictionaryに統合しても良い頃合いだと思うので、次はそれを進める。

ソースコードは追記にすべて載せます。
≫追記を読む...
2018年01月20日 (土) 23:49 | 編集
以前HSPで連想配列モジュールの実装を行った。
ただし、それは不完全な方法で線形探索を行うため、データ数が増えるほど時間がかかってしまう。
そこで、連想配列でよく使用されるアルゴリズムのハッシュテーブルを調べてみたら、
以外に簡単に実装できそうなことが判明したので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月14日 (日) 18:27 | 編集
PS4買いました。

ソフトは同時購入でロックマン コレクション2と太鼓の達人を購入しています。
DLでもMighty No.9とケロブラスターを購入。
MHW、ロックマン11購入予定。
とりあえず、ゲームソフトの触りだけの感想でも。

以下、追記より。
≫追記を読む...
2018年01月01日 (月) 00:00 | 編集
新年あけましておめでとうございます。
今年もよろしくお願いいたします。

とくにいうこともありませんのでこの辺で。
MHWのためにPS4買おうかどうしようか。
Template by 【投資信託のことなら】投信Web /

Powered by .