asm*_*asm 6 lisp recursion sbcl common-lisp slime
功能:
给定列表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))))
它永远不会从第二次通话回来.我只能猜测,由于某种原因,我正在为垃圾收集器做一些可怕的事情,但我看不清楚是什么.有没有人有任何想法？
您的代码中错误的一件事是您对 EQ 的使用。EQ 比较身份。
EQ不是用来比较数字的。两个数字的 EQ 可以是 true 也可以是 false。
如果您想按标识、按值或字符进行比较，请使用 EQL。不是情商。
实际上
(remove-if (lambda (x) (eql x item)) list)
只是
(remove item list)
对于您的代码，EQ bug可能意味着在递归调用中调用 permute，而实际上没有从列表中删除数字。
除此之外，我认为 SBCL 只是忙于内存管理。我的 Mac 上的 SBCL 获得了大量内存（超过 1 GB）并且正忙于执行某些操作。一段时间后，计算出结果。
您的递归函数会产生大量“垃圾”。LispWorks 说：1360950192 字节
也许你可以想出一个更有效的实施方案？
更新：垃圾
Lisp 提供了一些自动内存管理，但这并不能让程序员摆脱对空间效应的思考。
Lisp 使用栈和堆来分配内存。堆可能以某些方式为 GC 构建——例如分代、半空间和/或区域。有精确垃圾收集器和“保守”垃圾收集器（Intel 机器上的 SBCL 使用）。
当程序运行时我们可以看到各种效果：
正常的递归过程在堆栈上分配空间。问题：堆栈大小通常是固定的（即使某些 Lisp 可以在错误处理程序中增加堆栈大小）。
程序可能会分配大量内存并返回大量结果。PERMUTE 就是这样一个函数。它可以返回非常大的列表。
程序可以分配内存并暂时使用它，然后垃圾收集器可以回收它。即使程序不使用大量固定内存，创建和销毁的速率也可能非常高。
但还有更多问题。但对于上述每个问题，Lisp 程序员（以及所有其他使用带有垃圾收集的语言实现的程序员）都必须学习如何处理它。
用迭代代替递归。将递归替换为尾递归。
仅返回所需结果的一部分，而不生成完整的解决方案。如果您需要第 n 个排列，则计算该排列而不是所有排列。使用按需计算的惰性数据结构。使用 SERIES 之类的东西，它允许使用类似流但高效的计算。请参阅 SICP、PAIP 和其他高级 Lisp 书籍。
通过资源管理器重用内存。重用缓冲区而不是一直分配对象。使用高效的垃圾收集器，并特别支持收集短暂（短暂）对象。有时，它也可能有助于破坏性地修改对象，而不是分配新对象。
以上处理的是实际程序的空间问题。理想情况下，我们的编译器或运行时基础设施可以提供一些自动支持来处理这些问题。但实际上这并不起作用。大多数 Lisp 系统都提供低级功能来处理这个问题，而 Lisp 提供了可变对象 - 因为现实世界的 Lisp 程序的经验表明，程序员确实希望使用它们来优化他们的程序。如果您有一个计算涡轮叶片形状的大型 CAD 应用程序，那么关于非可变内存的理论/纯粹观点根本不适用 - 开发人员想要更快/更小的代码和更小的运行时占用空间。