6

功能：

给定一个列表 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))))

它永远不会从第二个电话回来。我只能猜测出于某种原因我对垃圾收集器做了一些可怕的事情，但我看不到是什么。有没有人有任何想法？

4

3 回答 3

4

您的代码中的一件事是您对 EQ 的使用。EQ 比较身份。

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

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

实际上

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

只是

(remove item list)

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

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

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

也许你可以想出一个更有效的实现？

更新：垃圾

Lisp 提供了一些自动内存管理，但这并不能让程序员从考虑空间效应的问题中解脱出来。

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

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

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

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

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

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

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

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

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

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

于 2010-02-25T08:56:29.663 回答
2

大多数平台上的 SBCL 使用分代垃圾收集器，这意味着在回收后存活超过一定数量的分配内存将很少考虑进行回收。您针对给定测试用例的算法生成了如此多的垃圾，以至于它多次触发 GC，以至于实际结果（显然必须在整个函数运行时中存活）是终身的，也就是说，移动到最后一代，它要么很少被收集或者根本没有。因此，在 32 位系统的标准设置下，第二次运行将耗尽堆（512 MB，可以使用运行时选项增加）。

可以通过手动触发收集器来对永久数据进行垃圾收集(sb-ext:gc :full t)。这显然取决于实现。

于 2010-02-25T12:06:42.300 回答
1

从输出的外观来看，您正在查看 slime-repl，对吗？

尝试更改为“*inferior-lisp*”缓冲区，您可能会看到 SBCL 已下降到 ldb（内置低级调试器）。最有可能的是，您已经设法破坏了调用堆栈。

于 2010-02-25T10:56:56.063 回答