摘要：然而，如果我們的集合列表是按排序順序排列的，那麼通過並行地對每個集合執行單個線性掃描，集合論操作可以僅需 O(n) 即可有效地實現，其中， n 是所有集合中的元素總數。通過兩個棧實現的不同之處在於，現在的項可能會根據我們進行 pop 的方向在 head 和 tail 之間來回推送，這就導致了此類操作的最壞情況的線性複雜性：當前後方向不斷變化時。

本文是本系列文章的第七篇，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)
1
CL-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 中文站翻譯並分享。

相關文章