Ich habe;Raumkomplexität einer einfachen Linq (zu Objekten) Abfrage
var maxVal = l.TakeWhile(x=>x < val).Where(x=>Matches(x)).Max();
Wie viel Platz braucht das? Erstellt Linq eine Liste der oben genannten Where() - Bedingung, oder ist Max() nur durch das IEnumerable iterierend, um zu verfolgen, was der aktuelle Max() ist?
Und wo kann ich weitere Informationen über diese finden, außer fragen auf SO f
ich mit Reflektor überprüft haben, dass jeder von Enumerable.TakeWhile, Enumerable.Where und Enumerable.Max in konstanten Raum laufen. Daher sollte diese gesamte Abfrage in konstantem Speicherplatz ausgeführt werden. Nicht überraschend, wenn man TakeWhile und Where in Betracht zieht, um verzögerte Ausführung + Streaming zu verwenden. Max verwendet keine verzögerte Ausführung, sondern muss nur 'max so weit' und den Enumerator im Quell-Enumerable speichern.
Nach der ReflectorMax() Methode durchläuft die Aufzählung.
Und wo kann ich weitere Informationen über diese finden, außer fragen auf SO f
Sie Reflector bei der Umsetzung einer .NET-Assembly suchen verwenden können.
Reflector ist dein Freund.
Insbesondere können Sie die Linq to Objects-Erweiterungsmethoden in der Enumerable-Klasse in System.Linq betrachten.
Die oben genannten verwenden Iterationen, also verwenden sie den beliebigen Platz, den die Enumeratoren einnehmen - normalerweise O (1). Max() ist O (1) Raum.
Bedenken Sie jedoch, dass nichts einen Entwickler davon abhält, einen Enumerator zu schreiben, der mehr als konstanten Platz einnimmt. Z.B. Durchqueren eines Baumes kann O (log n) Raum erfordern. Dies ist z.B. für SortedDictionary<K,V> und SortedSet<K,V>.
So hängt es teilweise davon ab, was l in Ihrem Code ist.
Das einzige, was von Enumerable angeboten wird, das ich nicht in konstantem Raum ausgeführt habe, ist ToList(), aus offensichtlichen Gründen. Bei einigen Aufzählungen ist dies ineffizient, da Sie bereits eine Raumkomplexität über der Konstanten (normalerweise O (n) beim Speichern der Elemente) haben und die betreffende Sammlung einen Mechanismus mit geringerer zeitlicher Komplexität bietet. Wenn Sie eine solche Sammlung selbst erstellen, bietet es sich an, eigene Versionen der von Enumerable angebotenen Erweiterungen anzubieten. Zum Beispiel, wenn Sie eine Sammlung haben, die inhärent sortiert ist, sollten Sie in der Lage sein, Min() und Max() in besser als O (n) Komplexität anzubieten (ob es O (1), O (ln) oder etwas anderes wäre hängt davon ab, auf welche Weise diese Sortierung beibehalten wurde). Da Instanzmethoden Erweiterungsmethoden überschreiben (wenn ein Ausdruck des Objekttyps anstelle des Instanztyps aufgerufen wird), ohne dass ein Unterschied zu dem Coder besteht, der Ihr Objekt verwendet, bieten Sie eine bessere Effizienz.
ToArray(), ToList(), ToDictionary(), ToLookup(), OrderBy(), OrderByDescending(), GroupBy(), Distinct() funktionieren meines Wissens nicht in konstantem Speicherplatz. Es kann mehr geben. Sie haben recht über die Effizienz Bit obwohl; Ich würde SortedList.Values.Max() nicht aufrufen, aber wer weiß, welche Optimierungen MS in Zukunft einfügen wird. – Ani
Gah! Ja, die, die du erwähnst, sind alle über konstantem Raum, sie waren mir beim Kommentieren nur in den Sinn gekommen. Eine bereits eingeführte Optimierung besteht darin, dass Count() prüft, ob die Aufzählung eine ICollection ist, und wenn dies der Fall ist, gibt sie den Wert ihrer Count-Eigenschaft zurück. –
Es ist sinnvoll, dass Max keine verzögerte Ausführung verwendet, da es ein T nicht IEnumerable zurückgibt. Eine andere Art zu betrachten ist, dass keiner von ihnen wirklich verzögerte Ausführung; Sie alle geben sofort ein Objekt zurück, das sich beim Aufzählen unterschiedlich verhält.Das Ergebnis von Max() wird jedoch nicht aufgezählt. Während dies die meiste Zeit nicht die beste Art ist, über Dinge nachzudenken, kann es helfen, wenn man versucht, sich zu erinnern, was verzögert wird oder nicht. –