为什么这会炸毁 Lispworks 中的堆？

Question

我正在尝试求解 Problem 14 in Project Euler（找到 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 中导致堆溢出。由于它不优雅地退出，我无法找出发生了什么。实际上，我不明白为什么这会消耗这么多堆space——最大的递归序列是 300 次调用。我是否遗漏了代码中的一些低效率？

欢迎任何意见。对代码的进一步评论也表示赞赏。

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

更新我确实尝试按照 Rainer Joswig 的建议进行编译，但没有帮助。

关于 coredump 和 sds 的评论，or 在这种情况下确实比 if 好，但我不能用散列 table 代替向量，因为 collatz 序列去大约有 50% 的时间。在运行代码之后，散列 table 有大约 250 万个条目。

最后，奇怪的是，我在测试一个较长的循环（一百万次迭代）的语法时设法重现了这个错误，这个循环只是处理了一些变量而根本没有收集任何东西。不幸的是，我丢失了代码——LispWorks 刚刚失败了，唉。我最好的猜测是 LispWorks 的内部存在一些泄漏或其他内存管理故障。

Answer 1

我发现这里有两个低效之处：

您正在使用由连续整数序列索引的散列 table。您可能应该改用（可扩展的）向量。
你的递归不是尾递归；您可能更愿意对其进行优化。

诚然，其中 none 可以解释堆耗尽。

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

我认为每次调用

时都必须调整散列大小 table 可能存在问题

(setf (gethash n collatz))

数字 n 大于当前 table 大小。当您在没有大小参数的情况下调用 make-hash-table 时，系统会选择一个依赖于实现的值。每次超过此值时， table 都必须在执行期间调整大小，这会消耗大量资源并可能导致您提到的崩溃。要解决此问题，您可以使用您知道不会超过的值创建 table：

(defparameter *collatz* (make-hash-table :size 1000000)).

Answer 4

LispWorks just went poof, alas. My best guess is that there's some leak or other memory management glitch in LispWorks' entrails.

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

LW商业版运行没问题

Answer 5

我是运行 LispWorks 7.1.1 64 位 Mac，使用解释器

CL-USER 1 > (defparameter *collatz* (make-hash-table))
*COLLATZ*

CL-USER 2 > (setf (gethash 1 *collatz*) 0)
0

CL-USER 3 > (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 4 > (loop for i from 1 to 1000000 maximize (n-collatz i))

Stack overflow (stack size 15998).
  1 (continue) Extend stack by 50%.
  2 (abort) Return to top loop level 0.

Type :b for backtrace or :c <option number> to proceed.
Type :bug-form "<subject>" for a bug report template or :? for other options.

所以上面显示的是 'stack overflow'，而不是 'heap overflow'。请注意，可以调整堆栈大小并继续。

现在我在新的 LispWorks 中再次尝试，但是编译函数：

CL-USER 1 > (defparameter *collatz* (make-hash-table))
*COLLATZ*

CL-USER 2 > (setf (gethash 1 *collatz*) 0)
0

CL-USER 3 > (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 4 > (compile 'n-collatz)
N-COLLATZ
NIL
NIL

CL-USER 5 > (loop for i from 1 to 1000000 maximize (n-collatz i))
524

编译后的代码工作正常，无需增加堆栈。

为什么这会炸毁 Lispworks 中的堆？

Why does this blow up the heap in Lispworks?

lisp

common-lisp

collatz

lispworks