English Version

Terminator T1000

Ihr kennt ja den Aschenputtel-Spruch “Die Guten ins Töpfchen, die Schlechten ins Kröpfchen.”?

Naja, .NET Linq hat eine Lösung für das Eine oder Andere, genannt Where(). Wenn man das benutzt, sieht die Lösung wahrscheinlich so aus:

var evens = list.Where(number => ((number % 2) == 0));
var odds =  list.Where(number => ((number % 2) != 0));

Aber es gibt keine Lösung für Beides. Also hab ich mir selbst eine geschrieben:

public static void Split<T>(this IEnumerable<T> source
    , Func<T, Boolean> predicate
    , out IEnumerable<T> trueList
    , out IEnumerable<T> falseList)
{
    trueList = source.Where(predicate);
    falseList = source.Except(trueList);
}

Die Performance dieser beiden Versionen ist genau gleich. Auf eine Liste, welche die Nummern 1…6 enthält, wird 12 mal zugegriffen (sechs mal um gegen gerade zu prüfen, sechs mal für ungerade). Nur der Zeitpunkt der Ausführung ändert sich minimal.

Um zu verstehen, was tatsächlich passiert, habe ich mir eine Klasse “Number” geschrieben, welche einen simplen Integer enthält. Aber der Getter loggt jeden Lesezugriff und ein statisches Feld zählt die insgesamten Zugriffe über alle Instanzen hinweg.

Der Output der Where()-Funktion ist dann so:

Starting Where

Printing evens
evens.GetType(): System.Linq.Enumerable+WhereListIterator`1[LinqSplit.Number]
Access #1. Number: 1
Access #2. Number: 2
2
Access #3. Number: 3
Access #4. Number: 4
4
Access #5. Number: 5
Access #6. Number: 6
6

Printing odds
odds.GetType(): System.Linq.Enumerable+WhereListIterator`1[LinqSplit.Number]
Access #7. Number: 1
1
Access #8. Number: 2
Access #9. Number: 3
3
Access #10. Number: 4
Access #11. Number: 5
5
Access #12. Number: 6

Finishing Where

Die Benutzung der Except()-Funktion auf der Liste, welche die geraden Zahlen als Ausfilterungskriterum benutzt, resultiert in diesem Output:

Starting Split

Printing evens
evens.GetType(): System.Linq.Enumerable+WhereListIterator`1[LinqSplit.Number]
Access #1. Number: 1
Access #2. Number: 2
2
Access #3. Number: 3
Access #4. Number: 4
4
Access #5. Number: 5
Access #6. Number: 6
6

Printing odds
odds.GetType(): System.Linq.Enumerable+d__92`1[LinqSplit.Number]
Access #7. Number: 1
Access #8. Number: 2
Access #9. Number: 3
Access #10. Number: 4
Access #11. Number: 5
Access #12. Number: 6
1
3
5

Finishing Split

Der Code hier oben hält sich komplett an das Linq-Konzept der verzögerten Ausführung (deferred / delayed execution). Der Code wird erst wirklich durchlaufen, wenn jemand eine Iteration über den Rückgabewert startet.

Es gibt aber auch Wege, die Performance zu verbessern. Wenn man zum Beispiel die Anzahl der Listelemente benötigt bevor man tatsächlich darüber iteriert, dann ist es eine schlechte Idee, erst Count() aufzurufen und dann die Iteration zu starten. Denn Count() macht genaz das Gleiche und am Ende hat man dann zweimal iteriert.

Deshalb ist es stilistisch ein guter Ansatz, die Iteration zu forcieren und das Ergebnis in eine List zu packen. Dann kann man die Count-Eigenschaft abfragen und so oft wie man will über die List iterieren.

Die Split()-Funktion kann auf ähnliche Weise verbessert werden, insbesondere wenn man die verzögerte Ausführung nicht wirklich benötigt. Man cacht einfach die Ergebnisse der Where()-Funktion in einer List und benutzt sie erst dann als Eingangsparameter für die Except()-Funktion und als Rückgabewert:

public static void SplitOptimized1<T>(this IEnumerable<T> source
    , Func<T, Boolean> predicate
    , out IEnumerable<T> trueList
    , out IEnumerable<T> falseList)
{
    trueList = source.Where(predicate).ToList();
    falseList = source.Except(trueList);
}

Wie man sehen kann, hat sich die Methodensignatur nicht wirklich geändert, denn List ist ein IEnumerable. Ich habe mich lediglich dazu entschieden, den Code sofort auszuführen. Das Ergebnis ist das:

Starting SplitOptimized1
Access #1. Number: 1
Access #2. Number: 2
Access #3. Number: 3
Access #4. Number: 4
Access #5. Number: 5
Access #6. Number: 6

Printing evens
evens.GetType(): System.Collections.Generic.List`1[LinqSplit.Number]
2
4
6

Printing odds
odds.GetType(): System.Linq.Enumerable+d__92`1[LinqSplit.Number]
1
3
5

Finishing SplitOptimized1

Wie man sehen kann, hat sich durch diese einfache Optimierung die Anzahl der Lesezugriffe auf die tatsächlichen Daten halbiert.

Nun könnte man aber argumentieren “Wenn man die verzögerte Ausführen weglässt, dann sei konsequent” und man hätte recht. Wenn man also diesen Weg nimmt, dann sollte man das auch in der Methodensigantur klar machen:

public static void SplitOptimized1<T>(this IEnumerable<T> source
    , Func<T, Boolean> predicate
    , out List<T> trueList
    , out IEnumerable<T> falseList)
{
    trueList = source.Where(predicate).ToList();
    falseList = source.Except(trueList);
}
public static void SplitOptimized2<T>(this IEnumerable<T> source
    , Func<T, Boolean> predicate
    , out List<T> trueList
    , out List<T> falseList)
{
    trueList = source.Where(predicate).ToList();
    falseList = source.Except(trueList).ToList();
}

Wie man sehen kann, habe ich auch den zweiten Output zur List gemacht, um es unmisverständlich klar zu machen, dass hier keine verzögerte Ausführung zur Anwendung kommt. Diese letzte Änderung hat allerdings keinen weiteren Performanceeinfluss auf die Lesezugriffe:

Starting SplitOptimized2
Access #1. Number: 1
Access #2. Number: 2
Access #3. Number: 3
Access #4. Number: 4
Access #5. Number: 5
Access #6. Number: 6

Printing evens
evens.GetType(): System.Collections.Generic.List`1[LinqSplit.Number]
2
4
6

Printing odds
odds.GetType(): System.Collections.Generic.List`1[LinqSplit.Number]
1
3
5

Finishing SplitOptimized2

Die Quelldateien können hier gefunden werden: LinqSplit.zip