Saturday, July 25, 2009

Listen vergleichen

Immer wieder stolpere ich über diesen Fehler...

Anforderung ist es den Inhalt zweier Listen miteinander zu vergleichen und hierbei Übereinstimmungen zu finden und in eine dritte Liste zu übernehmen. Der größte Fehler den man hier machen kann ist eine verschachtelte Schleife welche jeden Datensatz der einen Liste mit jedem Datensatz der zweiten Liste vergleicht.

Gehen wir mal davon aus dass zwei Listen jeweils 40.000 Werte Enthalten und die Übereinstimmungen gesucht werden sollen.

Zwei verschachtelte Schleifen
Der erste Ansatz sieht oft so aus:
// Zwei Beispiel-Sourcen
int count = 40000;
List<string> source1 = new List<string>(count);
List<string> source2 = new List<string>(count);

// Jeweils mit 40000 Einträgen füllen
for (int i = 0; i < count; i++)
{
   source1.Add(string.Format("String_{0}", i));
   source2.Add(string.Format("String_{0}", count - (i * 2)));
}

// Zeit messen
Stopwatch watch = new Stopwatch();
watch.Start();

// Result List
List<string> results = new List<string>();
int iterations = 0;

foreach (var s1 in source1)
{
   foreach (var s2 in source2)
   {
      iterations++;
      if (s1 == s2)
      {
         results.Add(s1);
      }
   }
}

// Fertig
watch.Stop();
Console.WriteLine("Itarations: {0}", iterations);
Console.WriteLine("Found matches: {0}", results.Count);
Console.WriteLine("Duration: {0}", watch.ElapsedMilliseconds);

Da beide Listen verschachtelt durchlaufen werden ergibt sich bei 40.000 Werten pro Liste die unglaubliche Menge von 1,600,000,000 Iterationen! Bei meinem Test brauchte dieser Source-Code 40 Sekunden um die beiden Listen miteinander zu vergleichen.

Innere Schleife mit "break" verlassen
Die erste, sehr einfache Möglichkeit die Aktion zu beschleunigen ist, wenn ein Wert gefunden wurde, die innere Schleife über "break" zu verlassen:
// Zwei Beispiel-Sourcen
int count = 40000;
List<string> source1 = new List<string>(count);
List<string> source2 = new List<string>(count);

// Jeweils mit 40000 Einträgen füllen
for (int i = 0; i < count; i++)
{
   source1.Add(string.Format("String_{0}", i));
   source2.Add(string.Format("String_{0}", count - (i * 2)));
}

// Zeit messen
Stopwatch watch = new Stopwatch();
watch.Start();

// Result List
List<string> results = new List<string>();
int iterations = 0;

foreach (var s1 in source1)
{
   foreach (var s2 in source2)
   {
      iterations++;
      if (s1 == s2)
      {
         results.Add(s1);
         // Aufhören wenn der Wert gefunden wurde
         break;
      }
   }
}

// Fertig
watch.Stop();
Console.WriteLine("Itarations: {0}", iterations);
Console.WriteLine("Found matches: {0}", results.Count);
Console.WriteLine("Duration: {0}", watch.ElapsedMilliseconds);

Hierbei reduziert sich die Menge der Iterationen bereits auf "nur noch" 1.000.030.000 und die Laufzeit auf 25 Sekunden.

.NET 3.5 HashSet<T>
Der wirklich korrekt Ansatz ist jedoch, die verschachtelte Schleife komplett aufzulösen. Hierfür kann seit .NET 3.0 ein HashSet und LINQ verwendet werden.
// Zwei Beispiel-Sourcen
int count = 40000;
List<string> source1 = new List<string>(count);
List<string> source2 = new List<string>(count);

// Jeweils mit 40000 Einträgen füllen
for (int i = 0; i < count; i++)
{
   source1.Add(string.Format("String_{0}", i));
   source2.Add(string.Format("String_{0}", count - (i * 2)));
}

// Zeit messen
Stopwatch watch = new Stopwatch();
watch.Start();

// Result List
List<string> results = new List<string>();
// Alle Werte aus source1 in ein HashSet
HashSet<string> set1 = new HashSet<string>(source1);

// Alle Werte aus source2 welche in dem HashSet existieren holen
results.AddRange(
   from s in source2
   where set1.Contains(s)
   select s);

// Fertig
watch.Stop();
Console.WriteLine("Found matches: {0}", results.Count);
Console.WriteLine("Duration: {0}", watch.ElapsedMilliseconds);

Hält man sich an dieses Design so geht, bei der gleichen Aufgabe, die Anzahl der Iterationen auf gerademal 80,000 (einmal durch die erste Liste um das HashSet aufzubauen und einmal durch die zweite Liste um die Übereinstimmungen zu finden) zurück, woraus sich eine Laufzeit von 11 Millisekunden ergibt.

.NET 2 Dictionary<T>
Da das HashSet nur ein Dictionary ohne Value-Liste ist und LINQ nichts anderes als eine einfache "foreach"-Schleife abbildet kann das gleiche Prinzip natürlich auf sehr einfach auf .NET 2.0 angewandt werden:
// Zwei Beispiel-Sourcen
int count = 40000;
List<string> source1 = new List<string>(count);
List<string> source2 = new List<string>(count);

// Jeweils mit 40000 Einträgen füllen
for (int i = 0; i < count; i++)
{
   source1.Add(string.Format("String_{0}", i));
   source2.Add(string.Format("String_{0}", count - (i * 2)));
}

// Zeit messen
Stopwatch watch = new Stopwatch();
watch.Start();

// Result List
List<string> results = new List<string>();
// Alle Werte aus source1 in ein Dictionary
Dictionary<string, string> dict = new Dictionary<string, string>(source1.Count);
foreach (string s in source1)
{
   dict.Add(s, s);
}

// Alle Werte aus source2, welche in dem Dictionary existieren, holen
foreach (string s2 in source2)
{
   if (dict.ContainsKey(s2))
      results.Add(s2);
}

// Fertig
watch.Stop();
Console.WriteLine("Found matches: {0}", results.Count);
Console.WriteLine("Duration: {0}", watch.ElapsedMilliseconds);

Die Laufzeit ist hierbei äquivalent zu der des HashSets in Verbindung mit LINQ.

Ergebnis
Das Thema mag für routinierte Backend Entwickler selbstverständlich sein, ist jedoch ein Fehler der immer und immer wieder gemacht wird.

Der Vergleich von 40.000 Werten mag hier groß erscheinen. Diese Probleme treten jedoch durchaus recht häufig auf. Vielleicht mit weniger zu vergleichenden Werten, allerdings kann es sein dass die Methoden wesentlich öfter als einmal (wie in unserem Beispiel) aufgerufen werden.

(Mein allererster Blog :-) )

4 comments:

  1. Hallo Florian

    Danke für dein Blogeintrag, hat mir sehr geholfen bei meinem Problem.

    ReplyDelete
    Replies
    1. Hi Daniel

      Danke dir für dein Feedback!
      (Und sorry für die späte Antwort...)

      Grüße
      Flo

      Delete
  2. Hallo Florian,

    ersteinmal danke für den Blogeintrag. Mir stellt sich nur eine Frage, ich beziehe mich auf deinen .Net2 Teil.
    Warum machst du aus Liste Source1 ein dictionary mit Key und Value Listeneintrag?
    Ginge nicht auch in der Bedingung der foreach schleife:
    27 foreach (string s2 in source2)
    28 {
    29 if (source1.Contains(s2))
    30 results.Add(s2);
    31 }

    Also wo liegt der Nachteil darin? so würde man sich doch das Dictionary sparen, oder?

    PS: Bin leider erst jetzt auf so ein Problem gestoßen, deshalb die späte Frage.

    ReplyDelete
    Replies
    1. Hallo Alexander

      List.Contains entspricht einer "versteckten" Version von "Innere Schleife mit 'break' verlassen" führen. Eine Liste ist nicht sortiert und nicht indiziert. Jeder Aufruf von "Contains" endet innerhalb der Liste zu einer Schleife über alle Elemente, bis ein passendes gefunden wurde. Du bleibst also bei einem Aufwand von O(n). Da Contains intern direkten Zugriff auf den Array-Buffer der List hat wird die Range-Check-Elimination zu einer besseren Performance führen als das Beispiel hier, aber es bleibt bei einem Partial- bis Full-Scann.

      Das Dictionary sorgt dafür, dass source1 nur einmal durchlaufen werden muss um das Dictionary aufzubauen. Danach verwenden alle aufrufe von dict.Contains den im Dictionary enthaltenen Hash-Index, was in Aufwand annähernd O(1) entspricht.

      Hoffe das hilf.
      Flo

      Delete