Der Kontext dieser Frage ist, dass ich mit Gen Expression Programming (GEP), einer Form von evolutionärer Algorithmus, mit Erlang . GEP verwendet ein string-basiertes DSL mit der Bezeichnung Karva-Notation . Die Karva-Notation lässt sich leicht in Ausdrucksstrukturen umwandeln, aber der Übersetzungsalgorithmus geht von einer Implementierung mit veränderbaren Objekten aus: unvollständig Sub-Ausdrücke werden zu einem frühen Zeitpunkt des Übersetzungsprozesses erstellt und ihre eigenen Unter-Ausdrücke werden später mit Werten gefüllt, die zum Zeitpunkt der Erstellung nicht bekannt waren.
Der Zweck der Karva-Notation besteht darin, dass sie garantiert, dass syntaktisch korrekte Ausdrücke ohne teure Codierungstechniken oder Korrekturen des genetischen Codes erzeugt werden. Das Problem ist, dass ich mit einer Single-Assignment-Programmiersprache wie Erlang den Ausdruck neu erstellen muss tree kontinuierlich, wenn jeder Sub-Ausdruck ausgefüllt wird. Dies braucht ein preiswertes - O (n)? - Aktualisiere die Operation und konvertiere sie in eine, die in exponentieller Zeit vervollständigt werden würde (sofern ich mich nicht irre). Wenn ich keinen effizienten funktionalen Algorithmus finde, um K-Ausdrücke in Ausdrucksbäume umzuwandeln, dann ist eine der überzeugenden Eigenschaften von GEP verloren.
Ich schätze, dass das K-Ausdruck-Übersetzungsproblem ziemlich unklar ist, also was ich will, ist Rat, wie man einen inhärent nicht-funktionalen Algorithmus (der mutierbare Datenstrukturen ausnutzt) in einen, der das nicht tut, umwandelt. Wie passen reine funktionale Programmiersprachen viele der Algorithmen und Datenstrukturen, die in den frühen Tagen der Informatik produziert wurden, die von der Wandlungsfähigkeit abhängen, um die Leistungsmerkmale zu erhalten, die sie brauchen?
Es gibt keinen einzigen Weg dies zu tun, es muss wirklich von Fall zu Fall versucht werden. Ich versuche normalerweise, sie in einfachere Operationen zu zerlegen, zu falten und zu entfalten und dann von dort zu optimieren. Der Karva-Dekodierungsfall ist, wie andere bemerkt haben, ein Breitenbaum, und ich habe mit treeUnfoldM_BF begonnen. Vielleicht gibt es ähnliche Funktionen in Erlang.
Wenn die Dekodieroperation unangemessen teuer ist, könnten Sie die Dekodierung memotisieren und Subbäume teilen / wiederverwenden ... obwohl es wahrscheinlich nicht in einen generischen Tree-Unfold passt und Sie dazu spezielle Funktionen schreiben müssten. Wenn die Fitnessfunktion langsam genug ist, kann es gut sein, einen naiven Decoder wie den unten aufgeführten zu verwenden. Es wird den Baum jeden Aufruf vollständig wiederherstellen.
%Vor%Der Kontext dieser Frage ist, dass ich mit Gen Expression Programming (GEP), einer Form von evolutionärer Algorithmus, mit Erlang . GEP verwendet ein string-basiertes DSL mit der Bezeichnung Karva-Notation . Die Karva-Notation lässt sich leicht in Ausdrucksstrukturen umwandeln, aber der Übersetzungsalgorithmus geht von einer Implementierung mit veränderbaren Objekten aus: unvollständig Sub-Ausdrücke werden zu einem frühen Zeitpunkt des Übersetzungsprozesses erstellt und ihre eigenen Unter-Ausdrücke werden später mit Werten gefüllt, die zum Zeitpunkt der Erstellung nicht bekannt waren.
Der Zweck der Karva-Notation besteht darin, dass sie garantiert, dass syntaktisch korrekte Ausdrücke ohne teure Codierungstechniken oder Korrekturen des genetischen Codes erzeugt werden. Das Problem ist, dass ich mit einer Single-Assignment-Programmiersprache wie Erlang den Ausdruck neu erstellen muss tree kontinuierlich, wenn jeder Sub-Ausdruck ausgefüllt wird. Dies braucht ein preiswertes - O (n)? - Aktualisiere die Operation und konvertiere sie in eine, die in exponentieller Zeit vervollständigt werden würde (sofern ich mich nicht irre). Wenn ich keinen effizienten funktionalen Algorithmus finde, um K-Ausdrücke in Ausdrucksbäume umzuwandeln, dann ist eine der überzeugenden Eigenschaften von GEP verloren.
Ich schätze, dass das K-Ausdruck-Übersetzungsproblem ziemlich unklar ist, also was ich will, ist Rat, wie man einen inhärent nicht-funktionalen Algorithmus (der mutierbare Datenstrukturen ausnutzt) in einen, der das nicht tut, umwandelt. Wie passen reine funktionale Programmiersprachen viele der Algorithmen und Datenstrukturen, die in den frühen Tagen der Informatik produziert wurden, die von der Wandlungsfähigkeit abhängen, um die Leistungsmerkmale zu erhalten, die sie brauchen?
Ich denke, ich habe herausgefunden, wie Sie Ihr spezielles Problem mit den K-Bäumen lösen können (das allgemeine Problem ist zu schwer: P). Meine Lösung wird in einem schrecklichen hybriden Python-ähnlichen psudocode dargestellt (ich bin heute sehr langsam auf meinem FP) aber ändert keinen Knoten, nachdem du einen erstellt hast (der Trick besteht darin, den Baum zu erstellen) von unten nach oben)
Zuerst müssen wir herausfinden, welche Knoten zu welcher Ebene gehören:
%Vor% Also in Data.Tree , das sollte Ihnen data Tree a = Node {rootLabel :: a, subForest :: Forest a} geben. Jetzt können Sie dies in einen Baum von unten umwandeln:
Ich bin mir ziemlich sicher, dass wir das jetzt sehr einfach in die Einzelaufgabe Erlang / Haskell umwandeln können.
Es gibt eine Reihe von Lösungen, wenn ein veränderbarer Zustand in der funktionalen Programmierung erforderlich ist.
Verwenden Sie einen anderen Algorithmus, der das gleiche Problem löst. Z.B. Quicksort wird allgemein als veränderbar angesehen und kann daher in einer funktionalen Umgebung weniger nützlich sein, aber Mergesort ist im Allgemeinen besser für eine funktionale Einstellung geeignet. Ich kann nicht sagen, ob diese Option in Ihrem Fall möglich oder sinnvoll ist.
Sogar funktionale Programmiersprachen bieten normalerweise eine Möglichkeit, den Status zu ändern. ( Dieser Blog Beitrag scheint zu zeigen, wie man es in Erlang macht. ) Für einige Algorithmen und Datenstrukturen ist dies in der Tat die einzige verfügbare Option (es gibt aktive Forschung zu dem Thema, denke ich); Zum Beispiel werden Hash-Tabellen in funktionalen Programmiersprachen im Allgemeinen mit veränderbarem Zustand implementiert.
In Ihrem Fall bin ich mir nicht sicher, ob die Unveränderlichkeit wirklich zu einem Performance-Engpass führt. Sie haben recht, der (Sub-) Baum wird bei der Aktualisierung neu erstellt, aber die Erlang-Implementierung wird wahrscheinlich alle Teilbäume wiederverwenden, die sich nicht geändert haben, was zu O (log n) -Komplexität pro Update anstelle von O (1) mit veränderbarem Zustand führt . Außerdem werden die Knoten der Bäume nicht kopiert, sondern die Referenzen auf die Knoten, die relativ effizient sein sollten. Sie können über Baumaktualisierungen in einer funktionalen Einstellung in z.B. die Dissertation von Okasaki oder in seinem Buch "Purely Functional Data Structures" basierend auf der These. Ich würde versuchen, den Algorithmus mit einer unveränderlichen Datenstruktur zu implementieren und zu einem veränderbaren zu wechseln, wenn Sie ein Leistungsproblem haben.
Es gibt keinen einzigen Weg dies zu tun, es muss wirklich von Fall zu Fall versucht werden. Ich versuche normalerweise, sie in einfachere Operationen zu zerlegen, zu falten und zu entfalten und dann von dort zu optimieren. Der Karva-Dekodierungsfall ist, wie andere bemerkt haben, ein Breitenbaum, und ich habe mit treeUnfoldM_BF begonnen. Vielleicht gibt es ähnliche Funktionen in Erlang.
Wenn die Dekodieroperation unangemessen teuer ist, könnten Sie die Dekodierung memotisieren und Subbäume teilen / wiederverwenden ... obwohl es wahrscheinlich nicht in einen generischen Tree-Unfold passt und Sie dazu spezielle Funktionen schreiben müssten. Wenn die Fitnessfunktion langsam genug ist, kann es gut sein, einen naiven Decoder wie den unten aufgeführten zu verwenden. Es wird den Baum jeden Aufruf vollständig wiederherstellen.
%Vor%Es gibt eine Reihe von Lösungen, wenn ein veränderbarer Zustand in der funktionalen Programmierung erforderlich ist.
Verwenden Sie einen anderen Algorithmus, der das gleiche Problem löst. Z.B. Quicksort wird allgemein als veränderbar angesehen und kann daher in einer funktionalen Umgebung weniger nützlich sein, aber Mergesort ist im Allgemeinen besser für eine funktionale Einstellung geeignet. Ich kann nicht sagen, ob diese Option in Ihrem Fall möglich oder sinnvoll ist.
Sogar funktionale Programmiersprachen bieten normalerweise eine Möglichkeit, den Status zu ändern. ( Dieser Blog Beitrag scheint zu zeigen, wie man es in Erlang macht. ) Für einige Algorithmen und Datenstrukturen ist dies in der Tat die einzige verfügbare Option (es gibt aktive Forschung zu dem Thema, denke ich); Zum Beispiel werden Hash-Tabellen in funktionalen Programmiersprachen im Allgemeinen mit veränderbarem Zustand implementiert.
In Ihrem Fall bin ich mir nicht sicher, ob die Unveränderlichkeit wirklich zu einem Performance-Engpass führt. Sie haben recht, der (Sub-) Baum wird bei der Aktualisierung neu erstellt, aber die Erlang-Implementierung wird wahrscheinlich alle Teilbäume wiederverwenden, die sich nicht geändert haben, was zu O (log n) -Komplexität pro Update anstelle von O (1) mit veränderbarem Zustand führt . Außerdem werden die Knoten der Bäume nicht kopiert, sondern die Referenzen auf die Knoten, die relativ effizient sein sollten. Sie können über Baumaktualisierungen in einer funktionalen Einstellung in z.B. die Dissertation von Okasaki oder in seinem Buch "Purely Functional Data Structures" basierend auf der These. Ich würde versuchen, den Algorithmus mit einer unveränderlichen Datenstruktur zu implementieren und zu einem veränderbaren zu wechseln, wenn Sie ein Leistungsproblem haben.
Ich denke, ich habe herausgefunden, wie Sie Ihr spezielles Problem mit den K-Bäumen lösen können (das allgemeine Problem ist zu schwer: P). Meine Lösung wird in einem schrecklichen hybriden Python-ähnlichen psudocode dargestellt (ich bin heute sehr langsam auf meinem FP) aber ändert keinen Knoten, nachdem du einen erstellt hast (der Trick besteht darin, den Baum zu erstellen) von unten nach oben)
Zuerst müssen wir herausfinden, welche Knoten zu welcher Ebene gehören:
%Vor% Also in +/*abcd , das sollte Ihnen [+, /*, abcd] geben. Jetzt können Sie dies in einen Baum von unten umwandeln:
Ich bin mir ziemlich sicher, dass wir das jetzt sehr einfach in die Einzelaufgabe Erlang / Haskell umwandeln können.
Tags und Links algorithm computer-science functional-programming mutable evolutionary-algorithm