Benötigen Sie bei der funktionalen Programmierung mehr Speicher, wenn die meisten Datenstrukturen unveränderlich sind?

Bei der funktionalen Programmierung sind da fast alle Datenstrukturen unveränderlich, wenn sich der Zustand ändern muss, wird eine neue Struktur angelegt. Bedeutet das viel mehr Speicherbedarf? Ich kenne das objektorientierte Programmierparadigma gut, jetzt versuche ich, etwas über das funktionale Programmierparadigma zu lernen. Das Konzept, dass alles unveränderlich ist, verwirrt mich. Es scheint, dass ein Programm mit unveränderlichen Strukturen viel mehr Speicher benötigt als ein Programm mit veränderlichen Strukturen. Schaue ich das überhaupt richtig an?

Die einzig richtige Antwort ist "manchmal". Es gibt viele Tricks, mit denen funktionale Sprachen die Verschwendung von Speicher vermeiden können. Die Unveränderlichkeit erleichtert die gemeinsame Nutzung von Daten zwischen Funktionen und sogar zwischen Datenstrukturen, da der Compiler gewährleisten kann, dass die Daten nicht geändert werden. Funktionale Sprachen tendieren dazu, die Verwendung von Datenstrukturen zu fördern, die effizient als unveränderliche Strukturen verwendet werden können (zum Beispiel Bäume anstelle von Hash-Tabellen). Wenn Sie der Mischung Faulheit hinzufügen, wie dies bei vielen funktionalen Sprachen der Fall ist, werden dadurch neue Möglichkeiten zum Speichern von Speicher hinzugefügt (es werden auch neue Möglichkeiten zum Verschwenden von Speicher hinzugefügt, aber darauf werde ich nicht eingehen).

Bei der funktionalen Programmierung sind da fast alle Datenstrukturen unveränderlich, wenn sich der Zustand ändern muss, wird eine neue Struktur angelegt. Bedeutet das viel mehr Speicherbedarf?

Das hängt von der Datenstruktur, den genauen Änderungen, die Sie vorgenommen haben, und in einigen Fällen vom Optimierer ab. Als ein Beispiel betrachten wir das Voranstellen einer Liste:

list2 = prepend(42, list1) // list2 is now a list that contains 42 followed
                           // by the elements of list1. list1 is unchanged

Hier ist der zusätzliche Speicherbedarf konstant - ebenso die Laufzeitkosten für Anrufe prepend. Warum? Denn prependschafft einfach eine neue Zelle, die 42als Kopf und list1als Schwanz hat. Es muss nicht kopiert oder auf andere Weise wiederholt werden list2, um dies zu erreichen. Das heißt, mit Ausnahme des zum Speichern erforderlichen Speichers 42wird list2derselbe Speicher wiederverwendet, der von verwendet wird list1. Da beide Listen unveränderlich sind, ist diese Freigabe absolut sicher.

In ähnlicher Weise benötigen die meisten Operationen beim Arbeiten mit ausgeglichenen Baumstrukturen nur logarithmisch viel zusätzlichen Speicherplatz, da möglicherweise nur ein Pfad des Baums gemeinsam genutzt wird.

Bei Arrays sieht die Situation etwas anders aus. Aus diesem Grund werden Arrays in vielen FP-Sprachen nicht so häufig verwendet. Wenn Sie jedoch so etwas tun arr2 = map(f, arr1)und arr1nach dieser Zeile nie wieder verwendet werden, kann ein intelligentes Optimierungsprogramm tatsächlich Code erstellen, der mutiert, arr1anstatt ein neues Array zu erstellen (ohne das Verhalten des Programms zu beeinflussen). In diesem Fall erfolgt die Aufführung natürlich wie in einer Gebotssprache.

Naive Implementierungen würden dieses Problem in der Tat aufdecken. Wenn Sie eine neue Datenstruktur erstellen, anstatt eine vorhandene zu aktualisieren, müssen Sie einen gewissen Overhead haben.

Verschiedene Sprachen haben unterschiedliche Arten, damit umzugehen, und es gibt einige Tricks, die die meisten von ihnen anwenden.

Eine Strategie ist die Speicherbereinigung . In dem Moment, in dem die neue Struktur erstellt wurde oder kurz danach, werden Verweise auf die alte Struktur ungültig, und der Garbage Collector wird sie je nach GC-Algorithmus sofort oder früh genug abrufen. Dies bedeutet, dass der Overhead zwar noch besteht, aber nur vorübergehend ist und nicht linear mit der Datenmenge wächst.

Eine andere ist die Auswahl verschiedener Arten von Datenstrukturen. Wo Arrays die Datenstruktur der Zielliste in imperativen Sprachen sind (normalerweise in einen dynamischen Neuzuweisungscontainer wie std::vectorin C ++ eingeschlossen), bevorzugen funktionale Sprachen häufig verknüpfte Listen. Bei einer verknüpften Liste kann eine Voranstellungsoperation ('cons') die vorhandene Liste als Endpunkt der neuen Liste wiederverwenden, sodass nur der neue Listenkopf zugewiesen wird. Ähnliche Strategien gibt es für andere Arten von Datenstrukturen - Mengen, Bäume, wie Sie es nennen.

Und dann gibt es eine faule Bewertung à la Haskell. Die Idee ist, dass von Ihnen erstellte Datenstrukturen nicht sofort vollständig erstellt werden. Stattdessen werden sie als "Thunks" gespeichert (Sie können sich diese als Rezepte für die Erstellung des Werts vorstellen, wenn er benötigt wird). Erst wenn der Wert benötigt wird, wird der Thunk zu einem tatsächlichen Wert erweitert. Dies bedeutet, dass die Speicherzuweisung aufgeschoben werden kann, bis eine Auswertung erforderlich ist, und zu diesem Zeitpunkt mehrere Thunks in einer Speicherzuweisung kombiniert werden können.

Ich weiß nur wenig über Clojure und seine unveränderlichen Datenstrukturen .

Clojure bietet eine Reihe unveränderlicher Listen, Vektoren, Mengen und Karten. Da sie nicht geändert werden können, bedeutet das Hinzufügen oder Entfernen von Elementen aus einer unveränderlichen Sammlung, dass eine neue Sammlung wie die alte erstellt wird, jedoch mit den erforderlichen Änderungen. Persistenz ist ein Begriff, der verwendet wird, um die Eigenschaft zu beschreiben, bei der die alte Version der Sammlung nach der "Änderung" noch verfügbar ist und die Auflistung ihre Leistungsgarantien für die meisten Vorgänge beibehält. Konkret bedeutet dies, dass die neue Version nicht mit einer vollständigen Kopie erstellt werden kann, da dies lineare Zeit erfordern würde. Persistente Sammlungen werden zwangsläufig mithilfe verknüpfter Datenstrukturen implementiert, sodass die neuen Versionen die Struktur mit der vorherigen Version gemeinsam nutzen können.

Grafisch können wir so etwas darstellen:

(def my-list '(1 2 3))

    +---+      +---+      +---+
    | 1 | ---> | 2 | ---> | 3 |
    +---+      +---+      +---+

(def new-list (conj my-list 0))

              +-----------------------------+
    +---+     | +---+      +---+      +---+ |
    | 0 | --->| | 1 | ---> | 2 | ---> | 3 | |
    +---+     | +---+      +---+      +---+ |
              +-----------------------------+

Zusätzlich zu den anderen Antworten möchte ich die Programmiersprache Clean erwähnen, die sogenannte Unique Types unterstützt . Ich kenne diese Sprache nicht, aber ich nehme an, dass eindeutige Typen eine Art "destruktives Update" unterstützen.

Mit anderen Worten, während die Semantik der Aktualisierung eines Status darin besteht, dass Sie durch Anwenden einer Funktion einen neuen Wert aus einem alten Wert erstellen, kann die Eindeutigkeitsbeschränkung dem Compiler ermöglichen, Datenobjekte intern wiederzuverwenden, da er weiß, dass auf den alten Wert nicht verwiesen wird mehr im Programm, nachdem der neue Wert erzeugt wurde.

Weitere Details finden Sie zB auf der Clean-Homepage und in diesem Wikipedia-Artikel