C++0x 3 - 暇つぶし2ch

C++0x 3 at TECH

574:564
08/05/05 22:10:03
>>570
なんで似たようなハッシュ値が近いbucketに入る必要があると思うの？
そういう必要は無いですよ、と588で
> このとき、隣接領域で bucket 番号が隣接している必要はない。
と明記したつもりなんだけどなあ。

具体例で説明すると、たとえば 1000×1000 のメッシュに切って、
(x/1000)×(y/1000) % 100 をハッシュ関数として設定したとしよう。
ここに (10000,10000) の点 p が与えられたとしよう。
この点を含む領域に対応するハッシュ関数値は (10×10) % 100 = 0 だから、
ハッシュ関数値 0 に対応する bucket を持ってくればいい。
(点 p に対して bucket(p) を実行することが、この操作に対応する）

次に、この点を含む領域の左側の領域を調べることにしよう。
左側の領域の座標に対応するハッシュ関数値は (9×10) % 100 = 90
だから、ハッシュ関数値 90 に対応する bucket を持ってくればいい。
（p を左に 1000 だけ平行移動した点 q に対して
　bucket(q) を実行することがこの操作に対応する）

次ページ

続きを表示

1を表示