12

通常、 float を で比較する==のは間違いであることはよく知られています。3D ベクトル クラス (float コンポーネント X、Y、Z) では、距離がゼロと見なされる場合、2 つのベクトルは等しいと見なされます。

public override bool Equals(object obj)
{
    if (obj == null) {
        return false;
    }

    if (GetType () != obj.GetType ()) {
        return false;
    }

    float d = DistSq ((Vec) obj);

    return IsConsideredZero (d);
}

public float DistSq(Vec p)
{
    Vec d = this - p;
    return d.LengthSq ();
}

public float LengthSq()
{
    return X * X + Y * Y + Z * Z;
}

private const float VEC_COMPARE_EPSILON_ABS = 1E-05f;
public static bool IsConsideredZero(float f)
{
    return Math.Abs (f) < VEC_COMPARE_EPSILON_ABS;
}

これまでのところ、すべてうまくいきました。ただし、ベクターのハッシュコードを取得したいと思います。hash = (int)X^(int)Y^(int)Zのようなものは必ず失敗することがわかります。

私が思いついた最高のものは次のとおりです。

public override int GetHashCode()
{
    return 0;
}

もちろん、これはちょっと面倒です。妥当なハッシュコードを取得する方法はありますか? NaN やその他の特別な値は可能ですが、それが重要な場合はほとんどありません。

4

5 に答える 5

15

通常のハッシュコード/等価プロパティが必要だと仮定することは不可能です。

  • X = Y かつ Y = Z の場合、X = Z (推移性)
  • X = Y の場合、Y = X (可換性)
  • X = X for all X (再帰性)

最初のルールが問題です。各値が次に大きい表現可能な数値と「等しい」と見なされると、すべての数値が等しくなってしまうからです。たとえば、0.1 以内の数値が別の数値と等しいと見なされるとします。

0 は 0.08 に等しい 0.08 は 0.16 に等しい 0.16 は 0.24 に等しい

=> 0 は推移性ルールにより 0.16 に等しい => 0 は推移性ルールにより 0.24 に等しい

（等）

推移性ルールを無視すると、(おそらく) 「等しい」値に等しいハッシュコードが必要になります。これにより、推移性ルールが効果的に適用されます。上記の例では、0 と 0.08 は、0 と 0.16 と同様に、等しいハッシュコードを持つ必要があります。したがって、0 と 0.16 のハッシュコードは等しくなければなりません。したがって、有用なハッシュコードを持つことはできません- それは定数でなければなりません。

于 2009-02-24T08:27:55.793 に答える
8

後者は推移的ではないため、比較方法と一致するハッシュコードを持つことはできないと思います: 3 つのベクトル A、B、C について、A.Equals(B)とB.Equals(C)が true の場合でも、A.Equals(C)false である可能性があります。(A と B の間の距離が 6e-6、B と C の間の距離が 6e-6、A と C の間の距離が 1.2e-5 であると想像してください) しかし、ハッシュコードは単なる数値であるため、ハッシュコードの等価性は常に推移的です。

この場合、浮動小数点座標の正確な値に基づいてハッシュを計算する hashcode メソッドを作成し、ドキュメンテーションで equals と矛盾することを述べます。私はそれが実際には解決策ではないことを知っていますが、実際の解決策が存在するとは思わないことを考えると、単なる0よりも自明でないハッシュコードを持つ方が良い.

于 2009-02-24T08:28:24.047 に答える
7

一般的なケースではないと思います。証明のスケッチは次のようになります。

任意の 2 つの数字 a と b を取ります。それらの差を d とする。次に、イプシロンステップを間に挟んで d/イプシロン数を作成する場合、各ステップは前のステップと「等しく」なければなりません。これは、ハッシュコードセマンティクスによって同じハッシュコードを持ちます。したがって、すべての数値は同じハッシュコードを持つ必要があります。

他の制約を追加する場合にのみ、この問題を解決できます。

余談ですが、Equals の定義も間違っています。a.Equals(b) と b.Equals(c) は true ですが、a.Equals(c) は true ではなく、equals では間違っています。これは、 Transitivityプロパティを壊すこととして知られています。

その場合、私は何ができますか？

解決策は、ハッシュを何に使用しているかによって異なります。1 つの解決策は、概念的なグリッドを導入することです。等号とハッシュコードを変更して、同じグリッド キューブ内にある場合に 2 つの数値が等しくなるように、定数の小数点以下の桁数に丸め、丸められた数値で等号とハッシュコードを取得します。ゼロに近いことが重要な場合は、丸めの前に epsilon/2 のオフセットを追加して、ゼロが立方体の中心になるようにします。これは正しいですが、2 つの数値を等しくせずに (float の制限内で) 任意に近づけることができます。したがって、一部のアプリケーションでは問題ありませんが、そうでないアプリケーションもあります。これはmghieのアイデアに似ています。

于 2009-02-24T08:27:56.107 に答える
4

みんな正解…

ただし、よく行われることの 1 つは、ハッシュの概念を少し拡張することです。側面 >> イプシロンのボックスで 3D 空間を分割することを検討してください。

ポイントのハッシュは、それが属するボックスです。ポイントを検索する場合、対応するボックスでポイントをチェックするのではなく (通常のハッシュの場合と同様)、隣接するボックスもチェックします。3D では、最大 8 つのボックスで回避する必要があります。

于 2009-02-24T08:48:42.170 に答える
2

解決できないものを提示したため、どのような手法を使用しても問題が発生します。

必要なのは、1) ほとんどの数値 a と b で a != b の場合、a.GetHashCode() != b.GetHashCode() のように均等に分散されたハッシュですが、2) a == b の場合 a.GetHashCode() = の場合です。 = b.GetHashCode() は true でなければなりません。

定数を返すと、(2) は満たされますが、(1) は満たされません。

1E-5 境界で丸め、それをハッシュ違反として使用すると、(1) は満たされますが、(2) は違反されることを示すことができます。たとえば、1E-5 と 2E-5 を見てみましょう。丸めによって 2 つの異なるハッシュ値が生成されますが、比較すると同等です。これは、上記の制約 (2) に違反します。これを簡単に一般化して、数値を丸めると同様の問題が発生することを証明できます。

別のアプローチを選択することをお勧めします。根本的な問題は、あるポイントが既に持っているポイントに近いかどうかを判断することだと思います。座標空間を再帰的に半分に分割することをお勧めします (境界に沿ったポイント (つまり、境界から <=1E-5) の両方の半分)。スペースを段階的に分割すると (バイナリ ツリーを考えてください)、必要な結果をすばやく返し、作成が非常に簡単なデータ構造を作成できます。

私が推測に失敗し、ハッシュを使用する必要がある場合は、それぞれ 1E-5 に丸められますが、5E-6 だけオフセットされる 2 つのハッシュ値を使用して、必要なことを行うことができます。すべての等しい点は、2 つのハッシュ値のいずれかで等しいと比較されます。これには、ハッシュ ルーチンごとに 1 回ずつ、ハッシュ テーブルにポイントを 2 回入力する必要があります。

于 2009-02-24T09:18:52.567 に答える