通过 Lisp 语言理解编程算法：链表篇（下）-InfoQ

GTLC全球技术领导力峰会·上海站，首批讲师正式上线！了解详情 



 写点什么

本文是本系列文章的第七篇，Lisp（历史上曾拼写为 LISP），是具有悠久历史的计算机编程语言家族，有独特和完全括号的前缀符号表示法。本文旨在通过 Lisp 编程语言理解链表的基本概念，由于原文篇幅较长，InfoQ 通过上下篇的形式进行翻译发布。

先进先出与后进先出

由于列表的灵活性，使它们成为实现许多流行的抽象数据结构的通用选择。

队列

队列或先进先出（FIFO）具有以下接口：

enqueue 末尾的项
dequeue 第一个元素：获取它并将其从队列中删除

它对元素规定了先进先出（FIFO）顺序。队列可以直接用 our-own-list 这样的单向链表来实现。显然，它也可以构建在动态数组之上，但需要对集合进行永久的扩展和收缩，正如我们已经知道的那样，这并不是它们使用的首选场景。

队列结构有许多用途，用于按照特定顺序处理项（其中一些我们将在本书的后续章节中提到）。

栈

栈（stack）或后进先出（LIFO）甚至比队列更简单，并且使用范围更广。它的接口如下：

push，将项推到栈的顶部，使其成为第一个元素
pop 从顶部取出一个项：从栈中获取并将其删除

一个简单的 Lisp 列表可以作为一个栈。你可以在几乎每个带有 Lisp 代码的文件中看到这种用法。最常见的模式是迭代过程中的结果累加：使用栈接口，我们可以用更简单的方式重写 simple-mapcar （即惯用的 Lisp）：

(defun simple-mapcar (fn list)  (let ((rez ()))    (dolist (item list)      (push (call fn item) rez))    (reverse rez)))

复制代码

栈按照相反的时间顺序保存元素，因此可以用来保存更改的历史记录，以便能够撤销它们。编译器在过程调用约定中使用这个特性：存在一个单独的程序内存段，称为栈（stack）段，当函数调用发生时（从程序的入口点开始，在 C 语言中，称为 “main” 函数），所有的参数和局部变量都放在这个栈上，以及调用的程序代码段中的返回地址。这种方法允许存在局部变量，这些局部变量只在调用期间持续，并且相对于当前栈头部被引用，而不像全局变量那样绑定到内存中某个绝对位置。在过程调用返回后，栈将被“展开”（unwound），所有本地数据都将被“遗忘”，从而将上下文返回到调用之前的相同状态。这种基于栈的历史保存是一种非常常见和有用的模式，同样可以在用户代码中使用。

Lisp 本身也使用这一技巧来实现全局变量，它能够通过 let 块的范围获得上下文相关的值：每个这样的变量也有一个与之相关联的值的栈。这是经验丰富的 Lisp 程序员经常使用的 Lisp 语言中最不受重视的特性之一。下面是一个带有标准全局变量的小例子（由于这个特殊属性，在 Lisp 中称之为 special）*standard-output*，它存储对当前输出流的引用：

CL-USER> (print 1)1CL-USER> (let ((*standard-output* (make-broadcast-stream)))           (print 1))1

复制代码

在第一次 print 调用中，我们看到了打印值和返回值，而在第二次调用中，只看到 print 函数的返回值，而它的输出实际上被发送到 /dev/null。

栈也可用于实现队列。我们需要它们中的两个来做这件事：一个用于对项进行入队操作，一个用于对项进行出队操作。实现如下：

(defstruct queue  head  tail)
(defun enqueue (item queue)  (push item @queue.head))
(defun dequeue (queue)  ;; Here and in the next condition, we use the property that an empty list  ;; is also logically false. This is discouraged by many Lisp style-guides,  ;; but, in many cases, such code is not only more compact but also more clear.  (unless @queue.tail    (do ()        ((null @queue.head))  ; this loop continues until head becomes empty      (push (pop @queue.head) @queue.tail)))      ;; By pushing all the items from the head to the tail we reverse      ;; their order — this is the second reversing that cancels the reversing      ;; performed when we push the items to the head and it restores the original order.  (when @queue.tail    (values (pop @queue.tail)            t)))  ; this second value is used to indicate that the queue was not empty
CL-USER> (let ((q (make-queue)))           (print q)           (enqueue 1 q)           (enqueue 2 q)           (enqueue 3 q)           (print q)           (dequeue q)           (print q)           (enqueue 4 q)           (print q)           (dequeue q)           (print q)           (dequeue q)           (print q)           (dequeue q)           (print q)           (dequeue q))#S(QUEUE :HEAD NIL :TAIL NIL) #S(QUEUE :HEAD (3 2 1) :TAIL NIL) #S(QUEUE :HEAD NIL :TAIL (2 3)) #S(QUEUE :HEAD (4) :TAIL (2 3)) #S(QUEUE :HEAD (4) :TAIL (3)) #S(QUEUE :HEAD (4) :TAIL NIL) #S(QUEUE :HEAD NIL :TAIL NIL) NIL  ; no second value indicates that the queue is now empty

复制代码

这种队列实现对于 enqueue/dequeue 仍然有 O(1) 的操作时间。每个元素将经历 4 次操作：2 次 push 操作和 2 次 pop 操作（用于 head 和 tail）。

另一种基于栈的结构是具有最小元素的栈，即某种结构不仅按后进先出顺序来保存元素，而且还跟踪其中的最小元素。挑战在于，如果我们只是添加包含当前最小值的 min 槽，当这个最小值从栈中进行 pop操作时，我们需要检查所有剩余的元素来找到新的最小值。我们可以通过添加另一个栈来避免这种额外的工作：最小值栈。现在，每个 push 和 pop 操作都要求我们也检查第二个栈的头部，如果添加或删除的元素恰好是最小值，就相应地将其进行 push 操作推送到最小值栈或从那里对其进行 pop 操作。

演示栈用法的著名算法是完全带括号的算术表达式求值：

(defun arith-eval (expr)  "EXPR is a list of symbols that may include:   square brackets, arithmetic operations, and numbers."  (let ((ops ())        (vals ())        (op nil))    (dolist (item expr)      (case item        ([ ) ; do nothing        ((+ - * /) (push item ops))        (] (:= op (pop ops)               val (pop vals))           (case op             (+ (:+ val (pop vals)))             (- (:- val (pop vals)))             (* (:* val (pop vals)))             (/ (:/ val (pop vals))))           (push val vals))        (otherwise (push item vals))))    (pop vals)))
CL-USER> (arith-eval '([ 1 + [ [ 2 + 3 ] * [ 4 * 5 ] ] ] ]))101

复制代码

双端队列

Deque 是双端队列（double-ended queue）的简写，可以同时按两种顺序进行遍历：先进先出和后进先出。它有 4 个操作：push-front 和 push-back（也称为 shift），pop-front 和 pop-back（也称为 unshift）。这种结构可以用双向链表实现，也可以用两个栈的简单队列来实现。通过两个栈实现的不同之处在于，现在的项可能会根据我们进行 pop 的方向在 head 和 tail 之间来回推送，这就导致了此类操作的最坏情况的线性复杂性：当前后方向不断变化时。

这种结构的用例是同时利用直接和反向排序的算法：一个典型的例子是工作窃取算法（job-stealing algorithms），当主工作器从前面处理队列时，而其他工作器在空闲时，可能会从后面窃取优先级最低的项（将同一工作发生冲突的可能性降至最低）。

栈的实际运用：SAX 解析

对于处理不同数据集的人来说，自定义的 XML 解析是一项常见的任务，因为许多数据集都是 XML 格式的，例如 Wikipedia 和其他维基数据资源。XML 解析主要有两种方法：

DOM 解析读取整个文档，并在内存中创建其树表示。这种技术对小型文档来说很方便，但是对于大型文档来说，比如 Wikipedia 的转储文档，它很快就会填满所有可用的内存。此外，如果你只想从深树结构中提取一些特定的部分，那么处理深树结构也不是很方便。
SAX 解析是使用流方法的另一种变体。解析器读取文档，并在完成特定部分的处理后，调用相关的回调：读取打开标记、关闭标记以及读取当前元素的内容时应该做什么。这些操作发生在每个标记上，我们可以将整个过程看作是利用所谓的“访问者模式”遍历文档树：当访问每个节点时，我们有机会在开始、中间和结束后做出反应。

一旦你习惯了 SAX 解析，由于它的简单性，它就会成为处理 XML、JSON 和其他支持类似流解析方法的格式的首选工具。通常，最简单的解析模式就足够了：记住我们正在查看的标记，当它匹配一组有趣的标记时，处理其内容。然而，有时候我们需要根据更广泛的背景下作出决定。例如，假设我们将文本标记成段落，这些段落被拆分成句子，这些句子又被标记出来。为了处理这样的三级结构，通过 SAX 解析，我们可以使用以下大纲（利用 CXML 库原语）：

(defclass text-sax (sax:sax-parser-mixin)  ((parags :initform nil :accessor sax-parags)   (parag :initform nil :accessor sax-parag)   (sent :initform nil :accessor sax-sent)   (tag :initform nil :accessor sax-tag)))
(defmethod sax:start-element ((sax text-sax)                              namespace-uri local-name qname attrs)  (declare (ignore namespace-uri qname attrs))  (:= (sax-tag sax) (mkeyw local-name))
(defmethod sax:end-element ((sax text-sax)                            namespace-uri local-name qname)  (declare (ignore namespace-uri qname))  (with-slots (tag parags sent) sax    (case tag      (:paragraph (push (reverse parag) parags)                  (:= parag nil))      (:sentence (push (reverse sent) parag)                 (:= sent nil)))))
(defmethod sax:characters ((sax text-sax) text)  (when (eql :token (sax-tag sax))    (push text (sax-sent sax)))
(defmethod sax:end-document ((sax text-sax))  (reverse (sax-parags sax)))

复制代码

这段代码将返回 sax:end-document 方法中段落的累积结构，以及两个栈：当前句子和当前段落用于在解析时积累中间数据。以类似的方式，如果有必要，还可以使用另一个栈遇到的标记来精确地跟踪我们在文档树中的位置。总体而言，你使用 SAX 解析的次数越多，就越会意识到栈足以解决 99% 的挑战。

列表作为集合

另一个非常重要的抽象数据结构是集合（set）。这是一个集合，无论我们将每个元素添加多少次，它都只保存一次。这种结构可用于各种情况：当我们需要跟踪已经看到和处理的项时；当我们想要计算元素组之间的关系时；等等。

基本上，它的接口由集合论操作组成：

添加 / 删除项
检查项是否在集合中
检查一个集合是否为另一个集合的子集
并集（union）、交集（intersection）、差集（difference）等等

集合有一个有趣的方面，即元素操作（add/remove/member）和集合操作（union/…）的有效实现，需要使用不同的具体数据结构，因此，应该根据主要用例做出选择。实现集合的一种方法是使用链表。Lisp 对此有标准的库支持，包括一下函数：

adjoin，如果项不在列表中，则将其添加到列表中
member ，检查项在集合中是否存在
subsetp，用于子集关系查询
union、intersection、set-difference 和 set-exclusive-or，用于集合操作

这种方法适用于小型集合（最多几十个元素），但通常效率相当低。向集合中添加项或检查成员资格需要 O(n)的操作，而在哈希集合（我们将在关于键值结构的章节中讨论），这些操作都是 O(1) 操作。union 和其他集合论操作的简单实现将需要 O(n^2)，因此我们必须将一个集合中的每个元素与另一个集合中的每个元素进行比较。然而，如果我们的集合列表是按排序顺序排列的，那么通过并行地对每个集合执行单个线性扫描，集合论操作可以仅需 O(n) 即可有效地实现，其中，n 是所有集合中的元素总数。使用哈希集也会导致同样的复杂性。

下面是在排序列表上构建的数字集合的 union的简化实现：

(defun sorted-union (s1 s2)  (let ((rez ()))    (do ()        ((and (null s1) (null s2)))      (let ((i1 (first s1))            (i2 (first s2)))        (cond ((null i1) (dolist (i2 s2)                           (push i2 rez))                         (return))              ((null i2) (dolist (i1 s1)                           (push i1 rez))                         (return))              ((= i1 i2) (push i1 rez)                         (:= s1 (rest s1)                             s2 (rest s2)))              ((< i1 i2) (push i1 rez)                         (:= s1 (rest s1)))              ;; just T may be used instead              ;; of the following condition              ((> i1 i2) (push i2 rez)                         (:= s2 (rest s2))))))    (reverse rez)))
CL-USER> (sorted-union '(1 2 3)                       '(0 1 5 6))(0 1 2 3 5 6)

复制代码

这种方法甚至对于基于未排序列表的集合也很有用，因为排序只是一种 O(n * log n) 操作。更好的是，当用例主要需对集合进行集合论操作，而 changes/membership 查询的数量相对较少时，最有效的技术可能是始终对列表进行排序。

归并排序

谈到排序，我们在前一章讨论的数组排序算法，对于列表而言效率并不高，因为它们是基于交换操作的，在列表的情况下是 O(n)。因此，需要另一种方法，目前存在一些有效的列表排序算法，其中最突出的是归并排序（merge sort）。它的工作原理是将列表拆分为两个相等的部分，直到我们得到简单的单元素列表，然后将排序后的列表合并到更大的排序列表中。正如我们在前面的示例中看到的那样，排序列表的合并过程是高效的。这种方法的一个很好的特点是它的稳定性，即在合并过程中得到适当的实现，那么它将保留相等元素的原始顺序。

(defun merge-sort (list comp)  (if (null (rest list))      list      (let ((half (floor (length list) 2)))        (merge-lists (merge-sort (subseq seq 0 half) comp)                     (merge-sort (subseq seq half) comp)                     comp))))
(defun merge-lists (l1 l2 comp)  (let ((rez ())    (do ()        ((and (null l1) (null l2)))      (let ((i1 (first l1))            (i2 (first l2)))        (cond ((null i1) (dolist (i l2)                           (push i rez))                         (return))              ((null i2) (dolist (i l1)                           (push i rez))                         (return))              ((call comp i1 i2) (push i1 rez)                                 (:= l1 (rest l1)))              (t (push i2 rez)                 (:= l2 (rest l2))))))    (reverse rez)))

复制代码

与二分查找相同的复杂度分析也适用于该算法。在递归树的每一层，我们都执行 O(n) 操作：每个元素被推入结果列表一次，反转一次，并且最多有 4 次比较操作：3 次空检查和 1 次 comp 函数的调用。我们还需要在 subseq 操作中对每个元素执行一次复制，并在递归下降时获取列表的长度（尽管它可以被记住并作为函数调用参数传递）。每个元素的操作总数不超过 10 个，这是一个常量。正如我们已经知道的，树的高度是 (log n 2)。因此，总复杂度为 O(n * log n)。

现在，让我们来测量这种排序所需的实时时间，并将其与数据一章中的 prod-sort （使用最佳数组访问器）的时间进行比较：

CL-USER> (with ((lst (random-list 10000))                (vec (make-array 10000 :initial-contents lst)))           (print-sort-timings "Prod" 'prod-sort vec)           (print-sort-timings "Merge " 'merge-sort lst))= Prodsort of random vector =Evaluation took:  0.048 seconds of real time= Prodsort of sorted vector =Evaluation took:  0.032 seconds of real time= Prodsort of reverse sorted vector =Evaluation took:  0.044 seconds of real time= Merge sort of random vector =Evaluation took:  0.007 seconds of real time= Merge sort of sorted vector =Evaluation took:  0.007 seconds of real time= Merge sort of reverse sorted vector =Evaluation took:  0.008 seconds of real time

复制代码

有趣的是，结果发现，归并排序比快速排序要快 5 倍左右，尽管似乎每一次递归所需的操作数至少是快速排序的 2~3 倍。为什么我们得到这样的结果，这留给读者作为练习：我将从分析函数调用开始，看看大部分时间浪费在哪里。

很明显，merge-lists 过程的工作方式与我们在前面讨论过的排序列表上的集合论操作相类似。事实上，它是在 Lisp 标准库中提供的。使用标准的 merge，归并排序可以用完全函数的方式编写，也可以用通用的方式支持来任何类型的序列：

(defun merge-sort (seq comp)  (if (or (null seq)  ; avoid expensive length calculation for lists          (<= (length seq) 1))      seq      (let ((half (floor (length seq) 2)))        (merge (type-of seq)               (merge-sort (subseq seq 0 half) comp)               (merge-sort (subseq seq half) comp)               comp))))

复制代码

与数组排序函数相比，归并排序还有一个本质上的区别：它不是原位排序的。因此，它还需要 O(n * log n) 额外的空间来保存每次迭代产生的半个子列表。对它们进行排序和原位合并是不可能的。有一些方法可以在一定程度上减少这种额外的空间使用，但不能完全消除它。

归并排序的并行化

然而，如果我们考虑对这一过程实现并行化的问题，归并排序的额外空间缺点可能就会变得无关紧要。任何算法的并行实现的一般思想，都是以这样一种方式分割工作，即允许减少与执行这些工作的工作器成比例的运行时间。在理想的情况下，如果我们有 m 个工作器，并能够均匀地分配工作，那么运行时间应该能减少到原来的 1/m。对于归并排序，这将意味着只有 O(n/m * log n)。然而，这种理想的减少并不总是可以实现的，因为算法中经常存在瓶颈，需要所有或部分工作器等待其中一个完成工作。

下面是一个简单的归并排序并行化的实现，它使用了 eager-future2 库，该库基于 Lisp 实现的多线程功能，增加了高级数据并行能力：

(defun parallel-merge-sort (seq comp)  (if (or (null seq) (<= (length seq) 1))      seq      (with ((half (floor (length seq) 2))             (thread1 (eager-future2:pexec                       (merge-sort (subseq seq 0 half) comp)))             (thread2 (eager-future2:pexec                       (merge-sort (subseq seq half) comp))))        (merge (type-of seq)               (eager-future2:yield thread1)               (eager-future2:yield thread2)                              comp))))

复制代码

eager-future2:pexec 过程将每个 merge-sort 提交给线程池，该线程池管理系统中可用的多个 CPU 线程，并继续执行，而不等待它返回。而 eager-future2:yield 将暂停执行，直到执行适当的 merge-sort 线程返回为止。

当我用 4 路处理器机器上以串行和并行的方式执行归并排序来运行测试函数时，我得到了以下结果：

CL-USER> (with ((lst1 (random-list 10000))                (lst2 (copy-list lst1)))           (print-sort-timings "Merge " 'merge-sort lst1)           (print-sort-timings "Parallel Merge " 'parallel-merge-sort lst2))= Merge sort of random vector =Evaluation took:  0.007 seconds of real time  114.29% CPU= Merge sort of sorted vector =Evaluation took:  0.006 seconds of real time  116.67% CPU= Merge sort of reverse sorted vector =Evaluation took:  0.007 seconds of real time  114.29% CPU= Parallel Merge sort of random vector =Evaluation took:  0.003 seconds of real time  266.67% CPU= Parallel Merge sort of sorted vector =Evaluation took:  0.003 seconds of real time  266.67% CPU= Parallel Merge sort of reverse sorted vector =Evaluation took:  0.005 seconds of real time  220.00% CPU

复制代码

速度提高了大约 2 倍，这也反应 CPU 利用率从大约 100%（即 1 个 CPU）上升到 250%。这些数字是正确的，因为归并排序过程仍然是以串行方式执行的，并且仍然是瓶颈。在归并排序的并行化中，还有更为复杂的方法可以实现最佳的 m 倍加速，但鉴于它们的复杂性，我们不会在本书赘述。

列表与 Lisp

历史上，Lisp 的名称起源于 “List Processing”（列表处理）的缩写，这既表明了列表在 Lisp 语言早期发展中的重要性，也表明了灵活性（列表的一个主要特征）始终是其设计的基石。为什么列表对 Lisp 很重要？也许，最初，它与该语言本身的数据结构的可用性和良好支持有关吧。但是，很快焦点转移到这样一个事实上：与其他语言不同，Lisp 代码在编译器中不是以自定义的基于字符串的格式输入的，而是以嵌套列表的形式输入的，这种嵌套列表直接表示语法树。再加上对列表数据结构的卓越出众的支持性，它为代码本身的编程处理打开了无数的可能性，这些代码在红系统、代码遍历程序和生成器等中都有体现。所以，“List Processing”（列表处理）原本并不是关于数据列表，而是关于代码列表，它完美地描述了这种语言的主要特征……

脚注：

[1] 而在 Lisp 机器中，cons 单元甚至有特殊的硬件支持，这样的改变会使它变得毫无用处。

[2] 但是，对于结构来说，如果这能起作用的话，这是依赖于实现的。在主要的实现中，它将会起作用。

作者介绍：

Vsevolod Dyomkin，Lisp 程序员，居住在乌克兰基辅。精通乌克兰语、俄语和英语。目前正在撰写关于 Lisp 的书籍 Programming Algorithms in Lisp，该书将使用 CC BY-NC-ND 许可（创作公用许可协议），供公众免费阅读。

原文链接：

LISP, THE UNIVERSE AND EVERYTHING

本系列文章最初发布于 Vesvolod Dyomkin 的 Blogger 博客，经原作者授权，由 InfoQ 中文站翻译并分享。

相关文章：

《通过 Lisp 语言理解编程算法：简介和复杂度》

《通过 Lisp 语言理解编程算法：Lisp 速成课程》

《通过 Lisp 语言理解编程算法：数据结构篇》