Ich versuche eine Funktion zu schreiben, die aufeinanderfolgende Duplikate aus einer seq<'a> herausfiltert, wie durch eine gegebene Gleichheitsfunktion bestimmt, aber mit einer Wendung: Ich brauche das letzte Duplikat aus einem Durchlauf von Duplikate, um es in die resultierende Sequenz zu bringen. Wenn ich zum Beispiel eine Sequenz [("a", 1); ("b", 2); ("b", 3); ("b", 4); ("c", 5)] habe und ich fun ((x1, y1),(x2, y2)) -> x1=x2 verwende, um nach Gleichheit zu suchen, ist das Ergebnis, das ich sehen möchte, [("a", 1); ("b", 4); ("c", 5)] . Der Punkt dieser Funktion ist, dass ich Datenpunkte reinkomme, wo manchmal Datenpunkte legitim den gleichen Zeitstempel haben, aber ich interessiere mich nur für den letzten, also möchte ich die vorhergehenden mit demselben Zeitstempel wegwerfen. Die Funktion, die ich implementiert habe, ist wie folgt:
In Bezug auf die eigentliche Arbeit funktioniert es:
%Vor%In Bezug auf die Leistung ist es jedoch ein Desaster:
%Vor%Klar mache ich hier etwas sehr dumm, aber ich kann nicht sehen, was es ist. Woher kommt der Performance-Hit? Mir ist klar, dass es bessere Implementierungen gibt, aber ich bin speziell daran interessiert zu verstehen, warum diese Implementierung so langsam ist.
EDIT: FYI, hat es geschafft, eine anständige Implementierung im funktionalen Stil zu finden, der nur auf Seq. -Funktionen beruht. Die Leistung ist in Ordnung und benötigt etwa das 1,6-fache der imperativ-ähnlichen Implementierung von @gradbot darunter, das Iteratoren verwendet. Es scheint, dass die Wurzel des Problems die Verwendung von Seq.head und Seq.tail in rekursiven Aufrufen in meiner ursprünglichen Anstrengung ist.
Das Leistungsproblem stammt von den verschachtelten Aufrufen von Seq.tail. Hier ist der Quellcode zu Seq.tail
%Vor% Wenn Sie Seq.tail(Seq.tail(Seq.tail(...))) aufrufen, hat der Compiler keine Möglichkeit, die von GetEnumerator() erzeugten Enumeratoren zu optimieren. Nachfolgende zurückgegebene Elemente müssen jede verschachtelte Sequenz und Enumerator durchlaufen. Dies führt dazu, dass jedes zurückgegebene Element durch alle zuvor erzeugten Sequenzen hochkullieren muss und alle diese Sequenzen ihren internen Zustand ebenfalls erhöhen müssen. Das Nettoergebnis ist eine Laufzeit von O (n ^ 2) anstelle von linearem O (n).
Leider gibt es momentan keine Möglichkeit, dies in einem funktionalen Stil in F # darzustellen. Sie können mit einer Liste (x :: xs) aber nicht für eine Sequenz. Bis die Sprache die native Unterstützung für Sequenzen verbessert, verwenden Sie Seq.tail nicht in rekursiven Funktionen.
Durch die Verwendung eines einzelnen Enumerators wird das Leistungsproblem behoben.
%Vor%Die erste Version dieser Antwort hat eine rekursive Version des obigen Codes ohne Mutation.
Das Problem besteht darin, wie Sie Sequenzen verwenden. All diese Renditen, Köpfe und Schwänze spinnen ein Netz von Iteratoren, die von Iteratoren abzweigen, und wenn Sie es schließlich beim Aufruf von List.ofSeq materialisieren, durchlaufen Sie Ihre Eingabesequenz viel mehr als Sie sollten.
Jedes dieser Seq.heads nimmt nicht einfach das erste Element einer Sequenz - es nimmt das erste Element des Schwanzes einer Sequenz eines Schwanzes einer Sequenz eines Schwanzes einer Sequenz und so weiter.
Überprüfen Sie dies - es zählt die Zeiten, zu denen der Elementkonstruktor aufgerufen wird:
%Vor% Übrigens, wenn Sie nur Seqs auf Lists umschalten, wird es sofort ausgeführt.
Seq.isEmpty, Seq.head und Seq.tail sind langsam, weil sie alle eine neue Enumerator-Instanz erstellen, in die sie dann hineinruft. Sie enden mit einer Menge GC.
Im Allgemeinen sind Sequenzen nur vorwärts, und wenn Sie sie wie Mustervergleiche für Listen verwenden, wird die Performance wirklich schlecht.
Schauen Sie sich Ihren Code etwas an ... | None -> yield! s erstellt einen neuen Enumerator, obwohl wir wissen, dass s leer ist. Bei jedem rekursiven Aufruf wird wahrscheinlich ein neues IEnumerable erstellt, das dann von der Call-Site mit yield! In einen Enumerator umgewandelt wird.
Wie die anderen Antworten schon sagten, sind seq wirklich langsam. Die eigentliche Frage ist jedoch, warum Sie hier ein seq verwenden möchten. Insbesondere beginnen Sie mit einer Liste und Sie möchten die gesamte Liste durchlaufen und am Ende eine neue Liste erstellen. Es scheint keinen Grund zu geben, eine Sequenz zu verwenden, außer Sie möchten sequenzspezifische Funktionen verwenden. In der Tat geben die Dokumente Folgendes an (Hervorhebung von mir):
Eine Sequenz ist eine logische Reihe von Elementen eines Typs. Sequenzen sind besonders nützlich, wenn Sie eine große, geordnete Sammlung von Daten haben, aber nicht unbedingt erwarten, alle Elemente zu verwenden . Einzelne Sequenzelemente werden nur nach Bedarf berechnet, sodass eine Sequenz in Situationen, in denen nicht alle Elemente verwendet werden, eine bessere Leistung bietet als eine Liste.
Um den Eingabetyp Seq effizient zu nutzen, sollte man jedes Element nur einmal durchlaufen und vermeiden, zusätzliche Sequenzen zu erzeugen.
Um andererseits den Ausgabetyp List effizient zu nutzen, sollte man großzügig die Funktionen cons und tail verwenden, die beide im Prinzip frei sind.
Die Kombination der beiden Anforderungen führt mich zu dieser Lösung:
%Vor% Beachten Sie jedoch, dass die ausgegebene Liste in umgekehrter Reihenfolge liegt, weil die Liste vorangestellt ist. Ich hoffe, das ist kein Dealbreaker, da List.rev eine relativ teure Operation ist.
Test:
%Vor%Hier ist ein ziemlich schneller Ansatz, der Bibliotheksfunktionen anstelle von Seq-Ausdrücken verwendet.
Ihr Test läuft in 0,007 Sekunden auf meinem PC.
Es hat einen ziemlich bösen Hack für das erste Element, das nicht brillant funktioniert und verbessert werden könnte.
%Vor%Tags und Links f# performance