时间戳

首页 > 解决方案 > 这个 Common Lisp 代码是否与 Winston / Horn 在 LISP 3rd Edition 中所教的内容相似/相等？

list - 这个 Common Lisp 代码是否与 Winston / Horn 在 LISP 3rd Edition 中所教的内容相似/相等？

问题描述

他们这么说

(defun user-reverse (l)
  (if (endp l)
      nil
      (append (user-reverse (rest l))
              (list (first l)))))

由于 n(n + 1)/2 的计算，这很糟糕。

然后他们说走这条路：

(defun user-reverse (l &optional result)
  (if (endp l)
      result
      (user-reverse (rest l)
                    (cons (first l) result))))

所以我在想，为什么你不能这样做：

(defun user-reverse (l)
  (do ((new-list nil))
      ((endp l) new-list)
    (push (pop l) new-list)))

这是一个坏习惯还是什么？或者它是否复制列表或其他内容？他们在前几章教“DO”，想知道是否有任何 LISPers 可以说出这是否与他们的榜样相当或更差，或者与他们的榜样不同？基本上，想知道他们的坏'n'例子是如何站起来的？

标签： listtime-complexitylispcommon-lispreverse

解决方案

有两个问题：

  • 算法和数据结构的复杂性和效率
  • 递归与循环

让我们首先看一下复杂性/效率问题。

Lisp 中的列表是 cons 单元格的单链表或空列表。因此，天真的追加到列表的末尾是一项昂贵的操作。在 Lisp 列表中，将元素添加到列表的前面很便宜，而将元素添加到列表的末尾则很昂贵。因此，应该编写一个例程，使其不使用这些昂贵的操作。

如果我们有一个像第一个使用代价高昂的附加操作的递归例程，我们希望找到一个不同的例程，它不会添加到列表的末尾。这就是为什么第二个例程优于第一个例程的原因。

递归与循环

您发布的第二个版本是结束递归的。递归调用可以用两个变量的跳转和更新来代替。这使用尾调用优化(TCO)。在 Lisp 中，这是一种优化，通常编译器可以做到。但是他们不需要这样做，基于解释器的实现通常不需要这样做。在 Scheme 中，语言定义要求实现支持 TCO。

使用 TCO，第二个版本既使用高效操作又在恒定空间中运行（不过，它分配了一个反向列表）。

没有 TCO，第二个版本使用高效的操作，但可能会导致大型列表的堆栈溢出。

环形

第三个版本使用循环 - 这里DO。它既使用高效的运算符，又仅受内存大小的限制。它不受堆栈大小的限制，因为它不进行任何递归调用。

通常在 Lisp 中的实际软件（-> 不是为了教学目的而编写的）中，人们会发现使用循环的代码，因为 TCO 并非在所有实现中普遍可用。例如，Common Lisp 的 ABCL 实现在 Java 虚拟机 (JVM) 上运行。由于 JVM 不提供直接功能来实现 TCO，因此 JVM 的编程语言实现通常不提供 TCO。ABCL 也不例外。

多列表

循环版本可以写成dolist：

(defun user-reverse (l &aux r)
  (dolist (e l r)
    (push e r)))

推荐阅读