我正在做 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))))
谢谢!
最佳答案
据我所知,您的代码实际上是懒惰的(从某种意义上说,它并不急于得出答案...... ;-) -- 见下文),但是它会产生一堆堆的垃圾。只要考虑一下 (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))
将在短时间内给您答案。
关于clojure - 为什么这不在恒定空间中运行(以及我如何使其如此)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3078811/