FC2ブログ
--.--
--
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

12.08
Mon
Lispのハッシュテーブル使ってて困ったことがあったので書きます。

まずハッシュテーブルとはキーと値の組みを効率的に扱うためのデータ構造で、
リストの配列とかで実装されていることが多いです。

基本的にハッシュテーブルの参照・追加は定数時間でできます。
(後述するようにハッシュコードが頻繁に衝突しなければ)

配列Arrayとそのサイズをnと考えます。大きいほどハッシュ値の衝突は起こりづらくなるはずです。
まずエントリーを追加する時はキーのハッシュ値を求めます.(これはとなります)
そのハッシュ値をインデックスとして配列Arrayを参照し、そこに値をぶち込みます。
ハッシュ値が衝突していれば既に配列に値が埋まっているのでリストとしてくっつけていきます。
参照を行う時もキーのハッシュ値を求めて配列を参照します。

ここで重要なのがハッシュ値を求める関数が高速であり、なるべく衝突をおこさない値を返すことです。

という事を踏まえてこないだ問題のおきたコードをはります。
ハッシュテーブルの使い方がおかしいのでいつまでたっても終わりません.



なにをしているコードなのかというと8パズルを解くやつです。
構造体で各盤面の状態を定義して幅優先探索で8パズルを解きます。
スロットには盤面を表す大きさ9の配列とかを持っています。

幅優先探索なので重複した状態を探索しないようにするために各状態(構造体)をキーとするハッシュテーブルを使って
記録しているのですが上手く機能してないのでいつまでたっても終わりません。

上のsolveをちょっと変えたのが以下です。



ハッシュテーブルのキーに構造体でなく、盤面を表す配列を指定しています。

このようにしてやるとうまく行きます。sbcl1.2.6の環境で実行してみると


Evaluation took:
2.069 seconds of real time
2.068129 seconds of total run time (1.984124 user, 0.084005 system)
[ Run times consist of 0.504 seconds GC time, and 1.565 seconds non-GC time. ]
99.95% CPU
102 lambdas converted
5,165,940,091 processor cycles
535,698,896 bytes consed

SEARCHED STATE: 181439
SORTEST: 31

-- PATH --

8 6 7
2 5 4
3 0 1

8 6 7
2 0 4
3 5 1

8 0 7
2 6 4
3 5 1

0 8 7
2 6 4
3 5 1

2 8 7
0 6 4
3 5 1

2 8 7
3 6 4
0 5 1

2 8 7
3 6 4
5 0 1

2 8 7
3 6 4
5 1 0

2 8 7
3 6 0
5 1 4

2 8 0
3 6 7
5 1 4

2 0 8
3 6 7
5 1 4

2 6 8
3 0 7
5 1 4

2 6 8
0 3 7
5 1 4

2 6 8
5 3 7
0 1 4

2 6 8
5 3 7
1 0 4

2 6 8
5 3 7
1 4 0

2 6 8
5 3 0
1 4 7

2 6 0
5 3 8
1 4 7

2 0 6
5 3 8
1 4 7

2 3 6
5 0 8
1 4 7

2 3 6
0 5 8
1 4 7

2 3 6
1 5 8
0 4 7

2 3 6
1 5 8
4 0 7

2 3 6
1 5 8
4 7 0

2 3 6
1 5 0
4 7 8

2 3 0
1 5 6
4 7 8

2 0 3
1 5 6
4 7 8

0 2 3
1 5 6
4 7 8

1 2 3
0 5 6
4 7 8

1 2 3
4 5 6
0 7 8

1 2 3
4 5 6
7 0 8

1 2 3
4 5 6
7 8 0


初めのsolveにめちゃくちゃ時間がかかる感じなのは構造体のハッシュ値を出した時に衝突が起こって
それのために時間が掛かっているのではないかと思いました。(リストの線形探索になってしまっているとか開番地法に時間がかかるとか?.処理系の実装がどうなっているのかわからないですが)

なので、sxhashというオブジェクトのハッシュ値を求めてくれるLispの関数を用いて構造体のハッシュ値を求めてたのが以下です。



適当に作った構造体の全てのハッシュ値が一致します。
だから始めの構造体をキーに取るバージョンだと上手くいかないのかと思ったのですが、
これは配列でもこうなります。つまり、



となります。

なので改善したsolveのコードがなぜうまく動いてるのかという話になるのですが、
そもそもハッシュコードを取るのにsxhashは使われていないのかな?とかいろいろ考えていました。

その時にみつけたやつWhy does `sxhash` return a constant for all structs?


Franzの人の回答が貼ってあるっぽいですが、make-hash-tableのhash-functionキーにhash関数を渡してやればいいとか書いて有りますね.処理系依存っぽいですけど。

でSBCLにもあるのか調べてみたらありました。(describe 'make-hash-table)してみると

:HASH-FUNCTION
If NIL (the default), a hash function based on the TEST argument is used,
which then must be one of the standardized hash table test functions, or
one for which a default hash function has been defined using
SB-EXT:DEFINE-HASH-TABLE-TEST. If HASH-FUNCTION is specified, the TEST
argument can be any two argument predicate consistent with it. The
HASH-FUNCTION is expected to return a non-negative fixnum hash code.


ありました。

そうですよね。普通他の言語とかでハッシュテーブル使って任意のオブジェクトをキーにしたいならhashメソッドとか実装されてないとおかしいですもんね。

でこれのラッパーもありました。CL-CUSTOM-HASH-TABLE

これを使って書いてみたのが以下。



実行してみる


Evaluation took:
5.627 seconds of real time
5.620351 seconds of total run time (5.492343 user, 0.128008 system)
[ Run times consist of 0.616 seconds GC time, and 5.005 seconds non-GC time. ]
99.88% CPU
102 lambdas converted
14,043,350,512 processor cycles
841,386,704 bytes consed

SEARCHED STATE: 181439
SORTEST: 31

-- PATH --


8 6 7
2 5 4
3 0 1

8 6 7
2 0 4
3 5 1

〜省略〜


coerceするのが若干ネックになっているのか、遅いですがうまくできました。

配列をキーに取ったときに上手くいったのは謎ですね...






スポンサーサイト

comment 0 trackback 0
トラックバックURL
http://telracsmoratori.blog.fc2.com/tb.php/203-9af4bcaf
トラックバック
コメント
管理者にだけ表示を許可する
 
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。