为什么这会使Lispworks中的堆爆炸呢？

Question

我正在尝试求解Euler项目中的问题14 (找到1到1000000之间最长的Collatz序列)。

我的代码由一个递归的回忆录函数组成，用于计算Collatz序列的长度，然后是一个循环以找到最大值。请参阅以下代码：

(defparameter *collatz* (make-hash-table))
(setf (gethash 1 *collatz*) 0)

(defun n-collatz (n)
  (if (gethash n *collatz*)
      (gethash n *collatz*)
      (setf (gethash n *collatz*)
            (if (evenp n)
                (1+ (n-collatz (/ n 2)))
                (1+ (n-collatz (1+ (* n 3))))))))

(loop for i from 1 to 1000000 maximize (n-collatz i))

这在Clozure中运行良好，但在Lispworks中导致堆溢出。当它不体面地离开时，我不知道发生了什么。实际上，我不明白为什么这会占用这么多堆空间--最大的递归序列是300多个调用。我是不是错过了代码中的一些效率低下的地方？

如有任何意见，我们将不胜感激。对代码的进一步评论也是非常感谢的。

PS:我使用Lispworks个人版，它对堆大小施加了限制。

UPDATE --我确实尝试过像Rainer建议的那样编译，但是没有帮助。

关于coredump和sds的注释，在这种情况下，or确实比if更好，但是我不能用哈希表代替向量，因为collatz序列上升了大约50%。运行代码后，哈希表有大约250万个条目。

最后，奇怪的是，我在测试一个长循环的语法(一百万次迭代)时，成功地再现了这个bug，这个循环只是篡改了一些变量，却什么也没有收集。不幸的是，我丢失了代码--不幸的是，LispWorks刚刚失败了。我最好的猜测是，LispWorks的内部存在一些泄漏或其他内存管理故障。

Answer 1

我在这里看到了两个效率低下的问题：

1. 您正在使用由连续整数序列索引的哈希表。您可能应该使用(可扩展的)向量。
2. 您的递归不是尾递归；您可能更愿意优化它。

诚然，所有这些都不能解释堆耗尽的原因。

Answer 2

一件事是确保编译了n-collatz：

(compile 'n-collatz)

或者通过通常的IDE命令使用编译器。

输入到LispWorks侦听器中的代码将以其他方式解释：

CL-USER 140 > (defun n-collatz (n)
                (if (gethash n *collatz*) (gethash n *collatz*)
                  (setf (gethash n *collatz*)
                        (if (evenp n)
                            (1+ (n-collatz (/ n 2)))
                          (1+ (n-collatz (1+ (* n 3))))))))
N-COLLATZ

CL-USER 141 > #'n-collatz
#<interpreted function N-COLLATZ 40600020CC>

CL-USER 142 > (compile 'n-collatz)
N-COLLATZ
NIL
NIL

CL-USER 143 > #'n-collatz
#<Function N-COLLATZ 4060007054>

Answer 3

唉，LispWorks刚刚喝了一杯。我最好的猜测是，LispWorks的内部存在一些泄漏或其他内存管理故障。

您正在使用的个人版本的LW，它有一个内存限制，而这个东西达到了这个限制。它提出了一个对话，说，然后退出。

LW的商业版本运行它没有任何问题。