优化 Clojure 中的尾递归:指数移动平均线
Optimize tail-recursion in Clojure: exponential moving average
我是 Clojure 新手,正在尝试使用尾递归实现指数移动平均函数。在使用 lazy-seq 和 concat 与堆栈溢出进行了一些斗争之后,我得到了以下有效但非常慢的实现:
(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)))]
)
)
)
)
)
对于 10,000 个项目的集合,Clojure 将花费大约 1300 毫秒,而 Python Pandas 调用如
s.ewm(alpha=0.3, adjust=True).mean()
只需要 700 美元。我怎样才能缩小性能差距?谢谢,
如果 res
是一个向量(在您的示例中),那么使用 peek
而不是 last
会产生更好的性能:
(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)))])))))
你在我电脑上的例子:
(time (ema3 (range 10000) 0.3))
"Elapsed time: 990.417668 msecs"
使用peek
:
(time (ema3 (range 10000) 0.3))
"Elapsed time: 9.736761 msecs"
这是一个使用 reduce
的版本,在我的电脑上速度更快:
(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"
对这些时间持保留态度。使用 criterium 之类的东西进行更彻底的基准测试。您可以使用 mutability/transients.
获得更多收益
就我个人而言,我会用 reductions
懒洋洋地做这件事。它比使用 loop/recur 或使用 reduce
手动构建结果向量更简单,这也意味着您可以在构建结果时使用它,而不需要等待最后一个元素看完了再看第一篇
如果您最关心吞吐量,那么我认为 Taylor Wood 的 reduce
是最好的方法,但懒惰的解决方案只是稍微慢一点,而且更加灵活。
(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
老实说,在该基准测试中,您甚至不能说惰性版本比矢量版本慢。我认为我的版本仍然较慢,但这是一个微不足道的差异。
如果您告诉 Clojure 期待双打,您也可以加快速度,这样它就不必反复检查 a
、c
等的类型。
(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
还有 25% 的加速,还不错。我希望您可以通过在 reduce
解决方案或 loop/recur 中使用基元来挤出更多,如果您真的很绝望的话。这在循环中特别有用,因为您不必对 double
和 Double
之间的中间结果进行装箱和拆箱。
我是 Clojure 新手,正在尝试使用尾递归实现指数移动平均函数。在使用 lazy-seq 和 concat 与堆栈溢出进行了一些斗争之后,我得到了以下有效但非常慢的实现:
(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)))]
)
)
)
)
)
对于 10,000 个项目的集合,Clojure 将花费大约 1300 毫秒,而 Python Pandas 调用如
s.ewm(alpha=0.3, adjust=True).mean()
只需要 700 美元。我怎样才能缩小性能差距?谢谢,
如果 res
是一个向量(在您的示例中),那么使用 peek
而不是 last
会产生更好的性能:
(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)))])))))
你在我电脑上的例子:
(time (ema3 (range 10000) 0.3))
"Elapsed time: 990.417668 msecs"
使用peek
:
(time (ema3 (range 10000) 0.3))
"Elapsed time: 9.736761 msecs"
这是一个使用 reduce
的版本,在我的电脑上速度更快:
(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"
对这些时间持保留态度。使用 criterium 之类的东西进行更彻底的基准测试。您可以使用 mutability/transients.
获得更多收益就我个人而言,我会用 reductions
懒洋洋地做这件事。它比使用 loop/recur 或使用 reduce
手动构建结果向量更简单,这也意味着您可以在构建结果时使用它,而不需要等待最后一个元素看完了再看第一篇
如果您最关心吞吐量,那么我认为 Taylor Wood 的 reduce
是最好的方法,但懒惰的解决方案只是稍微慢一点,而且更加灵活。
(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
老实说,在该基准测试中,您甚至不能说惰性版本比矢量版本慢。我认为我的版本仍然较慢,但这是一个微不足道的差异。
如果您告诉 Clojure 期待双打,您也可以加快速度,这样它就不必反复检查 a
、c
等的类型。
(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
还有 25% 的加速,还不错。我希望您可以通过在 reduce
解决方案或 loop/recur 中使用基元来挤出更多,如果您真的很绝望的话。这在循环中特别有用,因为您不必对 double
和 Double
之间的中间结果进行装箱和拆箱。