LISP - 反转列表

Lisp - 反转列表

反转列表中元素的顺序是一项常见任务。Common Lisp 为此提供了两个函数：reverse 和 nreverse。它们达到相同的结果，但在操作方式上存在关键差异：一个安全且非破坏性，另一个快速但具有破坏性。选择正确的一个是权衡安全性和性能的问题。

安全方法：reverse

reverse 函数创建并返回一个新列表，其中包含原始列表的倒序元素。原始列表完全保持不变。

Syntax

(reverse sequence)

Example

(let ((original-list '(a b c d e)))
  (format t "Original List: ~a~%" original-list)

  (let ((reversed-list (reverse original-list)))
    (format t "Reversed List: ~a~%" reversed-list))

  (format t "Original List (after reverse): ~a~%" original-list))

Output

Original List: (A B C D E)
Reversed List: (E D C B A)
Original List (after reverse): (A B C D E)

何时使用 reverse：这应该是你的默认选择。它安全且能防止意外的副作用，这是良好函数式编程的核心原则。除非你遇到了已验证的性能瓶颈，否则请使用它。

破坏性方法：nreverse

nreverse 函数（其中的 ‘n’ 代表 ‘non-consing’ 或 ‘destructive’，即非生成新 cons 单元或破坏性）复用原始列表的内存来创建反转后的列表。这更快，并避免分配新内存，但它会破坏原始列表。调用 nreverse 后，指向原始列表的变量不再有效，不应再使用。

Syntax

(nreverse sequence)

Example

(let ((my-list '(a b c d e)))
  (format t "Original List: ~a~%" my-list)

  ; 破坏性地反转列表。我们必须捕获返回值。
  (setf my-list (nreverse my-list))

  (format t "List after nreverse: ~a~%" my-list))

Output

Original List: (A B C D E)
List after nreverse: (E D C B A)

何时使用 nreverse：在性能关键的代码中使用它，当你确定原始列表不再需要时。常见的做法是先构建一个列表（以正向顺序构建效率很高），然后在最后对其进行 nreverse 以获得所需顺序，从而避免垃圾回收开销。

警告：nreverse 的危险

nreverse 的破坏性特点如果不小心使用，可能会导致令人惊讶的 bug。考虑以下两个变量指向相同列表数据的情景：

(let* ((list-a (list 1 2 3))
       (list-b list-a)) ; list-b 是一个别名，不是副本！

  (format t "Before: list-a = ~a, list-b = ~a~%" list-a list-b)

  (setf list-a (nreverse list-a))

  (format t "After:  list-a = ~a, list-b = ~a~%" list-a list-b))

Potential Output

Before: list-a = (1 2 3), list-b = (1 2 3)
After:  list-a = (3 2 1), list-b = (1)

因为 nreverse 修改了底层结构，所以 list-b 现在指向旧列表的一个片段，并且实际上已损坏。这种 bug 可能非常难以追踪。

总结与最佳实践

特点	reverse	nreverse
安全性	安全，非破坏性。	不安全，破坏性。
性能	较慢，分配新内存。	较快，复用现有内存。
原始列表	保持不变。	被破坏，不应再使用。
使用场景	大多数情况下的默认选择。	性能关键代码中，原始列表被丢弃的情况。

黄金法则：当有疑问时，使用 reverse。只有在测量到性能问题并理解其后果时，才优化使用 nreverse。