Optimierung einer rekursiven Brute-Force in eine eher mathematisch-lineare Lösung
Ich habe dieses Haskell-Programm geschrieben, um Euler 15 zu lösen (es benutzt eine sehr einfache dynamische Programmierung, um ein bisschen schneller zu laufen, also kann ich es tatsächlich ausführen, aber das Entfernen würde erwarten, dass es in O(2^n) . O(n) gemacht werden konnte, indem man es in eine Gleichung umwandelte und nach etwas längerem Nachdenken erkannte, dass es meiner obigen Lösung ziemlich ähnlich ist, mit Ausnahme der Rekursion (die auf unserem Hardware ) wird durch Mathematik ersetzt, die dasselbe repräsentiert (was auf unserer Hardware schnell ist).
Gibt es einen systematischen Weg, um diese Art der Optimierung (erzeugen und beweisen einer Rekursion) auf rekursive Sätze von Ausdrücken, insbesondere eine, die realistisch zu einem Compiler "unterrichtet" werden könnte Also wird diese Reduktion automatisch gemacht?
3 Antworten
Sie können die dynamische Programmierung auch verwenden, wenn das Problem in kleinere Teilprobleme zerlegt werden kann, z. B.
F (x, y) = F (x-1, y) + F (x, y-1)
hier ist F (x, y) teilbar in kleinere Teilprobleme, daher kann DP verwendet werden
%Vor% Wie Sie bereits erwähnt haben, kann die DP-Compiler-Optimierung verwendet werden, um Anweisungen im Compiler zu schreiben, die bei einer rekursiven Lösung prüfen, ob sie in Unterprobleme kleinerer Größen aufteilbar ist. Wenn dies der Fall ist, verwenden Sie DP mit einfacher for-Schleife Aufbau wie oben, aber der schwierigste Teil ist die automatische Optimierung, zB oberhalb der DP-Anforderungen O(xmax*ymax) space, kann aber leicht optimiert werden, um eine Lösung in O(xmax+ymax) space
Beispiellöser: Ссылка
Leider kann ich nicht viel über analytische algorithmische Optimierungen sagen, aber in der Praxis gibt es eine nützliche Technik für die dynamische Programmierung namens memoization . Mit der Memoize-Bibliothek können Sie beispielsweise Ihren Code als
%Vor%, so dass die Funktion go nur einmal für eine beliebige Kombination von Argumenten berechnet wird.
Dies scheint auch eine philosophische Frage zu sein. Es scheint, dass Sie fragen, dass der Compiler erkennt, dass Sie einen effizienteren (schneller? Verwenden weniger Ressourcen?) Prozess möchten, um den Wert des Funktionsaufrufs zurückzugeben (anstatt die effizienteste Art, Ihren Code auszuführen).
Wenn wir die Idee weiterführen, könnten wir einen Compiler vorschlagen, in diesem Fall mathematische Formeln, die den Code prägnanter / effizienter destillieren könnten; alternativ könnte der Compiler sich für eine Verbindung mit dem Internet entscheiden und einen anderen Computer (z. B. Google oder Wolfram) die Berechnung durchführen lassen; Im Extremfall wird der Compiler vielleicht erkennen, dass es nicht die Antwort auf Euler Project 15 ist, was zu diesem Zeitpunkt besser sein könnte, sondern ein Schokoladenkuchenrezept oder Anweisungen für die Beheizung Ihres Hauses.
Die Frage lässt mich an künstliche Intelligenz und die Rolle des Computers denken (wie viel Mathematik sollte der Computer für Sie tun? Wie viel sollte er dem Code genauer folgen?). Das heißt, diese Art der Optimierung sollte ein interessantes Projekt zum Nachdenken sein.