7

我有一个关于 Clojure 的问题：我正在尝试通过Project Euler来学习该语言，但我不明白幕后发生了什么：以下代码旨在使用返回所有素数列表，直到lim. 我认为它在堆空间中应该是 O(n)，因为我列出了所有直到 的数字lim，然后将它们一个一个过滤掉，同时将第一个数字移到一个新列表中。（我知道我实际上每次都在制作新列表，但我认为它们不会占用更多内存？）无论如何我正在运行这个

(defn getAllPrimes [lim] 
  (defn getPrimes [primes numlist]
    (if (not-empty numlist) ;base case;
    (recur (cons (first numlist) primes) ;put the prime on to the prime list 
           (filter
        (fn [x] (not (div? x (first numlist)))) ;remove the prime and all its multiples from the numlist
        (rest numlist)))
      primes)); return the primes
  (getPrimes () (range 2 lim))) ;call the recursive function with and empty prime list to be filled up and a full numlist to be emptied

当我打电话时，我一直在用完堆空间

(apply + (getAllPrimes 2000000))

，但我没有用完空间

(apply + (filter even? (range 2000000)))

所以我认为我一定不明白列表是如何在 recur 调用中被垃圾收集的，并且实际上正在使用 O(n*n) 堆或其他东西。

4

1 回答 1

6

我相信问题在于，每次重复时，您都在创建一个新的惰性序列，该序列引用最后一个，因此经过几次迭代后，您将持有一个 seq，该 seq 包含一个 seq 的头部，该头部包含一个 seq 的头部持有 seq 的头部。...所有中间序列都填满了你的堆。

尽管编写素数筛是一项有价值的练习，但如果您想得到答案，Clojure 确实在其标准库中包含素数序列：clojure.contrib.lazy-seqs/primes。这个特定欧拉问题的标准解决方案是单线。

作为风格点，内部定义不是一个好主意。实际效果与 defn 位于顶层相同，但如果我没记错的话，每次调用 getAllPrimes 时都会重新分配 var，并且强烈建议不要在运行时重新定义 var。由于代码只是定义了一个 var，getPrimes 仍然与 getAllPrimes 一样可见。在这种情况下，getPrimes 可以很容易地重写为没有内部函数、匿名或命名的循环/递归。这对你的惰性序列链问题没有帮助，但它确实使代码看起来更标准：

(defn getAllPrimes [lim]
  (loop [primes ()
         numlist (range 2 lim)]
    (if (not-empty numlist)
      (recur (cons (first numlist) primes)
             (filter (fn [x] (not (div? x (first numlist))))
                     (rest numlist)))
      primes)))

我也会避免使用 camelCase。此函数的 Clojure 标准名称是 get-all-primes。

然而，回到实际问题，为了让代码正常工作，您可以做的最少的工作就是在每次迭代中强制每个 seq，即将您的过滤器调用包装在一个 doall 中。我试过这个，虽然它仍然运行缓慢，但它至少运行完成而不会耗尽堆：

(defn get-all-primes [lim]
  (loop [primes ()
         numlist (range 2 lim)]
    (if (not-empty numlist)
      (recur (cons (first numlist) primes)
             (doall (filter #(not (div? % (first numlist)))
                            (rest numlist))))
      primes)))
于 2010-08-11T00:36:27.857 回答