Wer kennt das nicht. Man hat eine Liste von Werten auf der einen Seite und eine zweite Liste von Werten auf der anderen Seite. Diese gilt es nun abzugleichen. Vor dieser – wie ich dachte – sehr einfachen Herausforderung stand ich am Freitag. *Pff*. Nichts leichter als das dachte ich mir. Meine Idee war:

– Liste A durchlaufen und schauen ober der aktuelle Wert in Liste B vorkommt.
– Kommt der Wert in der Liste B vor, so kann er aus beiden Listen entfernt werden
– Am Ende habe ich eine bereinigte Liste A, deren Werte in der B Liste noch fehlen
– Und zum anderen eine Liste B, deren Werte in der Liste A nicht mehr vorhanden waren und somit obsolet sind (also gelöscht werden können)

Klappt einwandfrei. Hier das entsprechende Beispiel. Mit einer Liste von ‚int‘ wäre das natürlich langweilig, darum habe ich mir hier ein kleines Kundenobjekt gebastelt:

1
2
3
4
5
6
7
8
9
10
11

public class Kunde
{
    public string Vorname { get; set; }
    public string Nachname { get; set; }
 
    public Kunde(string vorname, string nachname)
    {
         Vorname = vorname;
         Nachname = nachname;
    }
}

Füllen wir das Ganze mal mit ein paar Dummy-Werten und auch einigen Einträgen die nicht gleich sind …

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

List<Kunde> KundenListe1 = new List<Kunde>();
List<Kunde> KundenListe2 = new List<Kunde>();
 
public FrmMain()
{
    InitializeComponent();
    ListenLaden(20000);
}
 
private void ListenLaden(int value)
{
    KundenListe1.Clear();
    KundenListe2.Clear();
    for (int i = 0; i < value; i++)
    {
        KundenListe1.Add(new Kunde("Hans", "Wurscht_" + i.ToString()));
 
        if (i % 2500 == 0)
            KundenListe2.Add(new Kunde("Hans", "Wurscht_X" + i.ToString()));
        else
            KundenListe2.Add(new Kunde("Hans", "Wurscht_" + i.ToString()));
    }
}

Die Methode zum Vergleichen sieht dann wie folgt aus:
(Anmerkung: Hab‘ da einige Varianten durchprobiert. So in etwas sah einer meiner Versuche aus.)

1
2
3
4
5
6
7
8
9
10
11
12
13

private void Vergleich()
{
    for (int i = 0; i < KundenListe1.Count; i++)
    {
        Kunde kunde = KundenListe2.Find(item => item.Vorname.Equals(KundenListe1[i].Vorname) && item.Nachname.Equals(KundenListe1[i].Nachname));
        if (kunde != null)
        {
            KundenListe2.Remove(kunde);
            KundenListe1.RemoveAt(i);
            i--;
        }
    }
}

Versehen wir das Ganze mit einer kleinen Stoppuhr, so sehen wir, dass der Vergleich (bei meinem PC) ca. 600 ms dauert. Also wo ist das Problem? Naja. Erhöhen wir doch mal die Anzahl der Einträge um 180.000. Sprich nun befinden sich 200.000 Elemente in der Liste. Schon dauert der Vorgang ein wenig länger, nämlich ca. 73 Sekunden. Man merkt deutlich, dass die Performance zu wünschen übrig lässt.

Nun, bei meinem Projekt musste ich keine 200.000 Einträge abgleichen, sondern 2.500.000 Einträge – und das Objekt hatte mehr als zwei Eigenschaften zum abgleichen. Da das Ganze nicht zeitkritisch ist, habe ich den Task für Samstag um sieben Uhr morgens angesetzt. Das Ende war leider nicht absehbar …

Also habe ich mich auf die Suche gemacht, wie man es ‚richtig‘ machen könnte. Wer jetzt glaubt, dass eine bessere Lösung aufwendiger ist, täuscht sich.

Schritt 1: Wir überschreiben in unserer Klasse ‚Kunde‘ zwei Funktionen. Über die ‚richtige‘ Implementierung von GetHashCode lässt sich an dieser Stelle streiten, daher möchte ich darauf jetzt auch gar nicht näher eingehen.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public override bool Equals(object obj)
{
    if (obj.GetType() != typeof(Kunde))
    {
        return false;
    }
    else
    {
        Kunde kunde = obj as Kunde;
        return kunde.Nachname.Equals(this.Nachname) && kunde.Vorname.Equals(Vorname);
    }
}
 
public override int GetHashCode()
{
    return Vorname.GetHashCode() + Nachname.GetHashCode();
}

Schritt 2: Wir brauchen eine neue Methode um die beiden Listen miteinander zu vergleichen. Hey. Was ist denn das, was uns das .NET Framework in der Version 3.5 mitgebracht hat: Enumerable.Intersect & Enumerable.Except.
Mit der Except Methode vergleicht man zwei Listen miteinander und bekommt als Ergebnis eine Liste mit alle Elementen, die in der erste Liste vorkommen, nicht aber in der zweiten. Hmm. War das nicht genau das was ich brauche? Somit sieht die neue Methode zum vergleichen so aus:

1
2
3
4

private void Vergleich()
{
    List<Kunde> differenz = KundenListe1.Except(KundenListe2).ToList();
}

Lassen wir den Worten doch Zahlen folgen: Für die 200.000 Einträge benötigen wir gerade mal 200 ms um die Differenzliste zu erstellen. Gut. Man muss fairerweise dazusagen: Man braucht noch die zweite Differenz in die andere Richtung. Aber selbst dann ist der Spuk in ca. 250 ms vorbei.

Und wie sieht das bei 2.500.000 Elementen aus? Was soll ich sagen – die Initialisierung der Elemente dauert länger als der Vergleich (1,5 Sekunden).

Hier werden die beiden Methoden nochmal sehr anschaulich dargestellt:
Except
Intersect

Vielen Dank an http://gehirnwindung.de/ für diese sehr anschaulichen Beispiele!

Hier noch ein paar Informationen zu GetHashCode
MSDN: GetHashCode
MSDN: Override GetHashCode on overriding Equals
Stackoverflow – kurze Diskussion über: Wie / Warum