Wie kombiniere ich nicht-Tail-Rekursion + effektive und synchronisierte Memoization + Bounded Stack-Verbrauch in Clojure?

Question

Wie kann man in Clojure die Nicht-Tail-Rekursion mit der synchronisierten Memoisierung und dem begrenzten Stack-Verbrauch (also kein Risiko eines Stack-Überlaufs) kombinieren? Mit synchronisierter Memoisierung meine ich, dass der Memo/Cache gleichzeitig und effizient zwischen Threads geteilt werden muss.

Mein spezieller Fall ist wie folgt:

; g() is non recursive 
; i is an integer 
; h is a hash with int keywords and vector of ints values 
; w is a hash with int keywords and int values 
(defn g [i h w] 
    (filter 
    #(-> (w %) 
     (= i)) 
    (h i))) 

; f is recursive, recurses non-trivially (non-tail, multiple times) 
; TODO: be memoizable (ideally in a synchronized way, for parallelism) 
; TODO: pose no risk stack overflow 
(defn f [i h w] 
    (if (nil? (h i)) 
    0 
    (let [part_sum 
     (map      ; will change this map to pmap or pvmap 
     #(f % h w) 
     (g i h))] 
     (-> (reduce + part_sum) 
      (/ 2) 
      (+ 1))))) 

; trivial, shown for completeness 
(defn ff [i h w] 
    (-> (f i h w) 
     (- 1) 
     (* 2) 
     (max 0))) 

Answer 1

Glücklicherweise können diese Fragen unabhängig angesprochen werden:

1. ein konsistenter gemeinsamer memoize Cache
2. nicht-Schwanz rekursive Iteration ohne den Stapel bläst

zu Frage 1, müssen Sie zunächst entscheiden, d an welcher Stelle der Cache gefüllt werden soll. Sollte es zu dem Zeitpunkt gefüllt sein, an dem Sie mit der Berechnung der Funktion beginnen. Das bedeutet, dass absolut garantiert sein sollte, dass jede Funktion nur einmal ausgeführt wird, auch wenn ein zweiter Aufruf erfolgt, während der erste ausgeführt wird. Oder wenn Sie zwei Aufrufe der Funktion gleichzeitig zulassen und nur eine davon im Cache speichern möchten. Eine geringfügige Abweichung davon ist, wenn Sie einfach das letzte zurückgegebene Ergebnis im Cache speichern.

Dieser letzte Ansatz ist, was Sie standardmäßig, wenn man

(def memoized-function (memoize function-name)) 

nur

nennen ans es ist suficient für fast alle Fälle. Wenn Sie die anderen Optionen benötigen, dann stellen Sie die Funktion, die Sie momisieren möchten, eine future statt das Ergebnis und nur deref die Werte, die Sie aus dem Cache erhalten, bevor Sie sie verwenden.

Für Option zwei, die in trampoline Funktion eingebaut ermöglicht konstante Stapel nicht-Schwanz rekursive Funktionen zu haben. Sie ändern Ihre Funktion so, dass sie im Basisfall (wenn die Rekursion beendet ist) einen Wert zurückgibt, der keine Funktion (nur ein normales Ergebnis) ist, und eine Funktion zurückgibt, wenn eine weitere Rekursion erforderlich ist. dann "springt" die trampoline Funktion wiederholt in die Funktion, bis ein Wert auf der anderen Seite herausfällt. Es sieht wie folgt aus:

user> (defn foo-helper [x] 
     (let [result 
       (if (pos? x) 
       #(foo-helper (dec x)) 
       x)] 
      (println "foo" x) 
      result)) 
#'user/foo-helper 
user> (trampoline foo-helper 4) 
foo 4 
foo 3 
foo 2 
foo 1 
foo 0 
0 

So können Sie den normalen Caching von Clojure mit dem normalen Trampolin Funktionsaufruf verbinden, ohne über "Thread-Sicherheit"