Hier ist meine Implementierung von merge sort in Scala:
%Vor%Es funktioniert korrekt und es scheint asymptotisch ist es auch gut, aber es ist viel langsamer (ca. 10 mal) als Java-Implementierung von hier Ссылка und verwendet viel Speicher. Gibt es eine schnellere Implementierung von merge sort, die funktional ist? Natürlich ist es möglich, Java-Version Zeile für Zeile zu portieren, aber das ist nicht das, wonach ich suche.
UPD: Ich habe Stream in List und #:: in :: geändert und die Sortierroutine wurde schneller, nur drei bis vier Mal langsamer als die Java-Version. Aber ich verstehe nicht warum stürzt es nicht mit Stack Overflow ab? merge ist nicht tail-rekursiv, alle Argumente werden streng ausgewertet ... wie ist das möglich?
Sie haben mehrere Fragen gestellt. Ich versuche, sie in einer logischen Reihenfolge zu beantworten:
In der Stream-Version verwenden Sie #:: merge(...) in der Funktion merge . Normalerweise wäre dies ein rekursiver Aufruf und könnte zu einem Stapelüberlauf für genügend große Eingabedaten führen. Aber nicht in diesem Fall. Der Operator #::(a,b) wird in class ConsWrapper[A] implementiert (es gibt eine implizite Konvertierung) und ist ein Synonym für cons.apply[A](hd: A, tl: ⇒ Stream[A]): Cons[A] . Wie Sie sehen können, ist das zweite Argument Anruf nach Name, was bedeutet, dass es lazy ausgewertet wird.
Das bedeutet, dass merge ein neu erstelltes Objekt vom Typ cons zurückgibt, das schließlich wieder zusammenführen wird. Mit anderen Worten: Die Rekursion passiert nicht auf dem Stack, sondern auf dem Heap. Und normalerweise haben Sie viel Heap.
Die Verwendung des Heaps für die Rekursion ist eine gute Methode, um sehr tiefe Rekursionen zu behandeln. Aber es ist viel langsamer als der Stapel. Also hast du die Geschwindigkeit für die Rekursionstiefe getauscht. Dies ist der Hauptgrund, warum Stream so langsam ist.
Der zweite Grund ist, dass Scala, um die Länge von Stream zu erhalten, das gesamte Stream materialisieren muss. Aber beim Sortieren der Stream müsste es sowieso jedes Element materialisieren, also tut das nicht sehr weh.
Wenn Sie Stream for List ändern, verwenden Sie tatsächlich den Stapel für die Rekursion. Jetzt könnte ein Stack Overflow passieren. Bei der Sortierung haben Sie jedoch normalerweise eine Rekursionstiefe von log(size) , normalerweise den Logarithmus der Basis 2 . Um also 4 Milliarden Eingabefelder zu sortieren, benötigen Sie etwa 32 Stack-Frames. Bei einer Standard-Stack-Größe von mindestens 320k (unter Windows haben andere Systeme größere Standardwerte), bleibt damit Platz für viele Rekursionen und damit für eine Menge zu sortierender Eingabedaten.
Es kommt darauf an: -)
Sie sollten den Stapel und nicht den Heap für die Rekursion verwenden. Und Sie sollten Ihre Strategie abhängig von den Eingabedaten entscheiden:
Verwende keinen Swap und benutze deine Caches. Verwenden Sie veränderbare Datenstrukturen, wenn Sie können und an Ort und Stelle sortieren. Ich denke, dass funktionelles und schnelles Sortieren nicht sehr gut zusammen funktioniert. Um die Sortierung wirklich schnell zu machen, müssen Sie Stateful-Operationen (z. B. In-Place-Mergesort auf veränderbaren Arrays) verwenden.
Normalerweise probiere ich das bei allen meinen Programmen aus: Benutze möglichst reinen funktionalen Stil, benutze aber stateful operations für kleine Teile, wenn machbar (zB weil es bessere Performance hat oder der Code nur mit vielen Zuständen umgehen muss und viel wird besser lesbar, wenn ich var s anstelle von val s) verwende.
Hier sind einige Dinge zu beachten.
Zuerst berücksichtigen Sie nicht, dass der ursprüngliche Stream so sortiert wird, dass er leer ist. Sie können dies beheben, indem Sie die anfängliche Überprüfung in sort ändern, um if(xs.length <= 1) xs zu lesen.
Zweitens können Streams unkalkulierbare Längen haben (zB Strem.from(1) ), was ein Problem darstellt, wenn Sie versuchen, die Hälfte dieser (möglicherweise unendlichen) Länge zu berechnen - Sie könnten eine Überprüfung dafür mit hasDefiniteSize oder in Erwägung ziehen ähnlich (obwohl naiv verwendet, könnte dies einige ansonsten berechenbare Ströme herausfiltern).
Schließlich kann die Tatsache, dass dies definiert ist, um mit Streams zu arbeiten, sein, was es verlangsamt. Ich habe versucht, eine große Anzahl von Läufen Ihrer Stream-Version von mergesort im Vergleich zu einer Version zu schreiben, die in Prozesslisten geschrieben wurde, und die Listenversion kam ungefähr dreimal schneller heraus (zugegebenermaßen nur für ein einziges Paar von Läufen). Dies deutet darauf hin, dass Streams auf diese Weise weniger effizient arbeiten als Listen oder andere Sequenztypen (Vector ist möglicherweise noch schneller oder verwendet Arrays gemäß der referenzierten Java-Lösung).
Das heißt, ich bin kein großer Experte für Timings und Effizienz, so dass jemand anders in der Lage sein kann, eine sachkundigere Antwort zu geben.
Ihre Implementierung ist eine Top-Down-Merge-Sortierung. Ich finde, dass eine Bottom-Up-Merge-Sortierung schneller ist und mit List.sorted vergleichbar ist (für meine Testfälle zufällig ausgewählte Listen von Zufallszahlen).