Memoize a Clojure Funktion, die einen faulen Sequenz als Eingabe nimmt

Wie kann ich memoize Arbeit haben, wenn das Argument einer memoised Funktion eine SequenzMemoize a Clojure Funktion, die einen faulen Sequenz als Eingabe nimmt

(defn foo 
    ([x] (println "Hello First") (reduce + x)) 
    ([x y] (println "Hello Second") (reduce + (range x y)))) 


(def baz (memoize foo))

Passing einer Arg- ist:

(time (baz (range 1 1000000))) ;=> Hello First "Elapsed time: 14.870628 msecs"

(time (baz (range 1 1000000))) ;=> "Elapsed time: 65.386561 msecs"

Pass 2 argumente:

(time (baz 1 1000000)) ;=> Hello Second "Elapsed time: 18.619768 msecs"

(time (baz 1 1000000)) ;=> "Elapsed time: 0.069684 msecs"

Der zweite Lauf der Funktion, wenn zwei Argumente übergeben scheint zu sein, was ich erwarte.

erscheint jedoch unter Verwendung eines Vektors mit Sequenzen zu arbeiten ...

(time (baz [1 2 3 5 3 5 7 4 6 7 4 45 6 7])) ;=> Hello First "Elapsed time: 0.294963 msecs" 


(time (baz [1 2 3 5 3 5 7 4 6 7 4 45 6 7])) ;=> "Elapsed time: 0.068229 msecs"

Quelle

2016-07-31 adebesin

Hmm. Wie man damit umgeht, ist eine knifflige Sache - man muss die gesamte Sequenz konsumieren, um die Identität zu Vergleichszwecken zu bestimmen, aber einer der Vorteile, ISeq zu unterstützen, ist das Potenzial für Faulheit. So kann ich das Argument für die aktuelle Semantik sehen - dass wir nicht die Vorkosten eines Aufrufs erhöhen wollen (um eine Sequenz vollständig zu realisieren, die theoretisch unendlich sein könnte), um möglicherweise Caching zu ermöglichen. –

... bei einer Implementierungsebene stellt sich die Frage, was passiert, wenn eine Sequenz als Schlüssel in einer Map verwendet wird. dh. do-Sequenzen unterstützen '.hashCode' in einer Weise, die ihren Inhalt reflektiert (und somit O (n) evaluiert), in einer Weise, die ihre Identität widerspiegelt (so dass die gleiche Sequenz nur mit sich selbst verglichen wird) oder gar nicht ? –

@CharlesDuffy - jede Implementierung des Sequenzvergleichs (Hash-Codes usw.) kann nur den Fall der Ungleichheit optimieren. Paradoxerweise ist es richtig, wenn "Memoize" als nützlich erachtet wird - wenn Sie den gleichen Schlüssel in der Karte haben, erhalten Sie die O (n) -Vergleichszeit, unabhängig von der Implementierung. Die Moral der Geschichte - "memoize" ist nicht dafür gedacht, mit langen Sequenzen als Parameter verwendet zu werden. –

memoize funktioniert, brauchen Sie nur Äpfel mit Äpfeln zu vergleichen. memoize sucht den Parameter in der Hash-Map der zuvor verwendeten, und als Ergebnis werden Sie die Sequenzen vergleichen. lange Sequenzen zu vergleichen ist, was eine lange Zeit in Anspruch nimmt, ob sie Vektoren sind oder nicht:

user> (def x (vec (range 1000000))) 
;; => #'user/x 
user> (def y (vec (range 1000000))) 
;; => #'user/y 
user> (time (= x y)) 
"Elapsed time: 64.351274 msecs" 
;; => true 
user> (time (baz x)) 
"Elapsed time: 67.42694 msecs" 
;; => 499999500000 
user> (time (baz x)) 
"Elapsed time: 73.231174 msecs" 
;; => 499999500000

Wenn Sie sehr kurze verwenden Eingabesequenzen, die Zeit von den reduce in Ihrer Funktion dominiert wird. Aber mit sehr langen die meiste Zeit, die Sie sehen, ist eigentlich die Vergleichszeit innerhalb memoize.

So technisch memoize Werke, auf die gleiche Art und Weise für alle Sequenzen. Aber "technisch" zu arbeiten bedeutet nicht "nützlich zu sein". Wie Sie selbst entdeckt haben, ist es nutzlos (tatsächlich vielleicht sogar schädlich) für die Eingabe mit teuren Vergleichs-Semantik. Ihre zweite Signatur löst dieses Problem.

Quelle

2016-07-31 18:04:09

Memoize a Clojure Funktion, die einen faulen Sequenz als Eingabe nimmt

Antwort

Verwandte Themen