recursion - sbcl 在第二次调用函数时永远运行

Question

函数:

给定一个列表 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 中使用 SLIME，我还没有做太多的定制。该函数在 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))))

它永远不会从第二次调用中返回。我只能猜测，由于某种原因，我正在对垃圾收集器做一些可怕的事情，但我看不到是什么。有人有什么想法吗？

Answer 1

您的代码中有一个错误是您对 EQ 的使用。情商比较身份。

情商不是用来比较数字的。两个数的 EQ 可以是真也可以是假。

如果您想按身份、按值或字符比较数字，请使用 EQL。不是情商。

其实

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

只是

(remove item list)

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

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

您的递归函数会产生大量“垃圾”。 LispWorks 说:1360950192 字节

也许您可以想出一个更有效的实现方案？

更新:垃圾

Lisp 提供了一些自动内存管理，但这并不能使程序员摆脱对空间效应的思考。

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

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

1. 正常的递归过程在堆栈上分配空间。问题:堆栈大小通常是固定的(即使某些 Lisp 可以在错误处理程序中增加它)。

2. 程序可能会分配大量内存并返回大量结果。 PERMUTE 就是这样一个函数。它可以返回非常大的列表。

3. 一个程序可以分配内存并临时使用它，然后垃圾收集器可以回收它。创建和销毁的速率可能非常高，即使程序不使用大量固定内存也是如此。

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

1. 用迭代代替递归。用尾递归代替递归。

2. 只返回需要的部分结果，不生成完整的解决方案。如果您需要第 n 个排列，则计算该排列而不是所有排列。使用按需计算的惰性数据结构。使用类似于 SERIES 的东西，它允许使用类似流但高效的计算。查看 SICP、PAIP 和其他高级 Lisp 书籍。

3. 使用资源管理器重用内存。重用缓冲区而不是一直分配对象。使用高效的垃圾收集器，特别支持收集临时(短暂的)对象。有时它也可能有助于破坏性地修改对象，而不是分配新对象。

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