Schreiben eines benutzerdefinierten Vergleichs für linq groupby

Question

Wieder ist dieses Beispiel eine sehr vereinfachte Version meines tatsächlichen Problems mit einem benutzerdefinierten Vergleich für linq Gruppierung. Was habe ich falsch gemacht?

Der folgende Code erzeugt das Ergebnis unter (1.2, 0), (4.1, 0), (4.1, 0), (1.1, 0),

jedoch seit 1.1 die folgende erwartete ich und 1.2 sind < 1,0 auseinander. (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

Der Gruppierungsalgorithmus (und ich denke, alle LINQ-Methoden) mit einem Gleichheitsvergleich vergleicht immer zuerst Hash-Codes und führt nur Equals aus, wenn zwei Hash-Codes gleich sind. Sie können sehen, dass, wenn Sie Tracing-Anweisungen in dem Gleichheitsvergleich hinzufügen:

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

was zur Folge hat:

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), 

Nur für die beiden Punkte mit dem gleichen Hash-Codes Equals ausgeführt wurde.

Jetzt können Sie den Vergleich tricksen, indem Sie immer 0 als Hash-Code zurückgeben. Wenn Sie das tun, wird der Ausgang sein:

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), 

nun für jedes Paar Equals wurde ausgeführt, und Sie haben Ihre Gruppierung bekommen.

Aber ...

Was ist "gleich"? Wenn Sie einen weiteren Punkt (2.1, 0.0) hinzufügen, welche Punkte möchten Sie in einer Gruppe? Mit dem Symbol ≈ für die Fuzzy-Gleichheit, wir haben -

1.1 ≈ 1.2 
1.2 ≈ 2.1 

aber

1.1 !≈ 2.1 

Das bedeutet, dass 1.1 und 2.1 nie in einer Gruppe sein (ihr Equals nie passiert), und dass es hängt in der Reihenfolge der Punkte ob 1.1 oder 2.1 sind mit 1.2 gruppiert.

Sie sind also hier auf einem rutschigen Abhang. Clustering Punkte durch Nähe ist bei weitem nicht trivial. Du betrittst das Reich cluster analysis.

Answer 2

Vergessen Sie nicht, die Auswirkungen von GetHashCode. Es wird erwartet, dass GetHashCode immer den gleichen Wert für zwei Objekte zurückgibt, für jede Equals würde True zurückgegeben. Wenn Sie diese Erwartung nicht erfüllen, werden Sie unerwartete Ergebnisse erhalten.

Speziell verwendet GroupBy wahrscheinlich so etwas wie eine Hash-Tabelle, um es zu ermöglichen, Elemente zusammen zu gruppieren, ohne jedes Element mit jedem anderen Element zu vergleichen. Wenn GetHashCode einen Wert zurückgibt, der nicht zwei Objekte in den gleichen Bucket der Hash-Tabelle bringt, wird davon ausgegangen, dass sie nicht gleich sind, und niemals versuchen, Equals für sie aufzurufen.

Sie werden feststellen, wie Sie versuchen, eine korrekte Implementierung für GetHashCode herauszufinden, dass ein grundlegendes Problem damit besteht, wie Sie Ihre Objekte gruppieren möchten. Was würden Sie erwarten, wenn Sie Punkte mit x-Werten von 1.0, 1.6 und 2.2 hätten? 1.0 und 2.2 sind zu weit voneinander entfernt, um in die gleiche Gruppe zu fallen, aber 1.6 ist nahe genug an beiden anderen Punkten, dass es in der gleichen Gruppe mit ihnen sein sollte. So Ihre Equals Methode bricht die Transitive Eigenschaft der Gleichheit:

, wenn A = B und B = C, dann ist auch A = C

Wenn Sie versuchen, Cluster-Gruppierung zu tun, du bist müssen eine andere Datenstruktur und einen anderen Algorithmus verwenden. Wenn Sie nur versuchen, die Standorte der Punkte etwas zu normalisieren, können Sie vielleicht einfach points.GroupBy(p => (int)p.X) sagen und den Gleichheitsvergleich vollständig vermeiden.