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