代码之家 › 专栏 › 技术社区 › Tyler

为什么它不能在恒定的空间中运行(如何使它运行)?

clojure

11

Tyler · 技术社区 · 16 年前

我在做欧拉计划来学习克洛朱尔。

1 到 m

(lcm 10) 退货 2520

这是一种相当残忍的方法。从理论上讲,我们从 米 1 米 把那个数平均地除以。

如果我正确理解“懒惰”的含义(如果我在这里真的很懒惰),那么这个应该在恒定的空间中运行。不需要再多拿一张 1 到 米 从我们循环的无穷多个数字中取一个值。

然而,我得到了一个 java.lang.OutOfMemoryError: Java heap space 米

 (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))))

谢谢!

4 回复 | 直到 11 年前

1

11

MichaÅ Marczyk 16 年前

据我所知,你的代码实际上是懒惰的(也就是说它并不急于得到答案…;-)--但它会产生一堆又一堆的垃圾。想想看 (lvm 17) (range 1 18) . 我无法重现您的内存不足问题,但我初步推测这可能是您的内存问题;GC设置。

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)) 我会很快给你答案。

2

4

j-g-faustus 16 年前

我在Clojure1.1上得到了相同的OutOfMemoryError,但在1.2上没有。

我想这是1.1版本的一个bug for 把多余的垃圾拿着。

3

user85109 user85109 16 年前

虽然我承认这是公认的暴力行为,但我还是不寒而栗。对于最多运行50的连续数字集,lcm为309044504245996706400。你真的想要一个循环来测试到那个点的每个数字来识别集合的lcm吗?

其他的计划似乎要好得多。例如,对序列的每个成员进行因子运算,然后简单地计算每个素因子的最大出现次数。或者,构建一个简单的素数筛,它可以同时对一组数字进行因子运算,同时允许您计算因子的多重性。

4

0

Rob Lachlan 16 年前

迈克尔对这个问题的看法是正确的。筛子会快一点,因为不需要gcd计算:

:这个代码实际上是非常错误的。我把它放在这里是为了提醒自己,如果我宿醉了,就要检查我的工作两次。

(ns euler (:use clojure.contrib.math))

(defn sieve 
  ([m] (sieve m (vec (repeat (+ 1 m) true)) 2))
  ([m sieve-vector factor] 
       (if (< factor m) 
       (if (sieve-vector factor)
           (recur m 
              (reduce #(assoc %1 %2 false)
                  sieve-vector
                  (range (* 2 factor) (+ 1 m) factor))
              (inc factor))
           (recur m sieve-vector (inc factor)))
       sieve-vector)))

(defn primes [m] (map key (filter val (seq (zipmap (range 2 m) (subvec (sieve m)  2))))))

(defn prime-Powers-LCM [m] (zipmap (primes m) (map #(quot m %) (primes m))))

(defn LCM [m] (reduce #(* %1 (expt (key %2) (val %2))) 1 (seq (prime-Powers-LCM m))))