为 linq groupby 编写自定义比较器

Question

同样，此示例是我的实际问题的非常简化版本，涉及用于 linq 分组的自定义比较器。我做错了什么？

下面的代码产生下面的结果 (1.2, 0), (4.1, 0), (4.1, 0), (1.1, 0),

但是我期待以下内容，因为 1.1 和 1.2 相差 < 1.0。 (1.2, 0), (1.1, 0), (4.1, 0), (4.1, 0),

class Program
{
    static void Main(string[] args)
    {
        IEnumerable<Point> points = new List<Point> { 
            new Point(1.1, 0.0)
            , new Point(4.1, 0.0) 
            , new Point(1.2, 0.0)
            , new Point(4.1, 0.0)
        };

        foreach (var group in points.GroupBy(p => p, new PointComparer()))
        {
            foreach (var num in group)
                Console.Write(num.ToString() + ", ");

            Console.WriteLine();
        }

        Console.ReadLine();
    }
}

class PointComparer : IEqualityComparer<Point>
{
    public bool Equals(Point a, Point b)
    {
        return Math.Abs(a.X - b.X) < 1.0;
    }

    public int GetHashCode(Point point)
    {
        return point.X.GetHashCode()
            ^ point.Y.GetHashCode();
    }
}

class Point
{
    public double X;
    public double Y;

    public Point(double p1, double p2)
    {
        X = p1;
        Y = p2;
    }

    public override string ToString()
    {
        return "(" + X + ", " + Y + ")";
    }
}

Answer 1

不要忘记 GetHashCode 的影响。期望 GetHashCode 对于任何两个对象总是 return 相同的值，因为每个 Equals 将 return 为真。如果你达不到那个期望，你会得到意想不到的结果。

具体来说，GroupBy 可能使用类似于散列 table 的东西来允许它将项目组合在一起，而不必将每个项目与其他项目进行比较。如果 GetHashCode returns 的值最终不会将两个对象放入哈希的同一个桶中 table，它将假定它们不相等，并且永远不会尝试给他们打电话Equals。

当您尝试找出 GetHashCode 的正确实现时，您会发现您尝试对对象进行分组的方式存在根本问题。如果您的点的 x 值为 1.0、1.6 和 2.2，您会期待什么？ 1.0 和 2.2 彼此相距太远而无法归入同一组，但是 1.6 与其他两个点足够近，因此应该与它们在同一组中。所以你的 Equals 方法打破了等式的 Transitive 属性:

whenever A = B and B = C, then also A = C

如果您尝试进行集群分组，您将需要使用更不同的数据结构和算法。如果您只是想稍微规范化点的位置，您可以只说 points.GroupBy(p => (int)p.X) 并完全避免相等比较器。

Answer 2

使用相等比较器的分组算法（我认为所有 LINQ 方法）总是首先比较哈希码，只有在两个哈希码相等时才执行 Equals。可以看到，如果在相等比较器中添加跟踪语句：

class PointComparer : IEqualityComparer<Point>
{
    public bool Equals(Point a, Point b)
    {
        Console.WriteLine("Equals: point {0} - point {1}", a, b);
        return Math.Abs(a.X - b.X) < 1.0;
    }

    public int GetHashCode(Point point)
    {
        Console.WriteLine("HashCode: {0}", point);
        return point.X.GetHashCode()
            ^ point.Y.GetHashCode();
    }
}

这导致：

HashCode: (1.1, 0)
HashCode: (4.1, 0)
HashCode: (1.2, 0)
HashCode: (4.1, 0)
Equals: point (4.1, 0) - point (4.1, 0)
(1.1, 0), 
(4.1, 0), (4.1, 0), 
(1.2, 0),

只对哈希码Equals相等的两点执行

现在您可以通过始终返回 0 作为哈希码来欺骗比较。如果这样做，输出将是：

HashCode: (1.1, 0)
HashCode: (4.1, 0)
Equals: point (1.1, 0) - point (4.1, 0)
HashCode: (1.2, 0)
Equals: point (4.1, 0) - point (1.2, 0)
Equals: point (1.1, 0) - point (1.2, 0)
HashCode: (4.1, 0)
Equals: point (4.1, 0) - point (4.1, 0)
(1.1, 0), (1.2, 0), 
(4.1, 0), (4.1, 0),

现在每对 Equals 都被执行了，你已经有了你的分组。

但是...

什么是"equal"？如果再加一个点(2.1, 0.0)，你要哪一组点？使用符号 ≈ 表示模糊等式，我们有 -

1.1 ≈ 1.2
1.2 ≈ 2.1

但是

1.1 !≈ 2.1

这意味着 1.1 和 2.1 永远不会在一组（他们的 Equals 永远不会通过）并且 这取决于点的顺序 1.1 或 2.1 是否与 1.2 分组。

所以你在这里很滑。按邻近度聚类点绝非微不足道。您正在进入 cluster analysis.

的领域

为 linq groupby 编写自定义比较器

writing a custom comparer for linq groupby

linq

iequalitycomparer