Optimieren der Tail-Rekursion in Clojure: exponentieller gleitender Durchschnitt

Question

Ich bin neu in Clojure und versuche, eine Exponential-Moving-Average-Funktion mit Tail-Rekursion zu implementieren. Nach ein wenig mit Stack kämpfen faul-Seq und concat surverses verwenden, habe ich auf die folgende Implementierung, die funktioniert, ist aber sehr langsam:

(defn ema3 [c a] 
    (loop [ct (rest c) res [(first c)]] 
     (if (= (count ct) 0) 
      res 
      (recur 
       (rest ct) 
       (into;NOT LAZY-SEQ OR CONCAT 
        res 
        [(+ (* a (first ct)) (* (- 1 a) (last res)))] 
        ) 
       ) 
      ) 
     ) 
    ) 

Für eine 10.000 Artikel Sammlung wird Clojure 1300ms Sie sich um, während eine Python Pandas Anruf wie

s.ewm(alpha=0.3, adjust=True).mean() 

wird nur 700 US nehmen. Wie kann ich diese Leistungslücke reduzieren? Vielen Dank,

Answer 1

Wenn res ist ein Vektor (die es in Ihrem Beispiel), dann mit peek statt last viel bessere Leistung ergibt:

(defn ema3 [c a] 
    (loop [ct (rest c) res [(first c)]] 
    (if (= (count ct) 0) 
     res 
     (recur 
     (rest ct) 
     (into 
      res 
      [(+ (* a (first ct)) (* (- 1 a) (peek res)))]))))) 

Ihr Beispiel auf meinem Computer:

(time (ema3 (range 10000) 0.3)) 
"Elapsed time: 990.417668 msecs" 

Verwendung peek:

(time (ema3 (range 10000) 0.3)) 
"Elapsed time: 9.736761 msecs" 

Hier ist eine Version reduce verwenden, die auf meinem Computer noch schneller ist:

(defn ema3 [c a] 
    (reduce (fn [res ct] 
      (conj 
       res 
       (+ (* a ct) 
       (* (- 1 a) (peek res))))) 
      [(first c)] 
      (rest c))) 
;; "Elapsed time: 0.98824 msecs" 

diese Timings mit einem Körnchen Salz. Verwenden Sie etwas wie criterium für ein besseres Benchmarking. Sie können möglicherweise mehr Gewinne mit Mutabilität/Transienten auspressen.

Answer 2

Persönlich würde ich dies träge mit reductions tun. Es ist einfacher zu tun, als loop/recur zu verwenden oder einen Ergebnisvektor von Hand mit reduce aufzubauen, und es bedeutet auch, dass Sie das Ergebnis konsumieren können, während es aufgebaut ist, anstatt auf das letzte Element warten zu müssen, bevor Sie es können schau dir den ersten an.

Wenn Sie am meisten am Durchsatz interessiert sind, dann nehme ich an, dass Taylor Wood's reduce der beste Ansatz ist, aber die faule Lösung ist nur sehr wenig langsamer und ist viel flexibler.

(defn ema3-reductions [c a] 
    (let [a' (- 1 a)] 
    (reductions 
    (fn [ave x] 
     (+ (* a x) 
      (* (- 1 a') ave))) 
    (first c) 
    (rest c)))) 

user> (quick-bench (dorun (ema3-reductions (range 10000) 0.3))) 

Evaluation count : 288 in 6 samples of 48 calls. 
      Execution time mean : 2.336732 ms 
    Execution time std-deviation : 282.205842 µs 
    Execution time lower quantile : 2.125654 ms (2.5%) 
    Execution time upper quantile : 2.686204 ms (97.5%) 
        Overhead used : 8.637601 ns 
nil 
user> (quick-bench (dorun (ema3-reduce (range 10000) 0.3))) 
Evaluation count : 270 in 6 samples of 45 calls. 
      Execution time mean : 2.357937 ms 
    Execution time std-deviation : 26.934956 µs 
    Execution time lower quantile : 2.311448 ms (2.5%) 
    Execution time upper quantile : 2.381077 ms (97.5%) 
        Overhead used : 8.637601 ns 
nil 

Ehrlich in diesem Benchmark Sie die faulen Version nicht einmal sagen kann langsamer als die Vektor-Version ist. Ich denke, meine Version ist immer noch langsamer, aber es ist ein verschwindend kleiner Unterschied.

Sie können auch die Dinge beschleunigen, wenn Sie Clojure darauf hinweisen, Doppelgänger zu erwarten, also muss es die Typen a, c und so weiter nicht doppelt überprüfen.

(defn ema3-reductions-prim [c ^double a] 
    (let [a' (- 1.0 a)] 
    (reductions (fn [ave x] 
        (+ (* a (double x)) 
        (* a' (double ave)))) 
       (first c) 
       (rest c)))) 

user> (quick-bench (dorun (ema3-reductions-prim (range 10000) 0.3))) 
Evaluation count : 432 in 6 samples of 72 calls. 
      Execution time mean : 1.720125 ms 
    Execution time std-deviation : 385.880730 µs 
    Execution time lower quantile : 1.354539 ms (2.5%) 
    Execution time upper quantile : 2.141612 ms (97.5%) 
        Overhead used : 8.637601 ns 
nil 

Weitere 25% Beschleunigung, nicht zu schlecht. Ich nehme an, Sie könnten ein bisschen mehr auspressen, indem Sie entweder in einer reduce Lösung Primitive verwenden oder wenn Sie wirklich verzweifelt sind, mit loop/recurve. Es wäre besonders hilfreich in einer Schleife, weil Sie die Zwischenergebnisse zwischen double und Double nicht weiter boxen und auspacken müssen.