代码之家 › 专栏 › 技术社区 › asm

sbcl在函数的第二个调用上永远运行

sbcl slime common-lisp lisp recursion

6

asm · 技术社区 · 14 年前

功能:

给定一个列表lst返回列表内容的所有排列,其长度正好为k,如果没有提供,则默认为列表长度。

(defun permute (lst &optional (k (length lst)))
  (if (= k 1)
   (mapcar #'list lst)
   (loop for item in lst nconcing
     (mapcar (lambda (x) (cons item x)) 
             (permute (remove-if (lambda (x) (eq x item)) lst) 
                      (1- k))))))

问题是: 我在和SBCL连接的Emacs中使用黏液,我还没有做过太多的定制。该函数在较小的输入(如lst='(1 2 3 4 5 6 7 8)k=3)上很好地工作,这是它在实践中最常用的。但是,当我连续两次使用大输入调用它时,第二次调用将永远不会返回,并且sbcl甚至不会显示在顶部。这些是repl上的结果:

CL-USER> (time (nth (1- 1000000) (permute '(0 1 2 3 4 5 6 7 8 9))))
Evaluation took:
12.263 seconds of real time
12.166150 seconds of total run time (10.705372 user, 1.460778 system)
[ Run times consist of 9.331 seconds GC time, and 2.836 seconds non-GC time. ]
99.21% CPU
27,105,349,193 processor cycles
930,080,016 bytes consed

(2 7 8 3 9 1 5 4 6 0)
CL-USER> (time (nth (1- 1000000) (permute '(0 1 2 3 4 5 6 7 8 9))))

从第二个电话里就再也不会回来了。我只能猜测,出于某种原因,我对垃圾收集者做了一些可怕的事情,但我看不到。有人有什么想法吗?

3 回复 | 直到 14 年前

1

4

Rainer Joswig Michael Fox 14 年前

代码中的一个错误是使用eq.eq比较身份。

eq不用于比较数字。两个数的eq可以是真的,也可以是假的。

如果要按标识、值或字符比较,请使用eql。不是等式

事实上

(remove-if (lambda (x) (eql x item)) list)

只是

(remove item list)

对于您的代码,eq错误可以意味着在递归调用中调用permute,而实际上没有从列表中删除数字。

除此之外,我认为SBCL只是忙于内存管理。我的Mac上的sbcl获得了大量的内存(超过一GB),正忙着做一些事情。一段时间后,计算出结果。

递归函数生成大量的“垃圾”。lispworks说:1360951922字节

也许你能想出一个更有效的实现方法?

更新: 垃圾

Lisp提供了一些自动的内存管理,但这并不能使程序员不去考虑空间效应。

Lisp同时使用堆栈和堆来分配内存。堆可能以特定的方式为GC构建——例如在代、半空间和/或区域中。有精确的垃圾收集器和“保守”的垃圾收集器(由Intel机器上的sbcl使用)。

当程序运行时,我们可以看到各种效果:

正常的递归过程在堆栈上分配空间。问题:堆栈大小通常是固定的(即使某些lisp可以在错误处理程序中增加它)。
一个程序可能会分配大量的内存并返回大量的结果。排列就是这样一种功能。它可以返回非常大的列表。
程序可以分配内存并临时使用它,然后垃圾收集器可以回收它。即使程序不使用大量的固定内存,创建和销毁的速度也可能非常高。

不过,还有更多的问题。但是对于上面的每一个,Lisp程序员(以及使用垃圾收集的语言实现的每一个其他程序员)都必须学习如何处理这个问题。

用迭代替换递归。用尾部递归替换递归。
只返回结果中需要的部分,而不生成完整的解决方案。如果你需要第n个排列,那么计算它,而不是所有的排列。使用按需计算的惰性数据结构。使用类似于series的东西,它允许使用类似于流但高效的计算。参见SICP、PAIP和其他高级Lisp书籍。
使用资源管理器重新使用内存。重用缓冲区,而不是一直分配对象。使用一个高效的垃圾收集器,特别支持收集短暂(短暂)的对象。有时,它还可以帮助破坏性地修改对象,而不是分配新对象。

上面讨论的是真实程序的空间问题。理想情况下,我们的编译器或运行时基础结构可以提供一些自动支持来处理这些问题。但事实上,这并不真正奏效。大多数Lisp系统都提供了处理这一问题的低级功能,而Lisp提供了可变对象——因为现实世界的Lisp程序的经验表明,程序员确实希望使用它们来优化程序。如果您有一个大型的CAD应用程序来计算涡轮叶片的形状,那么关于不可变内存的理论/纯粹的观点就不适用了——开发人员想要更快/更小的代码和更小的运行时占用空间。

2

Ramarren 14 年前

在大多数平台上,sbcl都使用一代垃圾收集器,这意味着对于收集而言,存活超过一定数量的已分配内存将很少被考虑。对于给定的测试用例,您的算法生成了太多的垃圾,以至于它多次触发GC,以至于实际的结果(显然必须在整个函数运行时生存下来)被保存,也就是说,移动到最后一代,而这一代的收集要么非常少,要么根本不收集。因此,第二次运行将在32位系统的标准设置上耗尽堆(512 MB,可以通过运行时选项增加)。

通过使用 (sb-ext:gc :full t) 。这显然依赖于实现。

3

1

Nietzche-jou 14 年前

从输出的角度看,你看到的是黏液回复,对吗?

尝试更改为“*劣质lisp*”缓冲区,您可能会看到sbcl已下降到ldb(内置的低级调试器)。最有可能的是,您已经成功地打开了调用堆栈。