Weiß jemand, was die schlimmstmögliche asymptotische Verlangsamung ist, die bei rein funktioneller Programmierung im Gegensatz zu Imperativ (d. h. Zulassen von Nebenwirkungen) auftreten kann?
Klärung aus Kommentar von itowlson : Gibt es ein Problem, bei dem der bekannteste nicht-destruktive Algorithmus asymptotisch schlechter ist als der bekannteste destruktive Algorithmus, und wenn ja, um wie viel?
Nach Pippenger [1996] , wenn man ein Lisp-System, das rein funktional ist (und eine strenge Evaluierungssemantik hat, nicht faul ist) mit einem, das Daten mutieren kann, vergleicht, kann ein für das unreine Lisp geschriebener Algorithmus, der in O läuft ( n ) in einen Algorithmus im reinen Lisp übersetzt werden, der in O ( n log n ) Zeit läuft (basierend auf der Arbeit von Ben-Amram und Galil [1992] über die Simulation von Direktzugriffsspeichern mit Hilfe von Zeigern. Pippenger stellt auch fest, dass es Algorithmen gibt, für die das das Beste ist, was Sie tun können; Es gibt Probleme, die O ( n ) im unreinen System sind, die Ω ( n log n ) im reinen System sind.
>Es gibt ein paar Vorbehalte gegen dieses Papier. Das wichtigste ist, dass es sich nicht um faule funktionale Sprachen wie Haskell handelt. Bird, Jones und De Moor [1997] < Zeigen Sie, dass das von Pippenger konstruierte Problem in einer faulen funktionalen Sprache in O ( n ) Zeit gelöst werden kann, aber nicht (und soweit ich weiß, niemand hat), ob oder nicht eine faule funktionale Sprache kann alle Probleme in der gleichen asymptotischen Laufzeit als eine Sprache mit Mutation lösen.
Das von Pippenger konstruierte Problem erfordert, dass Ω ( n log n ) speziell konstruiert wird, um dieses Ergebnis zu erzielen, und nicht notwendigerweise repräsentativ für praktische, reale Probleme ist. Es gibt ein paar Einschränkungen für das Problem, die ein wenig unerwartet sind, aber notwendig sind, damit der Beweis funktioniert. Insbesondere erfordert das Problem, dass die Ergebnisse online berechnet werden, ohne auf zukünftige Eingaben zugreifen zu können, und dass die Eingabe aus einer Folge von Atomen aus einem unbegrenzten Satz möglicher Atome und nicht aus einer festen Größenmenge besteht. Und das Papier erstellt nur (untere Grenze) Ergebnisse für einen unreinen Algorithmus der linearen Laufzeit; Für Probleme, die eine längere Laufzeit erfordern, ist es möglich, dass der zusätzliche O (log n ) Faktor, der in dem linearen Problem gesehen wird, in dem Prozess zusätzlicher Operationen, die für Algorithmen notwendig sind, "absorbiert" werden kann mit längeren Laufzeiten. Diese Klarstellungen und offenen Fragen werden kurz von Ben-Amram [1996] behandelt.
In der Praxis können viele Algorithmen in einer reinen funktionalen Sprache mit derselben Effizienz implementiert werden wie in einer Sprache mit veränderbaren Datenstrukturen. Eine gute Referenz zu Techniken, die für die effiziente Implementierung rein funktionaler Datenstrukturen verwendet werden, finden Sie in Chris Okasakis "Reinfunktionalen Datenstrukturen" [Okasaki 1998 ] (das ist eine erweiterte Version seiner Doktorarbeit [Okasaki 1996] ) .
Wer auf rein funktionalen Datenstrukturen Algorithmen implementieren will, sollte Okasaki lesen. Sie können immer eine O (log n ) Verlangsamung pro Operation erreichen, indem Sie veränderbaren Speicher mit einem ausgeglichenen binären Baum simulieren, aber in vielen Fällen können Sie wesentlich besser machen, und Okasaki beschreibt viele nützliche Techniken Von amortisierten Techniken zu Echtzeit-Techniken, die die amortisierte Arbeit schrittweise durchführen. Rein funktionale Datenstrukturen können ein wenig schwierig zu handhaben und zu analysieren sein, aber sie bieten viele Vorteile wie referenzielle Transparenz, die bei der Compileroptimierung, beim parallelen und verteilten Rechnen und bei der Implementierung von Features wie Versionierung, Rückgängigmachen und Zurücksetzen hilfreich sind / p>
Beachten Sie auch, dass all dies nur asymptotische Laufzeiten behandelt. Viele Techniken zur Implementierung rein funktionaler Datenstrukturen geben Ihnen eine gewisse Menge an konstanter Faktorabschwächung, aufgrund der zusätzlichen Buchhaltung, die notwendig ist, damit sie funktionieren, und Implementierungsdetails der fraglichen Sprache. Die Vorteile rein funktionaler Datenstrukturen können diese Verlangsamungen durch konstante Faktoren aufwiegen. Daher müssen Sie in der Regel Kompromisse basierend auf dem jeweiligen Problem eingehen.
Es gibt tatsächlich mehrere Algorithmen und Datenstrukturen, für die keine asymptotisch effiziente rein funktionale Lösung (t.i. eine in reinem Lambda-Kalkül implementierbare) bekannt ist, selbst mit Faulheit.
Wir nehmen jedoch an, dass in "imperativen" Sprachen der Zugriff auf den Speicher O (1) ist, während dies in der Theorie nicht so asymptotisch sein kann (dh für unbegrenzte Problemgrößen) und der Zugriff auf Speicher innerhalb eines riesigen Datensatzes immer O ( log n), das in einer funktionalen Sprache emuliert werden kann.
Wir müssen uns auch daran erinnern, dass tatsächlich alle modernen funktionalen Sprachen veränderbare Daten liefern, und Haskell liefert sogar, ohne auf Reinheit zu verzichten (die ST-Monade).
Dieser Artikel behauptet, dass die bekannten rein funktionalen Implementierungen von der Union-find-Algorithmus haben alle eine schlechtere asymptotische Komplexität als die, die sie veröffentlichen, die eine rein funktionale Schnittstelle hat, aber intern veränderliche Daten verwendet.
Die Tatsache, dass andere Antworten behaupten, dass es keinen Unterschied geben kann und dass zum Beispiel der einzige "Nachteil" des rein funktionalen Codes darin besteht, dass er parallelisiert werden kann, gibt Ihnen eine Vorstellung von der Informiertheit / Objektivität der funktionalen Programmiergemeinschaft über diese Angelegenheiten.
BEARBEITEN:
Die folgenden Kommentare weisen darauf hin, dass eine voreingenommene Diskussion über die Vor- und Nachteile einer reinen funktionalen Programmierung möglicherweise nicht von der "funktionalen Programmiergemeinschaft" kommt. Guter Punkt. Vielleicht sind die Befürworter, die ich sehe, nur, um eine Bemerkung zu machen, "Analphabeten".
Ich denke zum Beispiel, dass dies blog post wird von jemandem geschrieben, der als Repräsentant der funktionalen Programmiergemeinschaft bezeichnet werden kann, und da es sich um eine Liste von "Punkten für eine faule Bewertung" handelt, wäre es ein guter Platz, um irgendwelche Nachteile zu erwähnen, die faule und rein funktionale Programmierung haben könnten . Ein guter Platz wäre anstelle der folgenden (technisch wahr, aber voreingenommen, um nicht lustig zu sein) Entlassung:
Wenn strict eine Funktion O (f (n)) -Komplexität in einer strikten Sprache hat, dann hat sie auch in fauler Sprache die Komplexität O (f (n)). Warum ärgern? :)
Bei einer festen Obergrenze für die Speichernutzung sollte kein Unterschied bestehen.
Proofskizze: Angesichts einer festen Obergrenze für die Speichernutzung sollte man in der Lage sein, eine virtuelle Maschine zu schreiben, die einen imperativen Befehlssatz mit der gleichen asymptotischen Komplexität ausführt, als ob Sie tatsächlich auf diesem Rechner ausgeführt würden. Dies ist so, weil Sie den veränderbaren Speicher als persistente Datenstruktur verwalten können, indem Sie O (log (n)) lesen und schreiben, aber mit einer festen Obergrenze für die Speichernutzung, können Sie eine feste Menge an Speicher haben, was diese verursacht Zerfall zu O (1). Daher kann die funktionale Implementierung die imperative Version sein, die in der funktionalen Implementierung der VM ausgeführt wird, und sollten daher beide die gleiche asymptotische Komplexität aufweisen.
Ich würde vorschlagen, auf Leistung von Haskell zu lesen und dann einen Blick darauf zu werfen bei Alioth Language Shootout Performances für funktionale Sprachen gegenüber prozeduralen / OO-Einsen.
"Funktional" ist eine Reihe von verschiedenen Funktionen, von denen jede unabhängig nützlich ist, und es ist nützlicher, sie einzeln zu betrachten.
Unveränderbarkeit
Nun, da ich damit vertraut bin, versuche ich jedes Mal, wenn ich ein unveränderliches Ergebnis zurückgeben kann, dies auch in einem objektorientierten Programm zu tun. Es ist einfacher, über das Programm nachzudenken, wenn Sie Werttypdaten haben.
Funktionen als erste Klasse
Wie auch immer Sie es nennen wollen, indem Sie Delegierten, Aktionen oder Funktionen herumreichen, ist eine sehr praktische Methode, um eine ganze Reihe von realen Problemen zu lösen, wie das "Loch im mittleren Muster".
Die Fähigkeit, Funktionen zu erstellen (zum Beispiel, Action in eine Aktion zu verwandeln, ist auch in einigen Szenarien sehr nützlich.
Wir sollten hier auch die Lambda-Syntax notieren, da Sie nur die Lambda-Syntax erhalten, wenn Sie Funktionen auf erstklassige Typen anwenden. Lambda-Syntax kann sehr ausdrucksvoll und prägnant sein.
Monaden
Dies ist ein subtiles, aber sehr mächtiges Konstrukt. Es ist so leistungsfähig wie das Yield-Schlüsselwort, das zum Erstellen von IEnumerable-Klassen in C # verwendet wird. Im Wesentlichen baut es eine Zustandsmaschine für Sie unter der Decke, aber Ihre Logik sieht linear aus.
Lazy Evaluation & amp; Rekursion
Ich füge diese zusammen, denn während sie immer als Features funktionaler Programmierung in den Vordergrund gerückt sind, haben sie ihren Weg so schnell in andere Imperativ-Sprachen gefunden, dass es schwer ist, sie als funktional zu bezeichnen.
S-Ausdrücke
Ich bin mir nicht sicher, wo ich das hinstellen soll, aber die Fähigkeit, den nicht kompilierten Code als Objekt zu behandeln (und zu inspizieren / zu modifizieren), wie Lisp S-Expressions oder LINQ Expressions, ist in einige Möglichkeiten, das leistungsfähigste Werkzeug der funktionalen Programmierung. Die meisten neuen "fließenden" .NET-Schnittstellen und DSLs verwenden eine Kombination aus Lambda-Syntax und LINQ-Ausdrücke, um einige sehr präzise APIs zu erstellen. Ganz zu schweigen von Linq2Sql / Linq2Nhibernate, wo Ihr C # -Code "magisch" als SQL statt als C # -Code ausgeführt wird.
Tags und Links algorithm performance functional-programming