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

Question

我正在做Project Euler来学习Clojure.

该功能的目的是从计算整数集的LCM 1来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)相当于要求超过120万个懒惰过滤操作(range 1 18).我无法重现您的内存不足问题,但我暂时猜测它可能是您的内存和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))将在短时间内给您答案.