Weiß jemand, was die schlimmstmögliche asymptotische Verlangsamung ist, die auftreten kann, wenn man rein funktional programmiert und nicht zwingend (d.h. Seiteneffekte zulässt)?
Erläuterung zum Kommentar von itowlson Gibt es ein Problem, für das der beste bekannte nicht-destruktive Algorithmus asymptotisch schlechter ist als der beste bekannte destruktive Algorithmus, und wenn ja, um wie viel?
Según Pippenger [1996] Wenn man ein rein funktionales Lisp-System (mit strikter Auswertungssemantik, nicht faul) mit einem System vergleicht, das Daten verändern kann, wird ein für das unreine Lisp geschriebener Algorithmus, der in O( n ) kann in einen Algorithmus in reinem Lisp übersetzt werden, der in O( n Protokoll n ) Zeit (basierend auf Arbeiten von Ben-Amram und Galil [1992] über die Simulation von Arbeitsspeichern mit wahlfreiem Zugriff unter ausschließlicher Verwendung von Zeigern). Pippenger stellt auch fest, dass es Algorithmen gibt, für die dies das Beste ist, was man tun kann; es gibt Probleme, die O( n ) in dem unreinen System, die ( n Protokoll n ) im reinen System.
Es gibt einige Vorbehalte zu diesem Papier. Der wichtigste ist, dass es sich nicht mit faulen funktionalen Sprachen wie Haskell befasst. Bird, Jones und De Moor [1997] zeigen, dass das von Pippenger konstruierte Problem in einer faulen funktionalen Sprache in O( n ) Zeit, aber sie stellen nicht fest (und soweit ich weiß, hat das auch noch niemand getan), ob eine faule funktionale Sprache alle Probleme in der gleichen asymptotischen Laufzeit lösen kann wie eine Sprache mit Mutation oder nicht.
Das von Pippenger konstruierte Problem erfordert ( n Protokoll n ) wurde speziell zu diesem Zweck erstellt und ist nicht unbedingt repräsentativ für praktische, reale Probleme. Es gibt einige Einschränkungen für das Problem, die etwas unerwartet, aber notwendig sind, damit der Beweis funktioniert; insbesondere erfordert das Problem, dass die Ergebnisse online berechnet werden, ohne dass auf zukünftige Eingaben zugegriffen werden kann, und dass die Eingabe aus einer Folge von Atomen aus einer unbeschränkten Menge möglicher Atome besteht, anstatt aus einer Menge fester Größe. Außerdem werden in dem Papier nur Ergebnisse (untere Schranke) für einen unreinen Algorithmus mit linearer Laufzeit ermittelt; bei Problemen, die eine längere Laufzeit erfordern, ist es möglich, dass die zusätzlichen O(log n ) des linearen Problems kann möglicherweise durch zusätzliche Operationen, die für Algorithmen mit längeren Laufzeiten erforderlich sind, "absorbiert" werden. Diese Klarstellungen und offenen Fragen werden kurz erörtert durch Ben-Amram [1996] .
In der Praxis können viele Algorithmen in einer rein funktionalen Sprache genauso effizient implementiert werden wie in einer Sprache mit veränderbaren Datenstrukturen. Eine gute Referenz für Techniken zur effizienten Implementierung rein funktionaler Datenstrukturen finden Sie unter Chris Okasakis "Purely Functional Data Structures" [Okasaki 1998] (dies ist eine erweiterte Version seiner Dissertation (Okasaki 1996) ).
Jeder, der Algorithmen auf rein funktionalen Datenstrukturen implementieren muss, sollte Okasaki lesen. Man kann im schlimmsten Fall immer eine O(log n ) Verlangsamung pro Operation durch die Simulation von veränderbarem Speicher mit einem ausgeglichenen Binärbaum, aber in vielen Fällen kann man noch wesentlich besser vorgehen, und Okasaki beschreibt viele nützliche Techniken, von amortisierten Techniken bis hin zu Echtzeittechniken, die die amortisierte Arbeit inkrementell erledigen. Rein funktionale Datenstrukturen können etwas schwierig zu handhaben und zu analysieren sein, aber sie bieten viele Vorteile wie z.B. referenzielle Transparenz, die bei der Compiler-Optimierung, beim parallelen und verteilten Rechnen und bei der Implementierung von Funktionen wie Versionierung, Undo und Rollback hilfreich sind.
Beachten Sie auch, dass es hier nur um asymptotische Laufzeiten geht. Viele Techniken zur Implementierung rein funktionaler Datenstrukturen führen zu einer gewissen Verlangsamung um einen konstanten Faktor, was auf die zusätzliche Buchhaltung zurückzuführen ist, die für das Funktionieren dieser Strukturen erforderlich ist, sowie auf Implementierungsdetails der betreffenden Sprache. Die Vorteile rein funktionaler Datenstrukturen können diese Verlangsamungen um konstante Faktoren überwiegen, so dass Sie im Allgemeinen je nach Problemstellung Kompromisse eingehen müssen.
Es gibt in der Tat mehrere Algorithmen und Datenstrukturen, für die keine asymptotisch effiziente rein funktionale Lösung (d.h. eine, die in reinem Lambda-Kalkül implementiert werden kann) bekannt ist, selbst bei Faulheit.
Wir gehen jedoch davon aus, dass in "imperativen" Sprachen der Zugriff auf den Speicher O(1) ist, während das in der Theorie asymptotisch (d.h. für unbegrenzte Problemgrößen) nicht so sein kann und der Zugriff auf den Speicher innerhalb eines großen Datensatzes immer O(log n) ist, was in einer funktionalen Sprache emuliert werden kann.
Wir dürfen auch nicht vergessen, dass eigentlich alle modernen funktionalen Sprachen veränderbare Daten anbieten, und Haskell bietet sie sogar an, ohne die Reinheit zu opfern (die ST-Monade).
Dieser Artikel behauptet, dass die bekannten rein funktionalen Implementierungen von der Algorithmus zum Auffinden der Vereinigung haben alle eine schlechtere asymptotische Komplexität als das von ihnen veröffentlichte Programm, das eine rein funktionale Schnittstelle hat, aber intern veränderliche Daten verwendet.
Die Tatsache, dass in anderen Antworten behauptet wird, dass es niemals einen Unterschied geben kann und dass beispielsweise der einzige "Nachteil" von rein funktionalem Code darin besteht, dass er parallelisiert werden kann, gibt Ihnen einen Eindruck von der Informiertheit/Sachlichkeit der Gemeinschaft der funktionalen Programmierer in diesen Fragen.
EDITAR:
In den Kommentaren wird darauf hingewiesen, dass eine voreingenommene Diskussion über die Vor- und Nachteile der reinen funktionalen Programmierung möglicherweise nicht von der "funktionalen Programmiergemeinschaft" ausgeht. Gutes Argument. Vielleicht sind die Befürworter, die ich sehe, einfach, um einen Kommentar zu zitieren, "ungebildet".
Ich denke zum Beispiel, dass diese Blog-Eintrag wird von jemandem geschrieben, von dem man sagen könnte, dass er die Gemeinschaft der funktionalen Programmierer repräsentiert, und da es sich um eine Liste von "Punkten für faule Auswertung" handelt, wäre es ein guter Platz, um alle Nachteile zu erwähnen, die faule und rein funktionale Programmierung haben könnte. Ein guter Platz wäre anstelle der folgenden (technisch wahren, aber so voreingenommenen, dass sie nicht mehr lustig ist) Ablehnung gewesen:
Wenn eine strikte Funktion die Komplexität O(f(n)) in einer strikten Sprache hat, dann hat sie auch die Komplexität O(f(n)) in einer lazy language. Warum sich Sorgen machen? :)
Bei einer festen Obergrenze für die Speichernutzung sollte es keinen Unterschied geben.
Skizze zum Beweis: Bei einer festen Obergrenze für den Speicherverbrauch 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 man tatsächlich auf dieser Maschine arbeiten würde. Dies ist so, weil man den veränderlichen Speicher als persistente Datenstruktur verwalten kann, was zu O(log(n)) Lese- und Schreibvorgängen führt, aber bei einer festen Obergrenze für den Speicherverbrauch kann man eine feste Menge an Speicher haben, wodurch diese auf O(1) abfällt. Somit kann die funktionale Implementierung die imperative Version sein, die in der funktionalen Implementierung der VM läuft, und so sollten beide die gleiche asymptotische Komplexität haben.
CodeJaeger ist eine Gemeinschaft für Programmierer, die täglich Hilfe erhalten..
Wir haben viele Inhalte, und Sie können auch Ihre eigenen Fragen stellen oder die Fragen anderer Leute lösen.
