clojure - 为什么它不能在恒定的空间中运行(我如何做到这一点呢？)？

我正在做Euler项目来学习Clojure。

此函数的目的是计算从1到m的整数集的lcm。
(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))))

谢谢!

最佳答案

据我所知，您的代码实际上是懒惰的(在某种意义上说，我们并不急于找到答案... ;-)-参见下文)，但是它会一堆又一堆地堆积成堆的垃圾。只需考虑(lvm 17)就要求对(range 1 18)进行超过120万次延迟过滤操作。我无法重现您的内存不足问题，但我暂时推测这可能与您的内存和GC设置有关。

现在，尽管我意识到您的问题实际上与算法无关，但请注意，所有垃圾的产生，所有这些过滤操作的执行等不仅完全破坏了这种方法的空间复杂性，而且还破坏了时间复杂性。为什么不使用实际的LCM算法？就像将lcm(X) = gcd(X) / product(X)用作X一样，它是一组自然数。可以使用Euclid算法计算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))将在短时间内为您提供答案。

关于clojure - 为什么它不能在恒定的空间中运行(我如何做到这一点呢？)？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3078811/