clojure - 为什么这不在恒定空间中运行(以及我如何使其如此)？

Question

我正在做 Project Euler 来学习 Clojure。

此函数的目的是从 1 计算整数集的 lcm至 m .
(lcm 10)返回 2520
这是一种相当暴力的方法。理论上，我们从 m 遍历每个数字到无穷大并返回所有值 1 的第一个数字通过 m把这个数字平均分。

如果我正确理解“懒惰”的含义(如果我真的很懒惰)，那么这应该在恒定空间中运行。除了来自 1 的数字列表之外，不需要保存更多的数字。至 m和我们循环遍历的无限数字集中的 1 个值。

但是，我收到了 java.lang.OutOfMemoryError: Java heap space在 m值大于 17。

 (defn lcm [m]
  (let [xs (range 1 (+ m 1))]
  (first (for [x (iterate inc m) :when 
          (empty? 
              (filter (fn [y] (not (factor-of? y x))) xs))] x))))

谢谢!

Answer 1

据我所知，您的代码实际上是懒惰的(从某种意义上说，它并不急于得出答案...... ;-) -- 见下文)，但是它会产生一堆堆的垃圾。只要考虑一下 (lvm 17)相当于在 (range 1 18) 上要求超过 120 万次延迟过滤操作.我无法重现您的内存不足问题，但我暂时推测这可能是您的内存和 GC 设置的问题。

现在虽然我意识到你的问题实际上与算法无关，但请注意所有这些垃圾的产生，所有这些过滤操作的执行等不仅完全破坏了它的空间复杂度，而且还破坏了时间复杂度。为什么不使用实际的 LCM 算法？像一个剥削lcm(X) = gcd(X) / product(X)为 X一组自然数。 GCD 可以用欧几里德算法计算。

(defn gcd
  ([x y]
     (cond (zero? x) y
           (< y x)   (recur y x)
           :else     (recur x (rem y x))))
  ([x y & zs]
     (reduce gcd (gcd x y) zs)))

(defn lcm
  ([x y] (/ (* x y) (gcd x y)))
  ([x y & zs]
     (reduce lcm (lcm x y) zs)))

有了以上内容， (apply lcm (range 1 18))将在短时间内给您答案。