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