フロートの比較に伴うすべての問題をよく知っています。これがまさにこの質問の理由です。
3D ベクトル (3 つの浮動小数点数 - x、y、z) である値の高速ハッシュ テーブルを作成しようとしています。sqrt(x*x+y*y+z*z)ベクトルの長さは常に 1.0 (は 1.0) であると仮定できます。
基本的に、これは、同じ unsigned int 値とほぼ等しい値を取るハッシュ関数と、ハッシュ値が等しい場合に真である対応する等値演算子を探していることを意味します (必ずしもそれらが等しい場合だけではありません)。
編集-
これはハッシュ テーブルであるため、誤検知 (つまり、異なるが同じバケットにマップされるベクトル) が発生します。
偽陰性 (つまり、近いが異なるバケットにマップされるベクトル) は望ましくありませんが、それらを回避する方法はないようです。私の場合、それらは完全な破損を引き起こすわけではなく、私が対処しなければならないデータの重複だけです。
あなたが探していることは直接可能ではないと思います。平等の重要な特性の 1 つは、それが推移的であることです。(つまり、a == b かつ b == c の場合、a == c)。ただし、距離測定では、このプロパティは必要ありません。例：
単一の float を使用します (簡単にするため)。1e-3 未満離れた float が同じ値になるように、各 float をハッシュしたいとします。ここで、このハッシュ テーブルに 1000 個の float 値をすべて 1e-4 間隔で追加するとします。隣接する 2 つの値は、1e-3 よりも近いため、同じ float にハッシュする必要があります。ただし、推移性のため、これらの値の隣人も同じ値にする必要があり、その隣人なども同様です。その結果、1e-3 より離れたペアを含む 1000 個の値すべてが同じ整数にハッシュされます。これらの点を絵に描くとしたら:
A B C D E F G H ... Y Z
すべてのギャップが < 1e-3 離れているが、A と Z は > 1e-3 離れているとします (縮尺どおりではありません!)。これは満たすことができません。なぜなら、ハッシュ (A) == ハッシュ (B) およびハッシュ (B) == ハッシュ (C) などのすべてのペアに対して (それらが < 1e-3 離れているため) ハッシュ (A ) == ハッシュ (Z) でなければなりません。
考えられるオプションの 1 つは、すべてのベクトルが同じ値にハッシュされるベクトル空間の領域を定義することです (つまり、ハッシュする前にそれらを丸めます)。別の値に。隣接するすべての空間でベクトルを検索することで、これを回避できます。(つまり、上記の 1-d の場合、すべてのベクトルを最も近い 1e-3 の倍数に丸め、次に隣接するものを検索するため、5.3e-3 は 5e-3、4e-3、および 6-e3 を検索します。高次元の場合、すべての次元で近傍を検索する必要があります。)
float 値を次のように整数に変換します。
unsigned int IntValue = (int)(floatValue * MULT) + MULT;
したがって、最初の数字のいくつかを取得してから使用します
const MULT1 = (MULT << 1) + 1;
unsigned long long HashValue = (xIntValue * MULT1 * MULT1) + (yIntValue * MULT1) + zIntValue;
ハッシュ値として ((MULT * 2) + 1 を使用します。これは、IntValues が 0 と MULT * 2 の間になるためです)。
必要なメモリは、乗算器 MULT によって異なります。たとえば、32 を使用すると、64 * 64 * 64 * (ハッシュ項目のサイズ) = 262144 * (ハッシュ項目のサイズ) バイトを使用するハッシュテーブルが得られます。
一部の言語 (C、Java 5) では、float のバイナリ値にアクセスできます。このようにして、仮数の最初の N ビットを抽出し (比較中に問題を引き起こす最後の数ビットを無視します)、そこからハッシュを計算できます。
K 最近の問題を効果的に解こうとしていると思います。あなたが探しているのはlocalitysensitive hashingだと思います。また、四分木構造を使用して同じ結果を得ることができます。
あなたの問題について詳しく説明できますか？
ハッシュマップを使用していくつかの追加データを特定のベクトルにマップすると仮定すると、コンポーネントのバイナリ表現の XOR を使用できます (選択した言語でこれが可能な場合)。次に、ハッシュ マップに必要な数の LSB を (衝突を減らすために) 使用します。もちろん、これには、2 つの等しい (浮動小数点比較による) ベクトルが同じハッシュを持たない可能性があるという特性があります (たとえば、IEEE 浮動小数点 0 は -0 に等しいが、符号ビットが異なります)。
ただし、異なる計算の結果であるベクトルを使用してハッシュ ルックアップを行うことを計画している場合は、丸め誤差のためにハッシュ コードが一致しない可能性があるため、いずれにしても別のものを使用する必要があります。
高速なハッシュ テーブルである必要がありますか?それともツリー構造で十分ですか?
ある種の検索ツリーで一致するフロートを検索する方が簡単だと私には思えます。Bツリーは、適切なノード サイズを選択すると、キャッシュ ミスの数を最小限に抑えます。これにより、実際にはかなり高速になるはずです。
これがどれほど速いかはわかりませんが、単位ベクトルがあるので、それらはすべて球の表面にあります。http://en.wikipedia.org/wiki/Spherical_coordinate_systemに変換します。次に、ファイとシータを使用してバケットを選択します。誤検知はありません。隣接するセルで偽陰性を調べることができます。