Große O-Äquivalenz für LINQ select

10

Ich versuche festzustellen, ob sich die Big O-Äquivalenz einer verschachtelten Schleife ändert, wenn ich stattdessen eine LINQ-Auswahl verwende.

public void myFunc(List<Foo> fooList, List<Bar> barList)
{
    foreach(Foo foo in fooList)
    {
        foreach(Bar bar in barList)
        {
            if(foo.PropA == bar.PropA && bar.PropZ.HasValue)
                foo.PropC = foo.PropB * bar.PropZ;
        }
    }
}

Ich glaube, dieses Beispiel für eine verschachtelte Schleife ist aus Gründen der Komplexität O (n ^ 2).

Ich habe die verschachtelte Schleife durch eine LINQ-Auswahl wie folgt ersetzt:

public void myFunc(List<Foo> fooList, List<Bar> barList)
{
    foreach(Foo foo in fooList)
    {
        Bar bar = (from b in barList
                    where foo.PropA == b.PropA
                    select b).FirstOrDefault();

        if(bar.PropZ.HasValue)
            foo.PropC = foo.PropB * bar.PropZ;
    }
}

Wenn nichts anderes, scheint der Code ein wenig sauberer zu sein, da er ausdrücklich besagt: "Wir suchen nach diesem speziellen Code, mit dem wir Bararbeiten können."

Meine Frage lautet : Reduziert die Verwendung der LINQ-Auswahl die Big O-Komplexität?


quelle
3
Es wäre interessant, die vom Compiler erzeugte IL für jede dieser zu vergleichen.
Dan Pichelman
@ DanPichelman - Hör auf, mich zu schnüffeln! Ja, ich stimme zu, das wäre interessant herauszufinden. Sind sie gleichwertig oder nicht?
Könnte es einige Zeit sparen, bars zu durchlaufen und zuerst zu filtern bar.PropZ.HasValue, wenn Sie erwarten, dass mehr als eine winzige Menge als falsch ausgewertet wird? Beantwortet Ihre Frage nicht wirklich, ich überprüfe nur Ihren Code.
1
Tun diese beiden Schleifen überhaupt dasselbe, insbesondere in dem Fall, in dem dies foo.PropA == bar.PropAfür mehrere Einträge in gilt barList? Bearbeiten: definitiv nicht, da der zweite ein wirft, NullReferenceExceptionwenn die Auswahl zurückkehrt null.
Philip Kendall
1
Ich würde vermuten, .FirstOrDefault()dass die Linq-Schleife vorzeitig beendet wird, wenn eine Übereinstimmung gefunden wird, während Ihre dummen verschachtelten Schleifen nicht vorzeitig beendet werden. Ja, ich würde denken, dass Linq ein besseres Big-Oh hat. Aber ich bin mir nicht sicher, daher ein Kommentar und keine Antwort.
Mike Nakis

Antworten:

14

Big O ist das gleiche, da beide Codes (im schlimmsten Fall) einen Vergleich für jede Kombination von Elementen aus beiden Listen durchführen müssen. Wenn beispielsweise keine Übereinstimmungen zwischen den Listen vorhanden sind, muss durch keine Optimierung in der Linq-Implementierung nicht alle Elemente überprüft werden.

Aber hey, du willst doch nicht wirklich etwas über Big-O wissen, oder? Sie möchten wissen, ob der zweite schneller ist . Die Antwort lautet: Ja, die linq-basierte Lösung ist schneller (solange sie groß genug ist), da sie nur die Prüfung durchführen muss, bis die erste Übereinstimmung in der Liste gefunden wurde, während die verschachtelte Lösung immer alle Elemente besuchen muss . Die WhereMethode scannt nicht sofort die gesamte Liste, aber der Bewerter erstellt einen faulen Iterator. Die FirstOrDefaultMethode führt dann den Iterator aus, bis die erste Übereinstimmung gefunden ist, was bedeutet, dass im allgemeinen Fall nicht die gesamte Liste durchlaufen werden muss. Natürlich hat die Linq-Lösung einen gewissen Overhead. Wenn also n niedrig genug ist, ist die verschachtelte for-Schleife schneller.

Sie können die Quelle selbst überprüfen: https://github.com/dotnet/corefx/blob/master/src/System.Linq/src/System/Linq/Enumerable.cs

(Wenn Sie jedoch breakim ersten Beispiel ein a hinzufügen , sind die beiden Codes semantisch äquivalent, und der erste Code ist aufgrund des geringeren Overheads schneller.)

JacquesB
quelle
"Die Linq-basierte Lösung ist schneller" Wer weiß? LINQ hat einen Overhead mit konstantem Faktor, der leicht 2x überschreiten kann.
usr
@usr: Sie haben Recht, es hängt eher von der Häufigkeit der Übereinstimmungen als von der Größe der Listen ab. Je häufiger Übereinstimmungen auftreten, desto größer ist der relative Vorteil der linq-basierten Lösung.
JacquesB
5

Kein Unterschied in der Komplexität, beide sind O (n²), weil Linqs Wo ist O (n).
Die Verwendung von FirstOrDefault entspricht dazu:

if(foo.PropA == bar.PropA && bar.PropZ.HasValue) 
{
    foo.PropC = foo.PropB * bar.PropZ;
    break;
}

Dies ist eine Verbesserung der Berechnungszeit, jedoch nicht der Komplexität.

Sie können es besser machen, indem Sie eine Hashmap für eine der beiden Listen verwenden.
Der Join- Operator von Linq erstellt eine Hashmap für eine der beiden Listen, sodass Sie bei der Suche nach zwei übereinstimmenden Elementen an Leistung gewinnen:

    public void myFunc(List<Foo> fooList, List<Bar> barList)
    {
        var rows = fooList.Join(
                        barList, 
                        f => f.PropA, 
                        b => b.PropA, 
                        (f, b) => new { Foo = f, Bar = b }
                   );

        foreach (var row in rows)
        {
            if (row.Bar.PropZ.HasValue)
                row.Foo.PropC = row.Foo.PropB * row.Bar.PropZ.Value;
        }
    }

Dies sollte in O (n log (n)) ausgeführt werden.

Cyril Gandon
quelle
Können Sie erklären, warum O (n log (n)) ausgeführt wird? Nach dem Quellcode scheint es ein zu erstellen Lookup(Of TKey, TElement), zu iterieren barList, das Groupingfür jedes Element abzurufen und Elemente zum hinzuzufügen Grouping. Es iteriert dann über fooList, erhält das Groupingund gibt jedes Element in der Gruppierung zurück. Woher kommt das `log (n)?
Zach Mierzejewski