Clojure: gc超过限制，惰性求值，π序列

Question

接下来的代码：

(ns clojure101.series)

(defn avg [[x y]] (/ (+ x y) 2))

(defn avg-damp
  [seq]
  (map avg (partition 2 seq)))

(defn avg-damp-n
  [n]
  (apply comp (repeat n avg-damp)))

(defn sums
  [seq]
  (reductions + seq))

(defn Gregory-Leibniz-n
  [n]
  (/ (Math/pow -1 n) (inc (* 2 n))))

(def Gregory-Leibniz-pi
     (map #(* 4 (Gregory-Leibniz-n %)) (iterate inc 0)))

(println (first ((avg-damp-n 10) (sums Gregory-Leibniz-pi))))

当n=20时，我遇到了"gc overhead limit exceeded"错误。该怎么解决呢？

更新：我已更改avg-damp-n函数。

(defn avg-damp-n
  [n seq]
  (if (= n 0) seq
      (recur (dec n) (avg-damp seq))))

现在我可以得到n=20的数字

(time
 (let [n 20]
   (println n (first (avg-damp-n n (sums Gregory-Leibniz-pi))))))

20 3.141593197943081
"Elapsed time: 3705.821263 msecs"

更新2 我修复了一些错误，现在它可以正常工作:

(ns clojure101.series)

(defn avg [[x y]] (/ (+ x y) 2))

(defn avg-damp
  [seq]
  (map avg (partition 2 1 seq)))

(defn avg-damp-n
  [n]
  (apply comp (repeat n avg-damp)))

(defn sums
  [seq]
  (reductions + seq))

(defn Gregory-Leibniz-n
  [n]
  (/ (int (Math/pow -1 n)) (inc (* 2 n))))

(def Gregory-Leibniz-pi
     (map #(* 4 (Gregory-Leibniz-n %)) (range)))

; π = 3.14159265358979323846264338327950288419716939937510...

(time
 (let [n 100]
   (println n (double (first ((avg-damp-n n) (sums Gregory-Leibniz-pi)))))))

输出：

100 3.141592653589793
"Elapsed time: 239.253227 msecs"

- edbond

Answer 1

如kotarak所述，将惰性序列堆叠在惰性序列上似乎在GC方面效率低下。我能够在一个缓慢的原子系统上重现这个问题。参见：Error java.lang.OutOfMemoryError: GC overhead limit exceeded。

对于我来说，Gregory-Leibniz PI计算直接转化为这个Clojure代码，它只使用了一个惰性序列。

(defn Gregory-Leibniz-pi [n]
  (->> (range n)
       (map (fn [n] (/ (Math/pow -1 n) (inc (* 2 n)))))
       (apply +)
       (* 4)))

- Jürgen Hötzel

Answer 2

首先，尝试一个愚蠢但有效的解决方法：增加Java堆空间。

;in your clojure launch script
java -Xmx2G ...other options...

程序中有一部分在分区时不是惰性的，但是如果通过去掉对 count 的调用使其变为惰性，仍然会因默认堆大小导致 OutOfMemoryError 错误。可以通过用 reduce 计算平均值来替换 avg-damp-n 的 cleverness。

(take (integer-exponent 2 20) seq)

仍然会导致OutOfMemoryError。查看其他所有源代码，我没有看到其他任何东西看起来应该消耗堆空间。

- ellisbben

Answer 3

嗯... 对我来说这个可以工作。在Windows XP上测试过，使用Clojure 1.2版本。

user=> (defn avg
         [xs & {:keys [n] :or {n 2}}]
         (/ (reduce + xs) n))
#'user/avg
user=> (defn Gregory-Leibniz-n
         [n]
         (/ (Math/pow -1 n) (inc (+ n n))))
#'user/Gregory-Leibniz-n
user=> (->> (range)
         (map #(* 4 (Gregory-Leibniz-n %)))
         (reductions +)
         (partition 20)
         (map #(avg % :n 20))
         first
         println)
3.1689144018345354

这是正确的答案吗？我不了解Gregory-Leibniz递归，所以不确定这是否正确。

我注意到一个问题：你试图过于聪明。也就是说，你的avg-damp-n堆栈上的lazy seq又堆叠了一个lazy seq。由于可以插入任意值的n，在这种情况下，您迟早会遇到大n的堆栈溢出问题。如果有一种直接的解决方案，你应该优先选择它。虽然我不确定这是否是你实际遇到的问题。（就像我说的：对我来说没什么帮助，但它确实有效。）

- kotarak

---

考虑到这应该解析为圆周率，我不认为那是正确的答案。 ;) - Alex Taggart

@ataggert 你说得有道理。 ;) （小改动：但它可能仍然是原帖作者期望的数字...）（当然，使用(partition 2 1 ...)后，上面的代码就不再适用了。） - kotarak