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

我试图解决Problem 14 in Project Euler（有1个和1000000之间最长的在Collatz序列）。为什么这会炸毁Lispworks中的堆？

我的代码由递归，memoized函数来计算在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 我曾尝试编译为赖Joswig建议，但它并没有帮助。

关于coredump和sds的评论，在这种情况下or确实比if更好，但我无法用哈希表替换矢量，因为collatz序列在大约50％的时间内上升。运行代码后，哈希表有大约250万个条目。

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

来源

2015-10-08 Paulo Mendes

我不能重现溢出（这里没有Lispworks）;我只能说'（如果X X Y）'也写成'（或X Y）' – coredump

您是否在使用LispWorks个人版？如果是这样，那么请记住，散列表通常在具有大量未使用插槽的阵列上实现，因此您的散列表可能会增长到足以使LispWorks个人版在其堆限制上爆炸，随后其签名提示退出而无法恢复。 – acelent

更新：我确实按照Rainer Joswig的建议尝试编译，但它没有帮助。我想知道是否有任何方法让Lispworks更积极地编译东西。 –

我看到这里有两个效率低下：

您使用的是一个连续的整数序列索引的哈希表。你应该使用一个（可扩展的）向量。
你的递归是不是尾递归;你可能更喜欢优化它。

不可否认，这些都不能解释堆耗尽。

来源

2015-10-08 16:12:52 sds

有一件事是确保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-08 17:23:00

我觉得可能是一个问题，有每次调用

（SETF（gethash N次来调整哈希表collatz））

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

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

来源

2015-10-09 19:50:02 Leo

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

您正在使用LW的个人版本，它具有内存限制，并且这些内容达到此限制。它提出了一个对话，说，然后退出。

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

来源

2017-02-28 13:14:25

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

回答

相关问题