LINQ: Gruppierung nach einem Intervall

Nehmen wir folgendes Szenario an:

Es gibt eine Liste ist mit Einträge bestehend aus

• Name: wer hat den Eintrag gemacht
• Datum/Zeit: wann wurde der Eintrag getätigt
• Eintrag: die Daten des Eintrags (können beliebiger Natur sein)

gefüllt. Die Abfrage soll alle Einträge gruppiert nach Namen wiedergeben. Soweit kein Problem.

var query1 = list.GroupBy(i => i.Name);

Wenn aber alle Einträge die ein Benutzer (Name) innerhalb eines bestimmten Zeitintervalls getätigt hat gruppiert werden sollen so wird es (auf den ersten Blick) etwas komplizierter.

Im Internet gibt es zwar einige Ansätze aber alle die ich gefunden habe sind nicht zielführend und deshalb unterbreite ich hier meinen Lösungsweg. Dies soll anhand eines Beispiel erklärt werden. Das Beispiel setzt bei obigen Szenario an.

Wie funktioniert Gruppierung?

Beim Gruppieren wird jedes Element der Liste mit jedem anderen Element verglichen und falls der zur Gruppierung verwendete Schlüssel ident ist werden die Member des Elements im Ergebnis einer Lookup-Tabelle unter dem jeweiligen Schlüssel hinzugefügt.

Die Lookup-Tabelle verwendet für effiziente Verarbeitung Hash-Werte für die Schlüssel. Somit basiert der Vergleich der Elemente bzw. deren Schlüssel auf einem Vergleich der Hash-Werte. Sollte die zu vergleichenden Hash-Werte ident sein dann wird der Standardvergleich verwendet (vererbt von System.Object: Equals).

Somit kann die Gruppierung mit dem Standardvergleich für unsere Aufgabe nicht genutzt werden. Deshalb definieren wir einen eigenen Vergleich.

Klasse für Listeneinträge

Nachfolgend wird eine Klasse definiert mit deren Instanzen die Liste gefüllt wird.

[DebuggerDisplay("{Name} | {Datum}")]
public class Item
{
    public string Name { get; set; }   
    public DateTime Datum { get; set; }   
    public string Eintrag { get; set; }
}

Zur Erleichterung des Debugging wird die Klasse mit dem DebuggerDisplay-Attribut versehen. Hierbei wird festgelegt welche Member in der Variablenansicht gezeigt werden sollen. Sonst ist an der Klasse nichts besonderes.

Schlüssel und Vergleich

Schlüssel

Zur Gruppierung wird ein Schlüssel verwendet. Die Implementierung zeigt folgender Code. Da für unsere Aufgabe nach dem Namen und dem Datum gruppiert werden soll werden diese als Eigenschaften implementiert.

public class Key
{
    public string Name { get; set; }   
    public DateTime Datum { get; set; }
}

Vergleich

public class KeyComparer : IEqualityComparer<Key>
{
    bool IEqualityComparer<Key>.Equals(Key x, Key y)
    {
        return x.Name == y.Name && Math.Abs((x.Datum - y.Datum).TotalMinutes) < 5;
    }
    
    //---------------------------------------------------------------------   
    int IEqualityComparer<Key>.GetHashCode(Key obj)
    {
        return 0;    
    }
}

Obiger Code zeigt die Implementierung der Klasse die zum Vergleich verwendet wird. Sie implementiert die IEqualityComparer<T>-Schnittstelle. Wie eingangs erwähnt erfolgt der Vergleich zuerst nach dem Hash-Wert. Hier wird in der Methode GetHashCode konstant 0 zurückgeben (anderer Wert ist auch möglich – muss nur konstant sein) um den Vergleich auf die Equals-Methode “weiterzuleiten”.

In Equals wird geprüft ob die Namen ident sind und die Differenz der DateTime kleiner als das festgelegte Intervall ist. Beispielhaft wurden 5 Minuten verwendet.

Die Abfrage

Für die Abfrage wird die Überladung der Enumerable.GroupBy-Methode verwendet inder ein spezifischer Vergleich angegeben werden kann.

var query = list.GroupBy
(
    // Als Schlüssel eine Instanz von Key verwenden denn 
    // dafür wurde der Comparer definiert.        key =>
    new Key{Name = key.Name, Datum = key.Datum}, (key, groupItems) => new 
    {
        Name = key.Name,
        Einträge = groupItems.Select(g => g.Eintrag)
    },
    new KeyComparer() 
);

Für den Schlüssel wird eine Instanz der oben definierten Key-Klasse verwendet. Für diese Klasse wurde auch der IEqualityComparer definiert, von dem eine Instanz als letztes Argument übergeben wird. Somit ist es möglich eine Gruppierung nach einem Intervall (oder unscharfe Gruppierung / fuzzy grouping) zu ermöglichen.

Anmerkungen

• Diese Möglichkeit existiert nur für LINQ to Objects
• Statt einer Klasse für den Schlüssel und den Vergleich zu implementieren könnte die Klasse für die Listeneinträge derart geändert werden dass diese Klasse die IEquatable<T>-Schnittstelle implementiert und somit der Standardvergleich der Klasse geändert wird. Dies hat allerdings einen Nachteil: Es wird der Standardvergleich der Klasse geändert und dies kann fehlerhafte Auswirkungen auf andere Teile des Programms haben die auf dem Standardvergleich dieser Klasse beruhen.

Beispielprogramm

Nachfolgend ein Beispiel das vorstehendes zusammenfassend zeigt.

using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;

namespace GroupBy_Intervall
{
    class Program
    {
        static void Main(string[] args)
        {
            // Liste der Items erstellen:   
            List<Item> list = new List<Item>   
            {
                new Item{Name="A", Eintrag="A1", Datum=new DateTime(2009,6,11,12,0,0)},               
                new Item{Name="A", Eintrag="A2", Datum=new DateTime(2009,6,11,12,4,0)},               
                new Item{Name="B", Eintrag="B1", Datum=new DateTime(2009,6,11,12,0,0)},               
                new Item{Name="A", Eintrag="A1", Datum=new DateTime(2009,6,10,12,0,0)} 
            };

            // Die Abfrage:        
            var query = list.GroupBy
                (
                // Als Schlüssel eine Instanz von Key verwenden denn 
                // dafür wurde der Comparer definiert.      
                key =>

                   new Key
                   {
                       Name = key.Name,
                       Datum = key.Datum
                   }, (key, groupItems) =>

                   new
                   {
                       Name = key.Name,
                       Einträge = groupItems.Select(g => g.Eintrag)
                   },

                   new KeyComparer());

            // Kontrollausgabe:           
            foreach (var group in query)
            {
                Console.WriteLine("Name: {0}", group.Name);
                foreach (var eintrag in group.Einträge)
                    Console.WriteLine("\tEintrag: {0}", eintrag);
            }

            Console.ReadKey();
        }
    }
    //------------------------------------------------------------  
    public class Key
    {
        public string Name { get; set; }
        public DateTime Datum { get; set; }
    }
    //------------------------------------------------------------   
    public class KeyComparer : IEqualityComparer<Key>
    {
        bool IEqualityComparer<Key>.Equals(Key x, Key y)
        {
            return x.Name == y.Name &&
                Math.Abs((x.Datum - y.Datum).TotalMinutes) < 5;
        }
        //--------------------------------------------------------       
        int IEqualityComparer<Key>.GetHashCode(Key obj)
        {
            return 0;
        }
    }
}

Das Programm liefert korrekt die gewünschte Ausgabe:

Name: A
    Eintrag: A1
    Eintrag: A2
Name: B
    Eintrag: B1
Name: A
    Eintrag: A1