2

我正在尝试解决Project Euler 中的问题 14（找到 1 到 1000000 之间最长的 Collat​​z 序列）。

我的代码由一个递归的记忆函数组成，用于计算 Collat​​z 序列的长度，然后是一个循环来找到最大值。请看下面的代码：

(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 个人版，它对堆大小施加了限制。

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

关于 coredump 和 sds 的评论，or确实比if这种情况下要好，但我不能用哈希表代替向量，因为 collat​​z 序列大约有 50% 的时间上升。运行代码后，哈希表有大约 250 万个条目。

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

4

5 回答 5

4

一件事是确保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>
于 2015-10-08T17:23:00.817 回答
4

LispWorks 只是失败了，唉。我最好的猜测是 LispWorks 的内脏中存在一些泄漏或其他内存管理故障。

你用的是LW的个人版，有内存限制，这个东西达到了这个限制。它引发了一个对话框，上面写着，然后退出。

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

于 2017-02-28T13:14:25.933 回答
3

我在这里看到两个低效率：

  1. 您正在使用由连续整数序列索引的哈希表。您可能应该改用（可扩展的）向量。

  2. 您的递归不是尾递归；你可能更喜欢优化它。

诚然，这些都不能解释堆耗尽。

于 2015-10-08T16:12:52.130 回答
1

我正在使用解释器在 Mac 上运行 LispWorks 7.1.1 64bit

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.

所以上面显示的是“堆栈溢出”，而不是“堆溢出”。请注意，可以调整堆栈大小并继续。

现在我在一个新的 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

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

于 2019-05-02T12:18:57.697 回答
1

我认为每次调用时都必须调整哈希表的大小可能会出现问题

(setf (gethash n collat​​z ))

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

(defparameter *collatz* (make-hash-table :size 1000000)).
于 2015-10-09T19:50:02.160 回答