8

この質問は、こちらの質問と似ています。

私たちは皆、PointFが何であるかを知っていますね。これはデータ構造です：

public struct PointF
{
  public float X;
  public float Y;
}

IEqualityComparer<PointF>寛容に実装するには？私のEqualsコードがこのようなものだとしましょう

public const float Epsilon = 0.01; //say
public bool Equals(PointF pt1, PointF pt2)
{
   return Math.Abs(pt1.X-pt2.X)<Epsilon && Math.Abs(pt1.Y-pt2.Y)<Epsilon;
}

質問:GetHashCodeのディクショナリでPointF要素に正しくアクセスできるように、正しい を実装するにはどうすればよいですか?

数日頭を悩ませていますが、それでも満足のいく解決策が見つかりません。

4

3 に答える 3

14

距離で公差を定義する代わりに、点をグリッドに配置できます。
2 つのポイントが同じセルにある場合、それらは等しいと見なされ、同じハッシュ コードを持ちます。

public bool Equals(PointF pt1, PointF pt2)
{
   return GetCell(pt1.X) == GetCell(pt2.X)
       && GetCell(pt1.Y) == GetCell(pt2.Y);
}

public int GetHashCode(PointF pt)
{
   return GetCell(pt.X) ^ GetCell(pt.Y);
}

private static int GetCell(float f)
{
    return (int)(f / 10); // cell size is 10 pixels
}

命題:要件を満たすEqualsandの実装はありません。GetHashCode

証明:次の A、B、C の 3 点を考えます。

図

ご要望に応じて、

Equals(A, B) == true              // (i)
Equals(B, C) == true              // (ii)
Equals(A, C) == false             // (iii)
GetHashCode(A) == GetHashCode(B)  // (iv)
GetHashCode(B) == GetHashCode(C)  // (v)
GetHashCode(A) != GetHashCode(C)  // (vi)

しかし、(iv) と (v) から、

GetHashCode(A) == GetHashCode(C)

それによって

Equals(A, C) == true

これは (iii) と (vi) に矛盾します。

EqualsとGetHashCodeは同じ引数に対して異なる値を返すことができないため、要件を満たす実装はありません 。した

于 2010-01-13T08:58:47.400 に答える
1

GetHashCodeシーケンス内の前の値と次の値に等しい (許容範囲内で) 値の無限のシーケンスを持つことができますが、他の値ではなく、それらすべてに対して同一の値を返す必要があるため、それは可能ではないと思います。

于 2010-01-13T09:01:37.657 に答える
0

まあ、グリッドに基づく答えは良いですが、同じグリッドセルにない場合でも、とにかく近いポイントをグループ化する必要がある場合があります。私のアプローチは、これをグループ化して実装することです。2つのポイントが近いか、それらを接続する一連の近いポイントがある場合、2つのポイントは同じグループにあります。IEqualityComparerこのセマンティクスは、グループを作成する前にすべての項目を事前に知っている必要があるため、適切に実行することはできません。GroupByClusterそこで、基本的にこれを実現する単純なLINQスタイルの演算子を実行しました。

コードはここにあります：http：//ideone.com/8l0LH。VS 2010でコンパイルしますが、HashSet<>暗黙的に変換できないため、MonoでコンパイルできませんIEnumerable<>（なぜですか？）。

このアプローチは一般的であるため、あまり効率的ではありません。入力サイズは2次式です。具体的なタイプの場合は、より効率的にすることができます。たとえば、T = doubleの場合、入力配列を並べ替えてO(n log n)パフォーマンスを得ることができます。類似しているがより複雑なトリックは、2Dポイントにも適用できます。

余談ですがIEqualityComparer、「近似等式」は推移的ではないため、最初の命題をで実装することは不可能です（ただし、の等式は推移的でIEqualityComparerある必要があります）。

于 2012-09-13T11:05:44.140 に答える