Clojure初学者关于堆和垃圾回收的问题

Question

Clojure初学者关于堆和垃圾回收的问题

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)的堆或其他东西。

- Benjie Holson

2

这个问题之前已经在这里得到了回答：https://dev59.com/wHA85IYBdhLWcg3wF_cO 简要回答是 filter 创建了一个惰性序列，并且你正在不断地调用 filter，最终导致堆栈溢出。一个解决方法（正如 dreish 建议的那样）是通过 doall 在每一步中实现序列化。 - user445161

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- dreish · Accepted Answer

我认为问题在于每次递归时，你都会创建一个新的惰性序列，该序列引用上一个序列，因此经过几次迭代后，你将持有一个包含头部的序列的序列，该序列又包含头部的序列，该序列又包含头部的序列。所有中间序列都会填满堆。

虽然编写素数筛法是一项值得练习的任务，但如果您想得到答案，Clojure在其标准库中包含了素数序列：clojure.contrib.lazy-seqs/primes。这个特定的Euler问题的标准解决方案是一个单行代码。

作为样式要点，内部defn不是一个好主意。实际效果与defn在顶层相同，但如果我没有弄错，每次调用getAllPrimes时，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)))

我建议避免使用驼峰命名法。在Clojure中，此函数的标准名称应为get-all-primes。

回到实际问题，为了使您的代码正常工作，最简单的方法是强制每次迭代时对每个序列进行操作，即将您的过滤调用包装在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)))