此前，InfoQ 已經翻譯並分享了本系列的前兩章：《簡介和複雜度》、《Lisp 速成課程》，現在，我們即將介紹數據結構。數據結構（data structure）是計算機中存儲、組織數據的方式。數據結構意味着接口或封裝：一個數據結構可被視爲兩個函數之間的接口，或者是由數據類型聯合組成的存儲內容的訪問方法封裝。在本章中，我們將闡述 Lisp 中的數據結構。

在接下來的幾章中，我們將描述每種編程語言提供的基本數據結構、它們的用法以及與之相關的最重要算法。我們將從數據結構和元組或結構的概念開始，它們是最原始、最基本的概念。

數據結構與算法

讓我們從一個有點抽象的問題開始：算法和數據結構，哪個更重要？

從一個角度來看，算法是許多程序的本質，而數據結構似乎是次要的。此外，儘管大多數算法依賴於特定數據結構的某些特性，但並非所有算法都依賴這些特性。數據結構依賴算法的好例子是堆排序（Heapsort）、使用二叉查找樹（Binary Search Tree，BST）搜索、並查集（union-find）。而第二種是：Erastophenes 篩選法（埃拉托色尼篩選法，簡稱艾氏篩法）和一致哈希（consistent hashing）。

與此同時，一些經驗豐富的開發人員指出，當找到正確的數據結構時，算法幾乎會“自動”地編寫出來。Linux 之父 Linus Torvalds 曾經 表示 ：

爛程序員關心的是代碼。好程序員關心的是數據結構和它們之間的關係。（ Bad programmers worry about the code. Good programmers worry about data structures and their relationships. ）

Eric S. Raymond 在《UNIX 編程藝術》（ Art of Unix Programming ）一書中，對同一個想法提出了不那麼尖銳的版本，稱之爲“ 表示原則 ”（Rule of Representation）：

把知識疊入數據以求邏輯質樸而健壯。

即時最簡單的程序邏輯讓人類來驗證也很困難，但是就算是很複雜的數據，對人類來說，還是相對容易地就能夠推導和建模的。不信可以試試比較一下，是五十個節點的指針樹，還是五十行代碼的流程圖更清楚明瞭；或者，比較一下究竟用一個數組初始化器來表示轉換表，還是用 switch 語句更清楚明瞭呢？可以看出，不同的方式在透明性和清晰性方面具有非常顯著的差別。

數據要比編程邏輯更容易駕馭。所以接下來，如果要在複雜數據和複雜代碼中選擇一個，寧願選擇前者。更進一步，在設計中，你應該主動將代碼的複雜性轉移到數據之中去。

數據結構比算法更爲靜態。當然，它們中的大多數都允許隨着時間的推移而改變它們的內容，但是總有某些不變量存在。這允許通過簡單的歸納進行推理：只考慮兩種（或至少少數），即基本情況和一般情況。換句話說，數據架構基本上不再考慮時間的概念，並且隨着時間而變化是導致程序複雜性的主要原因之一。也就是說，數據結構是聲明性的，而大多數算法是命令式的。聲明性方法的優點是，你無需想象（追蹤）隨時間流動會發生什麼樣的變化。

因此，本書像大多數關於該主題的其他書籍一樣，也是圍繞數據結構組織的。大多數章節介紹了一個特定的結構、屬性和接口，並解釋了與之相關的算法，展示了它的實際用例。然而，一些重要的算法並不需要特定的數據結構，因此，也有幾個章節專門對它們進行討論。

數據結構概念

在數據結構中，實際上有兩種不同的類型：抽象和具體。它們之間的顯著區別在於，抽象結構只是一個接口（一組操作）和一些必須滿足的條件或不變量。它們的特定實現由具體的數據結構提供，這些實現可能在效率特性和內部機制方面存在顯著的差異。例如，抽象數據結構隊列（queue）只有兩個操作： enqueue 將項目添加到隊列的末尾， dequeue 在開頭獲取一個項目並將其從隊列中刪除。還有一個約束條件，即項目應該按照它們入列的相同順序出列。現在，隊列可以使用許多不同的底層數據結構來實現：鏈表或雙鏈表、數組或樹。每一個都具有不同的效率特性和隊列接口之外的附加屬性。我們將在書中討論這兩種類型，重點放在具體結構上，並解釋它們在實現特定抽象接口時的用法。

近年來，“數據結構”這一術語，已經有些失寵了，在面向對象的函數式編程範例或類的上下文中，通常被概念上更爲豐富的類型概念所取代。然而，對於本書來說，這兩個概念都不僅僅意味着我們只關心算法機制。首先，在算法的上下文中，它們還區分了所有無顯著差異的原始值（數字、字符等）。此外，類形成繼承的層次結構，而類型與範疇論（category theory）的代數規則相關聯。因此，在本書中，我們將解釋使用中性的數據結構術語，並在適當情況下偶爾提及其他變體。

譯註：範疇論（category theory），是數學的一門學科，以抽象的方法來處理數學概念，將這些概念形式化成一組組的“對象”及“態射”。範疇最容易理解的一個例子爲集合範疇，其對象爲集合，態射爲集合間的函數。但需注意，範疇的對象不一定要是集合，態射也不一定要是函數；一個數學概念若可以找到一種方法，以符合對象及態射的定義，則可形成一個有效的範疇，且所有在範疇論中導出的結論都可應用在這個數學概念之上。

相連數據結構與鏈接數據結構

當前的計算機體系結構由中央處理器（CPU）、存儲器和外圍輸入輸出設備組成。數據通過 I/O 設備，存儲在內存中，由 CPU 進行處理，以某種方式與外界進行交換。還有一個關鍵的約束因素，稱爲馮諾依曼瓶頸：即 CPU 只能處理存儲在有限數量的特殊基本內存塊（稱爲寄存器）中的數據。因此，它必須不斷地在寄存器和主存儲器之間來回移動數據元素（使用中間緩存來加快該過程）。現在，有些東西可以放入寄存器，有些則不能。第一個被稱爲原語（primitive），主要是將那些可以直接用整數表示的項聯合起來：整數 、浮點數、字符。所有需要自定義數據結構來表示的所有內容都不能作爲一個整體放入寄存器中。

另一個適用於處理器寄存器的項目是內存地址。實際上，有一個重要的常量：通用寄存器中的位數，它定義了特定 CPU 可以處理的最大內存地址，從而定義了它可以處理的最大內存量。對 32 位架構來說，它是 2^32 （4GB）；對於 64 位架構來說，你已經猜到了，它是 2^64 。內存地址通常稱爲 指針 （pointer），如果你將指針存放在寄存器中，那麼有一些命令允許 CPU 從它指向的位置檢索內存中的數據。

因此，有兩種方法可以將數據結構放入內存中：

• 相連 （contiguous）結構佔用單個內存塊，其內容存儲在相鄰的內存塊中。要訪問特定的塊，我們應該知道它從分配給該結構的內存範圍開始的偏移量。（這通常由編譯器處理）。當處理器需要讀寫這一塊時，它將使用指針，該指針作爲結構的基址和偏移量之和來計算。相連結構的例子是數組和結構。
• 相反，鏈接結構不佔用相連的內存塊，即其內容位於不同的位置。這意味着只想特定塊的指針不能預先計算，應該存儲在結構本身中。這種結構更加靈活，但在訪問某個元素所用的空間和時間方面都會增加額外的開銷（當有嵌套時，可能需要多個躍點，而在相連結構中，它始終是常量）。存在大量鏈接數據結構，如列表、樹和圖。

元組

在大多數語言中，一些常見的數據結構（如數組或列表）是“內置”的，但是，如果我們追根究底的話，就會發現，它們的工作方式大多與任何用戶定義的數據結構基本相同。爲了實現任意的數據結構，這些語言提供了一種稱爲記錄、結構、對象等的特殊機制。它的正確名稱應該是“元組”（tuple）。它是由許多字段組成的數據結構，每個字段包含一個原始值（primitive value）、另一個元組或指向任何類型的另一個元組的指針。這樣，元組和表示任何結構，包括嵌套結構和遞歸結構。在類型論的背景下，這種結構被稱爲“產品類型”（product types）。

元組是一個抽象的數據結構，它唯一的接口是字段訪問器函數（field accessor function）：按名稱（命名元組）或索引（匿名元組）。它可通過多種方式實現，但最好使用具有常量時間訪問的相連變體。然而，在許多語言中，尤其是動態語言中，程序員經常使用列表或動態數組來創建一次性的 Ad-hoc 元組。

譯註：Ad-hoc 是拉丁文常用短語中的一個短語。這個短語的意思是“特設的、特定目的的（地）、即席的、臨時的、將就的、專案的”。這個短語通常用來形容一些特殊的、不能用於其它方面的的，爲一個特定的問題、任務而專門設定的解決方案。

Python 有一個專用的元組數據類型，通常就是爲了這個目的，它本質上是一個鏈接數據結構。下面的 Python 函數將返回一個十進制的元組（用括號編寫）和數字 x 的其餘部分：

 複製代碼

def truncate(x):
dec = int(x)
rem = x - dec
return (dec,rem)

這是一種簡單且效率不高的方法，當字段數量較少且結構的生命週期較短時，這種方法可能會發揮作用。然而，從效率和代碼清晰性的角度來看，一個更好的方法是使用預定義的結構。在 Lisp 中，元組被稱爲 “struct”，由 defstruct 定義，默認情況下，使用相連表示（儘管有一個選項可以使用底層的鏈表）。下面是一個簡單的成對數據結構（simple pair data structure）的定義（在 Lisp 中稱爲“slot”），它有兩個字段： left 和 right 。

 複製代碼

(defstructpair
left right)

這個 defstruct 宏，實際上，生成了若干個定義：結構類型的構造函數，被稱爲 make-pair ，並具有 2 個關鍵字參數： :left 和 :right 以及字段訪問器： pair-left 和 pair-right 。此外，結構常見的 print-object 方法將適用於我們的新結構，還可以使用 reader-macro （讀取宏）從打印表單中恢復它。以下代碼展示了它們是如何組合在一起的：

 複製代碼

CL-USER> (make-pair:left"foo":right"bar")
#S(PAIR:LEFT"foo":RIGHT"bar")
CL-USER> (pair-right(read-from-string(prin1-to-string*)))
"bar"

prin1-to-string 和 read-from-string 是互補的 Lisp 函數，它們允許以計算機可讀的形式打印值（如果提供了適當的 print-function（打印函數）），並將其讀取回來。理想情況下，良好的 print-representations 對人類和計算機來說都是可讀的，對於代碼透明度非常重要，不應該被忽視。

有一種方法可以對定義的每個部分自定義。例如，如果我們計劃經常使用“成對”（pair），那麼我們可以通過指定 (:conc-name nil) 屬性來省略 pair- 前綴。下面是 RUTILS 的一個改進的成對定義和它的簡化構造函數，我們將在本書中使用它。它使用 :type list 分配來與 destructuring macro （析構宏）集成。

 複製代碼

(defstruct(pair(:typelist) (:conc-namenil))
"A generic pair with left (LT) and right (RT) elements."
lt rt)

(defunpair (xy)
"A shortcut to make a pair of X and Y."
(make-pair:ltx:rty))

在函數調用中傳遞數據結構

最後一點。將數據結構與函數一起使用有兩種方法：要麼通過複製是當的內存區域（ 按值調用 （call-by-value））直接傳遞它們，這種方法通常應用於原始類型（primitive types）；要麼傳遞指針（ 按引用調用 （call-by-reference））。在第一種情況下，被調用函數中原始結構的內容是無法修改的；而在第二種情況下則是可能能夠修改的，因此應該考慮不合理更改的風險。處理這類問題的常用方法是調用任何更改之前製作一個副本，儘管有時原始數據結構可能會發生變化，因此不需要複製。顯然，引用調用方法更爲通用，因爲它允許修改和複製，而且由於複製是按需進行的，因此效率更高。這就是爲什麼在大多數編程語言中，它是處理結構（和對象）的默認方法。然而，在像 C 這樣的低級語言中，這兩種變體都得到了支持。此外，在 C++ 中，引用傳遞（pass-by-reference）有兩種類型：傳遞指針並傳遞實際上所謂的引用，這是指針上的語法糖，它允許使用非指針語法（點而不是箭頭）訪問參數，並添加了一些限制。但是，不管特定語言的特性如何，總的觀點都是一樣的。

作用中的結構：並查集

數據結構有不同的形狀和風格。在這裏，我想提到一個特殊而有趣的例子，在某種程度上，它既是數據結構又是算法。甚至連名稱也涉及到了某些操作，而不是靜態形式。大多數更高級的數據結構都有這樣的一個特徵，即它們不僅由形狀和排列來定義，還通過一組適用的操作集來定義。並查集（Union-Find）是一組數據結構的算法，可用於有效確定隨時間變化的集合中的集合成員。它們可用於查找網絡中不相交的部分、檢測圖中的循環、查找最小生成樹等等。這類問題的實例之一就是自動圖像分割：將圖像的不同部分、汽車與背景、癌細胞與正常細胞相分離。

譯註：並查集（Union-Find），顧名思義就是有 “合併集合” 和 “查找集合中的元素” 兩種操作的關於數據結構的一種算法。它主要涉及兩種基本操作：合併和查找。這說明，初始時並查集中的元素是不相交的，經過一系列的基本操作 (Union)，最終合併成一個大的集合。而在某次合併之後，有一種合理的需求：某兩個元素是否已經處在同一個集合中了？因此就需要 Find 操作。

讓我們考慮以下問題：如何確定圖中的兩點之間是否存在一條路徑？假設一個圖是一組點（頂點）和這些點中的某些點對之間的邊。圖中的路徑是從源到目的地的一系列點，每一對點都有一條連接它們的邊。如果兩個點之間存在某條路徑，則它們屬於同一個分量，否則，則屬於兩個不相交的分量。

包含三個不想交分量的圖。

對於兩個任意點，如何確定它們是否存在連接路徑？簡單的實現可能採用其中一種方法，並開始構建所有可能的路徑（這可以以廣度優先或深度優先的方式進行，甚至是隨機的）。無論如何，這樣的過程通常需要一些步驟，與圖的頂點數量成正比。我們可以做得更好嗎？這是一個常見的問題，它會讓我們得到更高效的算法。

並查集方法基於這樣一個簡單的想法：添加項時，記錄它們所屬組件的 ID。但如何確定這個 ID 呢？使用與此子集中的某個點關聯的 ID，如果該點位於其自身的子集中，則使用當前點的 ID。如果子集已經形成了呢？沒問題，我們可以通過迭代每個頂點，並以連接到的任意點的 ID 作爲子集的 ID 來模擬添加過程。下面是這種方法的實現（爲了簡化代碼，我們將使用指向 point 結構的指針，而不是 ID，但是，從概念上來說，它們是相同的）：

 複製代碼

(defstructpoint
parent); if the parent is null the point is the root

(defunuf-union (point1point2)
"Join the subsets of POINT1 and POINT2."
(:=(point-parentpoint1) (or(point-parentpoint2)
point2)))

(defunuf-find (point)
"Determine the id of the subset that a POINT belongs to."
(let((parent(point-parentpoint)))
(ifparent
(uf-findparent)
point)))

只需調用 (make-point) 就會向我們的集合中添加一個包含單個項的新子集。

注意， uf-find 使用遞歸來查找子集的根，即首先添加的點。因此，對於每個頂點，我們存儲一些中間數據，並且爲了獲得子集 ID，每次我們都要執行額外的計算。這樣，我們設法減少了平均情況下的查找時間，但仍然沒有完全排除它需要遍歷集合中的每個元素的可能性。這種所謂的“退化”情況，可能表現爲每個項目是參照以前添加的項目。也就是說，只有一個子集，它的成員鏈像這樣連接到下一個子集： a -> b -> c -> d 。如果我們在 a 上調用 uf-find ，它必須枚舉集合中的所有元素。

然而，有一種方法可以改進 uf-find 行爲：通過壓縮樹的深度，使所有點沿着路徑到它的根點，也就是說，將每個鏈壓縮成深度爲 1 的寬淺型的樹。

 複製代碼

d
^^^
| | |
a b c

不幸的是，對於整個子集，我們不能立即這樣做，但是，在每次 uf-find 運行期間，我們可以壓縮一條路徑，這也會縮短子樹中植根於其上的點的所有路徑！儘管如此，這還不能保證不會有足夠多的結合序列，使樹長得比發現的樹還要快，能把樹“壓扁”。但是還有另一個調整，結合了路徑壓縮，可以確保兩個操作的次線性（sublinear）（實際上，幾乎是恆定的）時間：跟蹤所有樹的大小，並將較小的樹鏈接到較大的樹下面。浙江確保所有的樹的高度都低於 (log n) 。嚴格證明這一點是相當複雜的，儘管如此，但憑直覺來看，我們可以通過觀察基本情況看出這種趨勢。如果我們加上二元樹和一元樹，我們仍然會得到高度爲 2 的樹。

下面是優化版本的實現代碼：

 複製代碼

(defstructpoint
parent
(size1))

(defunuf-find (point)
(let((parent(point-parentpoint)))
(ifparent
;; here, we use the fact that the assignment will also return
;; the value to perform both path compression and find
(:=(point-parentpoint) (uf-findparent))
point)))

(defunuf-union (point1point2)
(with((root1(uf-findpoint1))
(root2(uf-findpoint2))
(majorminor (if(>(point-sizeroot1)
(point-sizeroot2))
(valuesroot1 root2)
(valuesroot2 root1))))
(:+(point-sizemajor) (point-sizeminor))
(:=(point-parentminor) major)))

在這裏，Lisp 的多個值很方便，可以簡化代碼。有關它們的更多細節，請參見腳註 [1]。

所提出的方法在實現上相當簡單，但在複雜性分析上卻很複雜。因此，我只能給出最後的結果： m 並查集操作，使用樹加權和路徑壓縮，在一組 n 個對象執行 O((m + n) log* n) （其中， log* 是迭代對數：一個增長非常緩慢的函數，在實際應用上，可以被認爲是一個常數）。

最後，如果 O(n) 中幾乎所有的點都不屬於同一子集（其中 n 是要檢查的點的數量 [2]，所以 O(1) 就是兩個點），這種情況該如何檢查呢？請看以下示例代碼：

 複製代碼

(defunuf-disjoint (points)
"Return true if all of the POINTS belong to different subsets."
(let(roots)
(dolist(pointpoints)
(let((root(uf-findpoint)))
(when(memberroot roots)
(return-fromuf-disjointnil))
(pushroot roots))))
t)

從這個簡單的例子中可以得出更多的結論：

1. 我們最初的想法並不總是完美無缺的。檢查邊緣情況是否存在潛在問題是很重要的。
2. 我們已經目睹了一個壓根就不存在的數據結構示例：信息片段分佈在各個數據點上。有時，可以選擇以集中的方式將信息存儲在專用結構（如哈希表之類）中，或者將其分佈存儲在各個節點上。後一種方法通常更優雅，也更有效，儘管它並不是那麼明顯。

腳註：

[1] 此外，Python 有專門的語法來析構這類元組： dec, rem = truncate(3.14) 。但是，這並不是處理從函數返回一次值和一個或多個二次值的最佳方法。所有必需的值都是通過 value 表單返回： (values dec rem) ，可以用 (multiple-value-bind (dec rem) (truncate 3.14) ...) 或 (with ((dec rem (truncate 3.14))) ...) 來檢索。它更優雅，因爲可以通過通常方式調用函數來隨意丟棄二次值： (+ 1 (truncate 3.14)) => 4 ：在 Python 中是不可能的，因爲你不能用某個東西對元組進行求和。

[2] 實際上，這裏的複雜度是 O(n^2) ，這是由於使用了在 O(n) 中執行集合成員測試的函數 member ，但這對整個概念來說並不重要。如果期望使用數十個或數百個點調用 uf-disjoint ，那麼跟結構必須更改爲具有 O(1) 成員操作的哈希集。

作者介紹：

Vsevolod Dyomkin，Lisp 程序員，居住在烏克蘭基輔。精通烏克蘭語、俄語和英語。目前正在撰寫關於 Lisp 的書籍 Programming Algorithms in Lisp，該書將使用 CC BY-NC-ND 許可（創作公用許可協議），供公衆免費閱讀。

原文鏈接：

LISP, THE UNIVERSE AND EVERYTHING

本系列文章最初發佈於 Vesvolod Dyomkin 的 Blogger 博客，經原作者授權，由 InfoQ 中文站翻譯並分享。

相關文章