Ich habe mich entschieden, den CLRS-Algorithmus für die Einführung in Algorithmen zu bearbeiten, und habe das Druckproblem sorgfältig ausgewählt hier .
Ich habe das Problem durchgearbeitet und eine imperative Lösung gefunden, die in Python einfach zu implementieren war, aber etwas weniger in Clojure.
Ich bin völlig überfordert, die Compute-Matrix-Funktion von meiner Lösung in idiomatische Clojure zu übersetzen. Irgendwelche Vorschläge? Hier ist der Pseudocode für die Compute-Matrix-Funktion:
%Vor%Außerdem würde ich das Feedback über den Rest meiner Clojure-Quelle sehr schätzen, insbesondere in Bezug darauf, wie idiomatisch es ist. Ist es mir gelungen, außerhalb des Imperativparadigmas für den Clojure-Code, den ich bisher geschrieben habe, genügend nachzudenken? Hier ist es:
%Vor%BEARBEITEN: Ich habe meine Matrix-Konstrukt-Funktion mit der gegebenen Rückmeldung aktualisiert, also ist sie jetzt eine Zeile kürzer als meine Python-Implementierung.
%Vor% Ihre Matrix-Lookup- und Matrix-Set-Funktionen können vereinfacht werden. Sie können assoc-in und get-in zum Manipulieren verschachtelter assoziativer Strukturen verwenden.
Alex Miller erwähnt primitive Arrays. Wenn Sie am Ende in diese Richtung gehen müssen, können Sie mit int-array , aset-int und aget beginnen. Sehen Sie sich die clojure.core Dokumentation an, um mehr zu erfahren.
Ich kletterte an die Wand und konnte so gut wie Clojure-artig denken, um den Kern-Rechenmatrix-Algorithmus in ein praktikables Programm zu übersetzen.
Es ist nur eine Zeile länger als meine Python-Implementierung, obwohl es dichter geschrieben scheint. Natürlich sind Konzepte wie "map" und "reduce" Funktionen auf höherer Ebene, auf die Sie Ihre Denkgrenze setzen müssen.
Ich glaube, dass diese Implementierung auch einen Bug in meinem Python-Bug behebt. :)
%Vor%Danke Alex und Jake für deine Kommentare. Sie waren beide sehr hilfreich und haben mir auf meinem Weg zum idiomatischen Clojure geholfen.
Meine allgemeine Herangehensweise an dynamische Programme in Clojure besteht nicht darin, sich direkt mit der Konstruktion der Wertematrix zu befassen, sondern die Speicherung in Kombination mit einem Fixpunktkombinator zu verwenden. Hier ist mein Beispiel für die Berechnung der Bearbeitungsdistanz:
%Vor%Der einzige Unterschied zur naiven rekursiven Lösung besteht darin, die rekursiven Aufrufe durch Aufrufe von fp zu ersetzen.
Und dann erstelle ich einen festgeschriebenen Fixpunkt mit:
%Vor%Und dann rufe es mit:
%Vor%Ich finde Memoization einfacher, mein Gehirn einzuwickeln, als Tabellen zu mutieren.