Effizienz der rein funktionalen Programmierung

397

Weiß jemand, was die schlimmste mögliche asymptotische Verlangsamung ist, die auftreten kann, wenn rein funktional und nicht zwingend programmiert wird (dh Nebenwirkungen zugelassen werden)?

Klarstellung aus dem Kommentar von itowlson : Gibt es ein Problem, bei dem der bekannteste zerstörungsfreie Algorithmus asymptotisch schlechter ist als der bekannteste destruktive Algorithmus, und wenn ja, um wie viel?

Opt
quelle
6
Das gleiche wie beim zwingenden Programmieren, was auch immer das ist.
R. Martinho Fernandes
3
@jldupont: Um natürlich das Ergebnis einer Berechnung zurückzugeben. Es gibt viele nebenwirkungsfreie Programme. Sie können einfach nicht viel anderes tun, als mit ihren Eingaben zu rechnen. Aber das ist immer noch nützlich.
Jalf
24
Ich kann es so schlecht machen, wie Sie möchten, indem ich meinen Funktionscode schlecht schreibe! * grins * Ich denke, Sie fragen: "Gibt es ein Problem, bei dem der bekannteste zerstörungsfreie Algorithmus asymptotisch schlechter ist als der bekannteste destruktive Algorithmus, und wenn ja, um wie viel?" ... ist das richtig? ?
Itowlson
2
Könnten Sie ein Beispiel für die Art der Verlangsamung geben, an der Sie interessiert sind? Ihre Frage ist etwas vage.
Peter Recore
5
Ein Benutzer hat seine Antwort gelöscht, aber er behauptete, dass die funktionale Version des 8-Königinnen-Problems für n = 13 über eine Minute lief. Er gab zu, dass sie nicht "sehr gut geschrieben" war, also beschloss ich, meine eigene Version von zu schreiben 8 Königinnen in F #: pastebin.com/ffa8d4c4 . Unnötig zu erwähnen, dass mein reines Funktionsprogramm in etwas mehr als einer Sekunde n = 20 berechnet.
Julia

Antworten:

531

Laut Pippenger [1996] kann beim Vergleich eines rein funktionalen (und nicht faulen) Lisp-Systems mit einem System, das Daten mutieren kann, ein Algorithmus übersetzt werden, der für das unreine Lisp geschrieben wurde, das in O ( n ) ausgeführt wird zu einem Algorithmus in der reinen Lisp, der in O ( n log n ) -Zeit ausgeführt wird (basierend auf Arbeiten von Ben-Amram und Galil [1992] zur Simulation des Direktzugriffsspeichers mit nur Zeigern). Pippenger stellt auch fest, dass es Algorithmen gibt, für die dies das Beste ist, was Sie tun können. Es gibt Probleme, die im unreinen System O ( n ) sind und im reinen System Ω ( n log n ) sind.

Bei diesem Papier sind einige Einschränkungen zu beachten. Das wichtigste ist, dass es sich nicht um faule funktionale Sprachen wie Haskell handelt. Bird, Jones und De Moor [1997] zeigen, dass das von Pippenger konstruierte Problem in O ( n ) Zeit in einer faulen funktionalen Sprache gelöst werden kann , aber sie stellen nicht fest (und soweit ich weiß, hat niemand), ob oder Keine faule funktionale Sprache kann alle Probleme in derselben asymptotischen Laufzeit lösen wie eine Sprache mit Mutation.

Das von Pippenger konstruierte Problem erfordert , dass der in dem linearen Problem gesehene Ω ( n log n ) speziell konstruiert ist, um dieses Ergebnis zu erzielen, und ist nicht unbedingt repräsentativ für praktische Probleme in der realen Welt. Es gibt einige Einschränkungen für das Problem, die etwas unerwartet sind, aber erforderlich sind, damit der Beweis funktioniert. Das Problem erfordert insbesondere, 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 einer unbegrenzten Menge möglicher Atome und nicht aus einer Menge fester Größe besteht. Und das Papier legt nur (untere Grenze) Ergebnisse für einen unreinen Algorithmus der linearen Laufzeit fest; Bei Problemen, die eine längere Laufzeit erfordern, ist es möglich, dass das zusätzliche O (log n ) -Faktor bei zusätzlichen Operationen, die für Algorithmen mit längeren Laufzeiten erforderlich sind, möglicherweise "absorbiert" werden kann. Diese Klarstellungen und offenen Fragen werden von Ben-Amram [1996] kurz untersucht .

In der Praxis können viele Algorithmen in einer reinen Funktionssprache mit der gleichen Effizienz wie in einer Sprache mit veränderlichen Datenstrukturen implementiert werden. Eine gute Referenz zu Techniken zur effizienten Implementierung rein funktionaler Datenstrukturen finden Sie in Chris Okasakis "Rein funktionale Datenstrukturen" [Okasaki 1998] (eine erweiterte Version seiner Arbeit [Okasaki 1996] ).

Jeder, der Algorithmen für rein funktionale Datenstrukturen implementieren muss, sollte Okasaki lesen. Sie können im schlimmsten Fall immer eine O (log n ) -Verzögerung pro Operation erzielen, indem Sie veränderlichen Speicher mit einem ausgeglichenen Binärbaum simulieren. In vielen Fällen können Sie jedoch erheblich bessere Ergebnisse erzielen, und Okasaki beschreibt viele nützliche Techniken, von amortisierten Techniken bis hin zu realen. Zeit diejenigen, die die amortisierten Arbeit schrittweise erledigen. Rein funktionale Datenstrukturen können etwas schwierig zu bearbeiten und zu analysieren sein, bieten jedoch viele Vorteile wie referenzielle Transparenz, die bei der Compileroptimierung, beim parallelen und verteilten Rechnen sowie bei der Implementierung von Funktionen wie Versionierung, Rückgängigmachen und Rollback hilfreich sind.

Beachten Sie auch, dass in all dem nur asymptotische Laufzeiten behandelt werden. Viele Techniken zur Implementierung rein funktionaler Datenstrukturen führen zu einer gewissen konstanten Verlangsamung des Faktors, da zusätzliche Buchhaltung erforderlich ist, damit sie funktionieren, und Implementierungsdetails der betreffenden Sprache. Die Vorteile rein funktionaler Datenstrukturen können diese konstanten Faktorverlangsamungen überwiegen. Daher müssen Sie im Allgemeinen Kompromisse eingehen, die auf dem betreffenden Problem basieren.

Verweise

Brian Campbell
quelle
50
Pippinger ist die unbestrittene Autorität in dieser Frage. Wir sollten jedoch betonen, dass seine Ergebnisse theoretisch und nicht praktisch sind. Wenn es darum geht, funktionale Datenstrukturen praktisch und effizient zu gestalten, können Sie es nicht besser machen als Okasaki.
Norman Ramsey
6
itowlson: Ich muss zugeben, dass ich nicht genug von Pippenger gelesen habe, um Ihre Frage zu beantworten. Es wurde in einem von Okasaki zitierten Peer-Review-Journal veröffentlicht, und ich habe genug davon gelesen, um festzustellen, dass seine Behauptungen für diese Frage relevant sind, aber nicht genug, um den Beweis zu verstehen. Die unmittelbare Erkenntnis, die ich für die Konsequenzen der realen Welt bekomme, ist, dass es trivial ist, einen unreinen O ( n ) -Algorithmus in einen reinen O ( n log n ) -Algorithmus umzuwandeln , indem einfach ein modifizierbarer Speicher unter Verwendung eines ausgeglichenen Binärbaums simuliert wird. Es gibt Probleme, die es nicht besser machen können. Ich weiß nicht, ob sie rein theoretisch sind.
Brian Campbell
3
Das Pippenger-Ergebnis macht zwei wichtige Annahmen, die seinen Umfang einschränken: Es berücksichtigt "Online" - oder "reaktive" Berechnungen (nicht das übliche Modell einer Berechnung, die endliche Eingaben auf eine einzelne Ausgabe abbildet) und "symbolische" Berechnungen, bei denen Eingaben Sequenzen von sind Atome, die nur auf Gleichheit geprüft werden können (dh die Interpretation der Eingabe ist äußerst primitiv).
Chris Conway
2
Sehr gute Antwort; Ich möchte hinzufügen, dass es für rein funktionale Sprachen kein allgemein anerkanntes Modell für die Komplexität von Computern gibt, während in der unreinen Welt die Einheitskosten-RAM-Maschine relativ Standard ist (was den Vergleich schwieriger macht). Beachten Sie auch, dass die Obergrenze eines Lg (N) -Differenz in rein / unrein sehr einfach intuitiv erklärt werden kann, indem eine Implementierung von Arrays in einer reinen Sprache betrachtet wird (sie kostet lg (n) pro Operation (und Sie erhalten Verlauf). .
user51568
4
Wichtiger Punkt: Die sorgfältige Übersetzung einer rein funktionalen Spezifikation in eine kompliziertere, effizientere, rein funktionale Implementierung ist von geringem Nutzen, wenn Sie sie schließlich - entweder automatisch oder von Hand - in noch effizienteren unreinen Code übersetzen möchten. Verunreinigungen sind keine so große Sache, wenn Sie sie in einem Käfig aufbewahren können, z. B. indem Sie sie in einer Funktion ohne äußere Nebenwirkungen einschließen.
Robin Green
44

Es gibt in der Tat mehrere Algorithmen und Datenstrukturen, für die selbst bei Faulheit keine asymptotisch effiziente rein funktionale Lösung (eine, die in der reinen Lambda-Rechnung implementierbar ist) bekannt ist.

  • Der vorgenannte Gewerkschaftsfund
  • Hash-Tabellen
  • Arrays
  • Einige Graph-Algorithmen
  • ...

Wir gehen jedoch davon aus, dass in "imperativen" Sprachen der Zugriff auf den Speicher O (1) ist, während dies theoretisch nicht so asymptotisch sein kann (dh für unbegrenzte Problemgrößen) und der Zugriff auf den Speicher innerhalb eines riesigen Datensatzes immer O (log n) ist. , die in einer funktionalen Sprache emuliert werden können.

Wir müssen uns auch daran erinnern, dass tatsächlich alle modernen Funktionssprachen veränderbare Daten liefern, und Haskell liefert sie sogar, ohne die Reinheit zu beeinträchtigen (die ST-Monade).

jkff
quelle
3
Wenn der Datensatz in den physischen Speicher passt, ist der Zugriff darauf O (1), da es möglich ist, eine absolute Obergrenze für die Zeitspanne zum Lesen eines Elements zu finden. Wenn der Datensatz dies nicht tut, sprechen Sie von E / A, und dies ist bei weitem der dominierende Faktor, jedoch ist das Programm geschrieben.
Donal Fellows
Nun, natürlich spreche ich von O (log n) Operationen des Zugriffs auf externen Speicher. Auf jeden Fall habe ich bs gesprochen: externer Speicher kann auch O (1) -adressierbar sein ...
jkff
2
Ich denke, eines der größten Dinge, die die zwingende Programmierung im Vergleich zur funktionalen Programmierung gewinnt, ist die Fähigkeit, Verweise auf viele verschiedene Aspekte eines Zustands zu halten und einen neuen Zustand zu erzeugen, so dass alle diese Verweise auf die entsprechenden Aspekte des neuen Zustands verweisen. Die Verwendung der funktionalen Programmierung würde erfordern, dass direkte Dereferenzierungsoperationen durch Suchoperationen ersetzt werden, um den geeigneten Aspekt einer bestimmten Version des aktuellen Gesamtzustands zu finden.
Supercat
Selbst das Zeigermodell (O (log n) Speicherzugriff, lose gesagt) ist in extrem großen Maßstäben physikalisch nicht realistisch. Die Lichtgeschwindigkeit begrenzt, wie schnell verschiedene Computergeräte miteinander kommunizieren können, während derzeit angenommen wird, dass die maximale Informationsmenge, die in einer bestimmten Region gespeichert werden kann, durch ihre Oberfläche begrenzt ist.
Feuer
36

In diesem Artikel wird behauptet, dass die bekannten rein funktionalen Implementierungen des Union-Find-Algorithmus alle eine schlechtere asymptotische Komplexität aufweisen als die von ihnen veröffentlichten, die eine rein funktionale Schnittstelle haben, aber intern veränderbare Daten verwenden.

Die Tatsache, dass andere Antworten behaupten, dass es niemals einen Unterschied geben kann und dass der einzige "Nachteil" von rein funktionalem Code beispielsweise darin besteht, dass er parallelisiert werden kann, gibt Ihnen eine Vorstellung von der Informiertheit / Objektivität der funktionalen Programmiergemeinschaft in diesen Fragen .

BEARBEITEN:

Die folgenden Kommentare weisen darauf hin, dass eine voreingenommene Diskussion der Vor- und Nachteile einer reinen funktionalen Programmierung möglicherweise nicht von der „Community der funktionalen Programmierung“ stammt. Guter Punkt. Vielleicht sind die Befürworter, die ich sehe, nur, um einen Kommentar zu zitieren, "Analphabeten".

Ich denke zum Beispiel, dass dieser Blog-Beitrag von jemandem geschrieben wurde, von dem man sagen könnte, dass er repräsentativ für die funktionale Programmier-Community ist, und da es sich um eine Liste von „Punkten für eine verzögerte Bewertung“ handelt, wäre es ein guter Ort, um einen Nachteil zu erwähnen faule und rein funktionale Programmierung könnte haben. Ein guter Ort wäre anstelle der folgenden (technisch zutreffenden, aber voreingenommenen Entlassung) gewesen:

Wenn eine strenge Funktion in einer strengen Sprache die Komplexität O (f (n)) aufweist, hat sie auch in einer faulen Sprache die Komplexität O (f (n)). Warum ärgern? :) :)

Pascal Cuoq
quelle
4

Bei einer festen Obergrenze für die Speichernutzung sollte es keinen Unterschied geben.

Beweisskizze: Bei einer festgelegten Obergrenze für die Speichernutzung sollte es möglich sein, eine virtuelle Maschine zu schreiben, die einen imperativen Befehlssatz mit derselben asymptotischen Komplexität ausführt, als ob Sie tatsächlich auf dieser Maschine ausgeführt würden. Dies liegt daran, dass Sie den veränderlichen Speicher als persistente Datenstruktur verwalten können, wobei O (log (n)) gelesen und geschrieben wird. Mit einer festen Obergrenze für die Speichernutzung können Sie jedoch eine feste Speichermenge haben, wodurch diese entstehen Zerfall zu O (1). Daher kann die funktionale Implementierung die zwingende Version sein, die in der funktionalen Implementierung der VM ausgeführt wird, und daher sollten beide dieselbe asymptotische Komplexität aufweisen.

Brian
quelle
6
Eine feste Obergrenze für die Speichernutzung ist nicht die Art und Weise, wie Menschen diese Art von Dingen analysieren. Sie nehmen einen beliebig großen, aber endlichen Speicher an. Bei der Implementierung eines Algorithmus interessiert mich, wie er von der einfachsten Eingabe bis zu einer beliebigen Eingabegröße skaliert wird. Wenn Sie eine feste Obergrenze für die Speichernutzung festlegen, warum legen Sie dann nicht auch eine feste Obergrenze für die Dauer der Berechnung fest und sagen, dass alles O (1) ist?
Brian Campbell
@ Brian Campbell: Das ist wahr. Ich schlage nur vor, dass Sie, wenn Sie möchten, den Unterschied im konstanten Faktor in vielen Fällen in der Praxis ignorieren könnten. Man muss immer noch den Unterschied berücksichtigen, wenn man zwischen Speicher und Zeit Kompromisse eingeht, um sicherzustellen, dass die Verwendung von m mal mehr Speicher Ihre Laufzeit um mindestens einen Faktor von log (m) verringert.
Brian