如何实现 IEqualityComparer有公差

发布于 2024-08-17 20:25:34 字数 790 浏览 6 评论 0原文

这个问题与这里的问题类似。

我们都知道 PointF 是什么，但不知道我们？这是数据结构：

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

如何实现具有容差的 IEqualityComparer？假设我的 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 的字典，我将正确访问元素？

我绞尽脑汁几天了，但仍然找不到满意的解决方案。

原文

This question is similar to the one here.

We all know what PointF is, don't we? This is the data structure:

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

How to implement IEqualityComparer<PointF> with tolerance? Let's say my Equals code is like this

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;
}

Question: How to implement the correct GetHashCode so that for a dictionary of PointF, I will access the element correctly?

I crack my head a few days but still can't find a satisfactory solution.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

初见终念 2024-08-24 20:25:34

您可以将点放置在网格中，而不是通过距离定义容差。
如果两个点位于同一单元格中，则它们被视为相等并且具有相同的哈希码。

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
}

论文：没有满足您要求的Equals 和GetHashCode 实现。

证明：考虑以下三点，A、B、C：

根据您的要求，

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 无法为相同参数返回不同的值，因此没有满足您要求的实现。
qed

Instead of defining the tolerance by the distance, you could place the points in a grid.
If two points are in the same cell, they're considered equal and have the same hash code.

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
}

Thesis: There is no implementation of Equals and GetHashCode that meets your requirements.

Proof: Consider the following three points, A, B, and C:

As per your requirements,

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)

But from (iv) and (v) follows

GetHashCode(A) == GetHashCode(C)

and thereby

Equals(A, C) == true

which contradicts (iii) and (vi).

Since Equals and GetHashCode cannot return different values for the same arguments, there is no implementation that meets your requirements.
q.e.d.

回复收藏 0 原文

野生奥特曼 2024-08-24 20:25:34

我认为这是不可能的，因为您可能有一个无限序列的值，这些值与序列中的前一个值和下一个值相等（在容差范围内），但没有任何其他值，并且 GetHashCode 需要返回所有这些都具有相同的值。

回复收藏 0 原文

走过海棠暮 2024-08-24 20:25:34

嗯，基于网格的答案很好，但有时您无论如何都需要对接近的点进行分组，即使它们不在同一个网格单元中。我的方法是通过分组来实现这一点：如果两个点靠近或者有一系列靠近点连接它们，则它们位于同一组中。此语义无法使用适当的 IEqualityComparer 来完成，因为它需要在生成组之前提前了解所有项目。所以我做了一个简单的LINQ风格的运算符GroupByCluster，它基本上实现了这一点。

代码位于：http://ideone.com/8l0LH。它可以在我的 VS 2010 上编译，但无法在 Mono 上编译，因为 HashSet<> 无法隐式转换为 IEnumerable<>（为什么？）。

该方法是通用的，因此效率不高：它是输入大小的二次方。对于具体类型，它可以变得更高效：例如，对于 T = double，我们只需对输入数组进行排序即可获得 O(n log n) 性能。类似但更复杂的技巧也适用于 2D 点。

注意：您最初的主张不可能用 IEqualityComparer 实现，因为您的“近似相等”不是传递性的（但 IEqualityComparer 中的相等必须如此）。