數(shù)據(jù)結(jié)構(gòu)(data structure)是計(jì)算機(jī)中存儲(chǔ)、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)意味著接口或封裝：一個(gè)數(shù)據(jù)結(jié)構(gòu)可被視為兩個(gè)函數(shù)之間的接口，或者是由數(shù)據(jù)類型聯(lián)合組成的存儲(chǔ)內(nèi)容的訪問(wèn)方法封裝。在本章中，我們將闡述 Lisp 中的數(shù)據(jù)結(jié)構(gòu)。

 

 

在接下來(lái)的幾章中，我們將描述每種編程語(yǔ)言提供的基本數(shù)據(jù)結(jié)構(gòu)、它們的用法以及與之相關(guān)的最重要算法。我們將從數(shù)據(jù)結(jié)構(gòu)和元組或結(jié)構(gòu)的概念開(kāi)始，它們是最原始、最基本的概念。

 

 

數(shù)據(jù)結(jié)構(gòu)與算法

讓我們從一個(gè)有點(diǎn)抽象的問(wèn)題開(kāi)始：算法和數(shù)據(jù)結(jié)構(gòu)，哪個(gè)更重要?

從一個(gè)角度來(lái)看，算法是許多程序的本質(zhì)，而數(shù)據(jù)結(jié)構(gòu)似乎是次要的。此外，盡管大多數(shù)算法依賴于特定數(shù)據(jù)結(jié)構(gòu)的某些特性，但并非所有算法都依賴這些特性。數(shù)據(jù)結(jié)構(gòu)依賴算法的好例子是堆排序(Heapsort)、使用二叉查找樹(shù)(Binary Search Tree，BST)搜索、并查集(union-find)。而第二種是：Erastophenes 篩選法(埃拉托色尼篩選法，簡(jiǎn)稱艾氏篩法)和一致哈希(consistent hashing)。

譯注：

堆排序(Heapsort)是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹(shù)的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于(或者大于)它的父節(jié)點(diǎn)。

二叉查找樹(shù)(Binary Search Tree)，也稱二叉搜索樹(shù)、有序二叉樹(shù)(ordered binary tree)，排序二叉樹(shù)(sorted binary tree)。二叉查找樹(shù)相比于其他數(shù)據(jù)結(jié)構(gòu)的優(yōu)勢(shì)在于查找、插入的時(shí)間復(fù)雜度較低。為 O(log n)。二叉查找樹(shù)是基礎(chǔ)性數(shù)據(jù)結(jié)構(gòu)，用于構(gòu)建更為抽象的數(shù)據(jù)結(jié)構(gòu)，如集合、multiset、關(guān)聯(lián)數(shù)組等。

并查集，計(jì)算機(jī)科學(xué)中，并查集是一種樹(shù)型的數(shù)據(jù)結(jié)構(gòu)，其保持著用于處理一些不相交集合(Disjoint Sets)的合并及查詢問(wèn)題。

埃拉托色尼篩選法 (sieve of Erastophenes)，也稱素?cái)?shù)篩。這是一種簡(jiǎn)單且歷史悠久的篩法，用來(lái)找出一定范圍內(nèi)所有的素?cái)?shù)。它是列出所有小素?cái)?shù)最有效的方法之一，其名字來(lái)自于古希臘數(shù)學(xué)家埃拉托斯特尼(Erastophenes)，并且被描述在另一位古希臘數(shù)學(xué)家尼科馬庫(kù)斯(Nicomachus)所著的《算術(shù)入門(mén)》(Introduction to Arithmetic)中。

一致哈希 (consistent hashing), 由 MIT 的 Karger 及其合作者提出，現(xiàn)在這一思想已經(jīng)擴(kuò)展到其它領(lǐng)域。在這篇 1997 年發(fā)表的學(xué)術(shù)論文中介紹了 “一致哈希” 如何應(yīng)用于用戶易變的分布式 Web 服務(wù)中。哈希表中的每一個(gè)代表分布式系統(tǒng)中一個(gè)節(jié)點(diǎn)，在系統(tǒng)添加或刪除節(jié)點(diǎn)只需要移動(dòng) K/n 項(xiàng)。一致哈希的概念還被應(yīng)用于分布式散列表(DHT)的設(shè)計(jì)。DHT 使用一致哈希來(lái)劃分分布式系統(tǒng)的節(jié)點(diǎn)。所有關(guān)鍵字都可以通過(guò)一個(gè)連接所有節(jié)點(diǎn)的覆蓋網(wǎng)絡(luò)高效地定位到某個(gè)節(jié)點(diǎn)。

與此同時(shí)，一些經(jīng)驗(yàn)豐富的開(kāi)發(fā)人員指出，當(dāng)找到正確的數(shù)據(jù)結(jié)構(gòu)時(shí)，算法幾乎會(huì)“自動(dòng)”地編寫(xiě)出來(lái)。Linux 之父 Linus Torvalds 曾經(jīng)表示：

爛程序員關(guān)心的是代碼。好程序員關(guān)心的是數(shù)據(jù)結(jié)構(gòu)和它們之間的關(guān)系。(Bad programmers worry about the code. Good programmers worry about data structures and their relationships.)

Eric S. Raymond 在《UNIX 編程藝術(shù)》(Art of Unix Programming)一書(shū)中，對(duì)同一個(gè)想法提出了不那么尖銳的版本，稱之為“表示原則”(Rule of Representation)：

把知識(shí)疊入數(shù)據(jù)以求邏輯質(zhì)樸而健壯。

即時(shí)最簡(jiǎn)單的程序邏輯讓人類來(lái)驗(yàn)證也很困難，但是就算是很復(fù)雜的數(shù)據(jù)，對(duì)人類來(lái)說(shuō)，還是相對(duì)容易地就能夠推導(dǎo)和建模的。不信可以試試比較一下，是五十個(gè)節(jié)點(diǎn)的指針樹(shù)，還是五十行代碼的流程圖更清楚明了;或者，比較一下究竟用一個(gè)數(shù)組初始化器來(lái)表示轉(zhuǎn)換表，還是用 switch 語(yǔ)句更清楚明了呢?可以看出，不同的方式在透明性和清晰性方面具有非常顯著的差別。

數(shù)據(jù)要比編程邏輯更容易駕馭。所以接下來(lái)，如果要在復(fù)雜數(shù)據(jù)和復(fù)雜代碼中選擇一個(gè)，寧愿選擇前者。更進(jìn)一步，在設(shè)計(jì)中，你應(yīng)該主動(dòng)將代碼的復(fù)雜性轉(zhuǎn)移到數(shù)據(jù)之中去。

數(shù)據(jù)結(jié)構(gòu)比算法更為靜態(tài)。當(dāng)然，它們中的大多數(shù)都允許隨著時(shí)間的推移而改變它們的內(nèi)容，但是總有某些不變量存在。這允許通過(guò)簡(jiǎn)單的歸納進(jìn)行推理：只考慮兩種(或至少少數(shù))，即基本情況和一般情況。換句話說(shuō)，數(shù)據(jù)架構(gòu)基本上不再考慮時(shí)間的概念，并且隨著時(shí)間而變化是導(dǎo)致程序復(fù)雜性的主要原因之一。也就是說(shuō)，數(shù)據(jù)結(jié)構(gòu)是聲明性的，而大多數(shù)算法是命令式的。聲明性方法的優(yōu)點(diǎn)是，你無(wú)需想象(追蹤)隨時(shí)間流動(dòng)會(huì)發(fā)生什么樣的變化。

因此，本書(shū)像大多數(shù)關(guān)于該主題的其他書(shū)籍一樣，也是圍繞數(shù)據(jù)結(jié)構(gòu)組織的。大多數(shù)章節(jié)介紹了一個(gè)特定的結(jié)構(gòu)、屬性和接口，并解釋了與之相關(guān)的算法，展示了它的實(shí)際用例。然而，一些重要的算法并不需要特定的數(shù)據(jù)結(jié)構(gòu)，因此，也有幾個(gè)章節(jié)專門(mén)對(duì)它們進(jìn)行討論。

數(shù)據(jù)結(jié)構(gòu)概念

在數(shù)據(jù)結(jié)構(gòu)中，實(shí)際上有兩種不同的類型：抽象和具體。它們之間的顯著區(qū)別在于，抽象結(jié)構(gòu)只是一個(gè)接口(一組操作)和一些必須滿足的條件或不變量。它們的特定實(shí)現(xiàn)由具體的數(shù)據(jù)結(jié)構(gòu)提供，這些實(shí)現(xiàn)可能在效率特性和內(nèi)部機(jī)制方面存在顯著的差異。例如，抽象數(shù)據(jù)結(jié)構(gòu)隊(duì)列(queue)只有兩個(gè)操作： enqueue 將項(xiàng)目添加到隊(duì)列的末尾，dequeue 在開(kāi)頭獲取一個(gè)項(xiàng)目并將其從隊(duì)列中刪除。還有一個(gè)約束條件，即項(xiàng)目應(yīng)該按照它們?nèi)肓械南嗤�順序出列�，F(xiàn)在，隊(duì)列可以使用許多不同的底層數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)：鏈表或雙鏈表、數(shù)組或樹(shù)。每一個(gè)都具有不同的效率特性和隊(duì)列接口之外的附加屬性。我們將在書(shū)中討論這兩種類型，重點(diǎn)放在具體結(jié)構(gòu)上，并解釋它們?cè)趯?shí)現(xiàn)特定抽象接口時(shí)的用法。

近年來(lái)，“數(shù)據(jù)結(jié)構(gòu)”這一術(shù)語(yǔ)，已經(jīng)有些失寵了，在面向?qū)ο蟮暮瘮?shù)式編程范例或類的上下文中，通常被概念上更為豐富的類型概念所取代。然而，對(duì)于本書(shū)來(lái)說(shuō)，這兩個(gè)概念都不僅僅意味著我們只關(guān)心算法機(jī)制。首先，在算法的上下文中，它們還區(qū)分了所有無(wú)顯著差異的原始值(數(shù)字、字符等)。此外，類形成繼承的層次結(jié)構(gòu)，而類型與范疇論(category theory)的代數(shù)規(guī)則相關(guān)聯(lián)。因此，在本書(shū)中，我們將解釋使用中性的數(shù)據(jù)結(jié)構(gòu)術(shù)語(yǔ)，并在適當(dāng)情況下偶爾提及其他變體。

譯注： 范疇論(category theory)，是數(shù)學(xué)的一門(mén)學(xué)科，以抽象的方法來(lái)處理數(shù)學(xué)概念，將這些概念形式化成一組組的“對(duì)象”及“態(tài)射”。范疇最容易理解的一個(gè)例子為集合范疇，其對(duì)象為集合，態(tài)射為集合間的函數(shù)。但需注意，范疇的對(duì)象不一定要是集合，態(tài)射也不一定要是函數(shù);一個(gè)數(shù)學(xué)概念若可以找到一種方法，以符合對(duì)象及態(tài)射的定義，則可形成一個(gè)有效的范疇，且所有在范疇論中導(dǎo)出的結(jié)論都可應(yīng)用在這個(gè)數(shù)學(xué)概念之上。

相連數(shù)據(jù)結(jié)構(gòu)與鏈接數(shù)據(jù)結(jié)構(gòu)

當(dāng)前的計(jì)算機(jī)體系結(jié)構(gòu)由中央處理器(CPU)、存儲(chǔ)器和外圍輸入輸出設(shè)備組成。數(shù)據(jù)通過(guò) I/O 設(shè)備，存儲(chǔ)在內(nèi)存中，由 CPU 進(jìn)行處理，以某種方式與外界進(jìn)行交換。還有一個(gè)關(guān)鍵的約束因素，稱為馮諾依曼瓶頸：即 CPU 只能處理存儲(chǔ)在有限數(shù)量的特殊基本內(nèi)存塊(稱為寄存器)中的數(shù)據(jù)。因此，它必須不斷地在寄存器和主存儲(chǔ)器之間來(lái)回移動(dòng)數(shù)據(jù)元素(使用中間緩存來(lái)加快該過(guò)程)�，F(xiàn)在，有些東西可以放入寄存器，有些則不能。第一個(gè)被稱為原語(yǔ)(primitive)，主要是將那些可以直接用整數(shù)表示的項(xiàng)聯(lián)合起來(lái)：整數(shù) 、浮點(diǎn)數(shù)、字符。所有需要自定義數(shù)據(jù)結(jié)構(gòu)來(lái)表示的所有內(nèi)容都不能作為一個(gè)整體放入寄存器中。

另一個(gè)適用于處理器寄存器的項(xiàng)目是內(nèi)存地址。實(shí)際上，有一個(gè)重要的常量：通用寄存器中的位數(shù)，它定義了特定 CPU 可以處理的最大內(nèi)存地址，從而定義了它可以處理的最大內(nèi)存量。對(duì) 32 位架構(gòu)來(lái)說(shuō)，它是 2^32(4GB);對(duì)于 64 位架構(gòu)來(lái)說(shuō)，你已經(jīng)猜到了，它是 2^64。內(nèi)存地址通常稱為指針(pointer)，如果你將指針存放在寄存器中，那么有一些命令允許 CPU 從它指向的位置檢索內(nèi)存中的數(shù)據(jù)。

因此，有兩種方法可以將數(shù)據(jù)結(jié)構(gòu)放入內(nèi)存中：

相連(contiguous)結(jié)構(gòu)占用單個(gè)內(nèi)存塊，其內(nèi)容存儲(chǔ)在相鄰的內(nèi)存塊中。要訪問(wèn)特定的塊，我們應(yīng)該知道它從分配給該結(jié)構(gòu)的內(nèi)存范圍開(kāi)始的偏移量。(這通常由編譯器處理)。當(dāng)處理器需要讀寫(xiě)這一塊時(shí)，它將使用指針，該指針作為結(jié)構(gòu)的基址和偏移量之和來(lái)計(jì)算。相連結(jié)構(gòu)的例子是數(shù)組和結(jié)構(gòu)。

相反，鏈接結(jié)構(gòu)不占用相連的內(nèi)存塊，即其內(nèi)容位于不同的位置。這意味著只想特定塊的指針不能預(yù)先計(jì)算，應(yīng)該存儲(chǔ)在結(jié)構(gòu)本身中。這種結(jié)構(gòu)更加靈活，但在訪問(wèn)某個(gè)元素所用的空間和時(shí)間方面都會(huì)增加額外的開(kāi)銷(當(dāng)有嵌套時(shí)，可能需要多個(gè)躍點(diǎn)，而在相連結(jié)構(gòu)中，它始終是常量)。存在大量鏈接數(shù)據(jù)結(jié)構(gòu)，如列表、樹(shù)和圖。

元組

在大多數(shù)語(yǔ)言中，一些常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)(如數(shù)組或列表)是“內(nèi)置”的，但是，如果我們追根究底的話，就會(huì)發(fā)現(xiàn)，它們的工作方式大多與任何用戶定義的數(shù)據(jù)結(jié)構(gòu)基本相同。為了實(shí)現(xiàn)任意的數(shù)據(jù)結(jié)構(gòu)，這些語(yǔ)言提供了一種稱為記錄、結(jié)構(gòu)、對(duì)象等的特殊機(jī)制。它的正確名稱應(yīng)該是“元組”(tuple)。它是由許多字段組成的數(shù)據(jù)結(jié)構(gòu)，每個(gè)字段包含一個(gè)原始值(primitive value)、另一個(gè)元組或指向任何類型的另一個(gè)元組的指針。這樣，元組和表示任何結(jié)構(gòu)，包括嵌套結(jié)構(gòu)和遞歸結(jié)構(gòu)。在類型論的背景下，這種結(jié)構(gòu)被稱為“產(chǎn)品類型”(product types)。

元組是一個(gè)抽象的數(shù)據(jù)結(jié)構(gòu)，它唯一的接口是字段訪問(wèn)器函數(shù)(field accessor function)：按名稱(命名元組)或索引(匿名元組)。它可通過(guò)多種方式實(shí)現(xiàn)，但最好使用具有常量時(shí)間訪問(wèn)的相連變體。然而，在許多語(yǔ)言中，尤其是動(dòng)態(tài)語(yǔ)言中，程序員經(jīng)常使用列表或動(dòng)態(tài)數(shù)組來(lái)創(chuàng)建一次性的 Ad-hoc 元組。

譯注： Ad-hoc 是拉丁文常用短語(yǔ)中的一個(gè)短語(yǔ)。這個(gè)短語(yǔ)的意思是“特設(shè)的、特定目的的(地)、即席的、臨時(shí)的、將就的、專案的”。這個(gè)短語(yǔ)通常用來(lái)形容一些特殊的、不能用于其它方面的的，為一個(gè)特定的問(wèn)題、任務(wù)而專門(mén)設(shè)定的解決方案。

Python 有一個(gè)專用的元組數(shù)據(jù)類型，通常就是為了這個(gè)目的，它本質(zhì)上是一個(gè)鏈接數(shù)據(jù)結(jié)構(gòu)。下面的 Python 函數(shù)將返回一個(gè)十進(jìn)制的元組(用括號(hào)編寫(xiě))和數(shù)字 x 的其余部分：

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

這是一種簡(jiǎn)單且效率不高的方法，當(dāng)字段數(shù)量較少且結(jié)構(gòu)的生命周期較短時(shí)，這種方法可能會(huì)發(fā)揮作用。然而，從效率和代碼清晰性的角度來(lái)看，一個(gè)更好的方法是使用預(yù)定義的結(jié)構(gòu)。在 Lisp 中，元組被稱為 “struct”，由 defstruct 定義，默認(rèn)情況下，使用相連表示(盡管有一個(gè)選項(xiàng)可以使用底層的鏈表)。下面是一個(gè)簡(jiǎn)單的成對(duì)數(shù)據(jù)結(jié)構(gòu)(simple pair data structure)的定義(在 Lisp 中稱為“slot”)，它有兩個(gè)字段： left 和 right。

(defstruct pair
left right)

這個(gè) defstruct 宏，實(shí)際上，生成了若干個(gè)定義：結(jié)構(gòu)類型的構(gòu)造函數(shù)，被稱為 make-pair，并具有 2 個(gè)關(guān)鍵字參數(shù)：:left 和 :right 以及字段訪問(wèn)器：pair-left 和 pair-right。此外，結(jié)構(gòu)常見(jiàn)的 print-object 方法將適用于我們的新結(jié)構(gòu)，還可以使用 reader-macro (讀取宏)從打印表單中恢復(fù)它。以下代碼展示了它們是如何組合在一起的：

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 是互補(bǔ)的 Lisp 函數(shù)，它們?cè)试S以計(jì)算機(jī)可讀的形式打印值(如果提供了適當(dāng)?shù)?print-function(打印函數(shù)))，并將其讀取回來(lái)。理想情況下，良好的 print-representations 對(duì)人類和計(jì)算機(jī)來(lái)說(shuō)都是可讀的，對(duì)于代碼透明度非常重要，不應(yīng)該被忽視。

有一種方法可以對(duì)定義的每個(gè)部分自定義。例如，如果我們計(jì)劃經(jīng)常使用“成對(duì)”(pair)，那么我們可以通過(guò)指定 (:conc-name nil) 屬性來(lái)省略 pair- 前綴。下面是 RUTILS 的一個(gè)改進(jìn)的成對(duì)定義和它的簡(jiǎn)化構(gòu)造函數(shù)，我們將在本書(shū)中使用它。它使用 :type list 分配來(lái)與 destructuring macro (析構(gòu)宏)集成。

(defstruct (pair (:type list) (:conc-name nil))
"A generic pair with left (LT) and right (RT) elements."
lt rt)

(defun pair (x y)
"A shortcut to make a pair of X and Y."
(make-pair :lt x :rt y))

在函數(shù)調(diào)用中傳遞數(shù)據(jù)結(jié)構(gòu)

最后一點(diǎn)。將數(shù)據(jù)結(jié)構(gòu)與函數(shù)一起使用有兩種方法：要么通過(guò)復(fù)制是當(dāng)?shù)膬?nèi)存區(qū)域(按值調(diào)用(call-by-value))直接傳遞它們，這種方法通常應(yīng)用于原始類型(primitive types);要么傳遞指針(按引用調(diào)用(call-by-reference))。在第一種情況下，被調(diào)用函數(shù)中原始結(jié)構(gòu)的內(nèi)容是無(wú)法修改的;而在第二種情況下則是可能能夠修改的，因此應(yīng)該考慮不合理更改的風(fēng)險(xiǎn)。處理這類問(wèn)題的常用方法是調(diào)用任何更改之前制作一個(gè)副本，盡管有時(shí)原始數(shù)據(jù)結(jié)構(gòu)可能會(huì)發(fā)生變化，因此不需要復(fù)制。顯然，引用調(diào)用方法更為通用，因?yàn)樗�允許修改和復(fù)制，而且由于復(fù)制是按需進(jìn)行的，因此效率更高。這就是為什么在大多數(shù)編程語(yǔ)言中，它是處理結(jié)構(gòu)(和對(duì)象)的默認(rèn)方法。然而，在像 C 這樣的低級(jí)語(yǔ)言中，這兩種變體都得到了支持。此外，在 C++ 中，引用傳遞(pass-by-reference)有兩種類型：傳遞指針并傳遞實(shí)際上所謂的引用，這是指針上的語(yǔ)法糖，它允許使用非指針語(yǔ)法(點(diǎn)而不是箭頭)訪問(wèn)參數(shù)，并添加了一些限制。但是，不管特定語(yǔ)言的特性如何，總的觀點(diǎn)都是一樣的。

作用中的結(jié)構(gòu)：并查集

數(shù)據(jù)結(jié)構(gòu)有不同的形狀和風(fēng)格。在這里，我想提到一個(gè)特殊而有趣的例子，在某種程度上，它既是數(shù)據(jù)結(jié)構(gòu)又是算法。甚至連名稱也涉及到了某些操作，而不是靜態(tài)形式。大多數(shù)更高級(jí)的數(shù)據(jù)結(jié)構(gòu)都有這樣的一個(gè)特征，即它們不僅由形狀和排列來(lái)定義，還通過(guò)一組適用的操作集來(lái)定義。并查集(Union-Find)是一組數(shù)據(jù)結(jié)構(gòu)的算法，可用于有效確定隨時(shí)間變化的集合中的集合成員。它們可用于查找網(wǎng)絡(luò)中不相交的部分、檢測(cè)圖中的循環(huán)、查找最小生成樹(shù)等等。這類問(wèn)題的實(shí)例之一就是自動(dòng)圖像分割：將圖像的不同部分、汽車(chē)與背景、癌細(xì)胞與正常細(xì)胞相分離。

譯注： 并查集(Union-Find)，顧名思義就是有 “合并集合” 和 “查找集合中的元素” 兩種操作的關(guān)于數(shù)據(jù)結(jié)構(gòu)的一種算法。它主要涉及兩種基本操作：合并和查找。這說(shuō)明，初始時(shí)并查集中的元素是不相交的，經(jīng)過(guò)一系列的基本操作 (Union)，最終合并成一個(gè)大的集合。而在某次合并之后，有一種合理的需求：某兩個(gè)元素是否已經(jīng)處在同一個(gè)集合中了?因此就需要 Find 操作。

讓我們考慮以下問(wèn)題：如何確定圖中的兩點(diǎn)之間是否存在一條路徑?假設(shè)一個(gè)圖是一組點(diǎn)(頂點(diǎn))和這些點(diǎn)中的某些點(diǎn)對(duì)之間的邊。圖中的路徑是從源到目的地的一系列點(diǎn)，每一對(duì)點(diǎn)都有一條連接它們的邊。如果兩個(gè)點(diǎn)之間存在某條路徑，則它們屬于同一個(gè)分量，否則，則屬于兩個(gè)不相交的分量。

 

 

包含三個(gè)不想交分量的圖。

對(duì)于兩個(gè)任意點(diǎn)，如何確定它們是否存在連接路徑?簡(jiǎn)單的實(shí)現(xiàn)可能采用其中一種方法，并開(kāi)始構(gòu)建所有可能的路徑(這可以以廣度優(yōu)先或深度優(yōu)先的方式進(jìn)行，甚至是隨機(jī)的)。無(wú)論如何，這樣的過(guò)程通常需要一些步驟，與圖的頂點(diǎn)數(shù)量成正比。我們可以做得更好嗎?這是一個(gè)常見(jiàn)的問(wèn)題，它會(huì)讓我們得到更高效的算法。

并查集方法基于這樣一個(gè)簡(jiǎn)單的想法：添加項(xiàng)時(shí)，記錄它們所屬組件的 ID。但如何確定這個(gè) ID 呢?使用與此子集中的某個(gè)點(diǎn)關(guān)聯(lián)的 ID，如果該點(diǎn)位于其自身的子集中，則使用當(dāng)前點(diǎn)的 ID。如果子集已經(jīng)形成了呢?沒(méi)問(wèn)題，我們可以通過(guò)迭代每個(gè)頂點(diǎn)，并以連接到的任意點(diǎn)的 ID 作為子集的 ID 來(lái)模擬添加過(guò)程。下面是這種方法的實(shí)現(xiàn)(為了簡(jiǎn)化代碼，我們將使用指向 point 結(jié)構(gòu)的指針，而不是 ID，但是，從概念上來(lái)說(shuō)，它們是相同的)：

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

(defun uf-union (point1 point2)
"Join the subsets of POINT1 and POINT2."
(:= (point-parent point1) (or (point-parent point2)
point2)))

(defun uf-find (point)
"Determine the id of the subset that a POINT belongs to."
(let ((parent (point-parent point)))
(if parent
(uf-find parent)
point)))

只需調(diào)用 (make-point) 就會(huì)向我們的集合中添加一個(gè)包含單個(gè)項(xiàng)的新子集。

注意，uf-find 使用遞歸來(lái)查找子集的根，即首先添加的點(diǎn)。因此，對(duì)于每個(gè)頂點(diǎn)，我們存儲(chǔ)一些中間數(shù)據(jù)，并且為了獲得子集 ID，每次我們都要執(zhí)行額外的計(jì)算。這樣，我們?cè)O(shè)法減少了平均情況下的查找時(shí)間，但仍然沒(méi)有完全排除它需要遍歷集合中的每個(gè)元素的可能性。這種所謂的“退化”情況，可能表現(xiàn)為每個(gè)項(xiàng)目是參照以前添加的項(xiàng)目。也就是說(shuō)，只有一個(gè)子集，它的成員鏈像這樣連接到下一個(gè)子集： a -> b -> c -> d。如果我們?cè)?a 上調(diào)用 uf-find ，它必須枚舉集合中的所有元素。

然而，有一種方法可以改進(jìn) uf-find 行為：通過(guò)壓縮樹(shù)的深度，使所有點(diǎn)沿著路徑到它的根點(diǎn)，也就是說(shuō)，將每個(gè)鏈壓縮成深度為 1 的寬淺型的樹(shù)。

d
^ ^ ^
| | |
a b c

不幸的是，對(duì)于整個(gè)子集，我們不能立即這樣做，但是，在每次 uf-find 運(yùn)行期間，我們可以壓縮一條路徑，這也會(huì)縮短子樹(shù)中植根于其上的點(diǎn)的所有路徑!盡管如此，這還不能保證不會(huì)有足夠多的結(jié)合序列，使樹(shù)長(zhǎng)得比發(fā)現(xiàn)的樹(shù)還要快，能把樹(shù)“壓扁”。但是還有另一個(gè)調(diào)整，結(jié)合了路徑壓縮，可以確保兩個(gè)操作的次線性(sublinear)(實(shí)際上，幾乎是恒定的)時(shí)間：跟蹤所有樹(shù)的大小，并將較小的樹(shù)鏈接到較大的樹(shù)下面。浙江確保所有的樹(shù)的高度都低于 (log n) 。嚴(yán)格證明這一點(diǎn)是相當(dāng)復(fù)雜的，盡管如此，但憑直覺(jué)來(lái)看，我們可以通過(guò)觀察基本情況看出這種趨勢(shì)。如果我們加上二元樹(shù)和一元樹(shù)，我們?nèi)匀粫?huì)得到高度為 2 的樹(shù)。

下面是優(yōu)化版本的實(shí)現(xiàn)代碼：

(defstruct point
parent
(size 1))

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

(defun uf-union (point1 point2)
(with ((root1 (uf-find point1))
(root2 (uf-find point2))
(major minor (if (> (point-size root1)
(point-size root2))
(values root1 root2)
(values root2 root1))))
(:+ (point-size major) (point-size minor))
(:= (point-parent minor) major)))

在這里，Lisp 的多個(gè)值很方便，可以簡(jiǎn)化代碼。有關(guān)它們的更多細(xì)節(jié)，請(qǐng)參見(jiàn)腳注 [1]。

所提出的方法在實(shí)現(xiàn)上相當(dāng)簡(jiǎn)單，但在復(fù)雜性分析上卻很復(fù)雜。因此，我只能給出最后的結(jié)果：m 并查集操作，使用樹(shù)加權(quán)和路徑壓縮，在一組 n 個(gè)對(duì)象執(zhí)行 O((m + n) log* n) (其中， log* 是迭代對(duì)數(shù)：一個(gè)增長(zhǎng)非常緩慢的函數(shù)，在實(shí)際應(yīng)用上，可以被認(rèn)為是一個(gè)常數(shù))。

最后，如果 O(n) 中幾乎所有的點(diǎn)都不屬于同一子集(其中 n 是要檢查的點(diǎn)的數(shù)量 [2]，所以 O(1) 就是兩個(gè)點(diǎn))，這種情況該如何檢查呢?請(qǐng)看以下示例代碼：

(defun uf-disjoint (points)
"Return true if all of the POINTS belong to different subsets."
(let (roots)
(dolist (point points)
(let ((root (uf-find point)))
(when (member root roots)
(return-from uf-disjoint nil))
(push root roots))))
t)

從這個(gè)簡(jiǎn)單的例子中可以得出更多的結(jié)論：

我們最初的想法并不總是完美無(wú)缺的。檢查邊緣情況是否存在潛在問(wèn)題是很重要的。

我們已經(jīng)目睹了一個(gè)壓根就不存在的數(shù)據(jù)結(jié)構(gòu)示例：信息片段分布在各個(gè)數(shù)據(jù)點(diǎn)上。有時(shí)，可以選擇以集中的方式將信息存儲(chǔ)在專用結(jié)構(gòu)(如哈希表之類)中，或者將其分布存儲(chǔ)在各個(gè)節(jié)點(diǎn)上。后一種方法通常更優(yōu)雅，也更有效，盡管它并不是那么明顯。

腳注：

[1] 此外，Python 有專門(mén)的語(yǔ)法來(lái)析構(gòu)這類元組：dec, rem = truncate(3.14)。但是，這并不是處理從函數(shù)返回一次值和一個(gè)或多個(gè)二次值的最佳方法。所有必需的值都是通過(guò) value 表單返回：(values dec rem) ，可以用 (multiple-value-bind (dec rem) (truncate 3.14) ...) 或 (with ((dec rem (truncate 3.14))) ...) 來(lái)檢索。它更優(yōu)雅，因?yàn)榭梢酝ㄟ^(guò)通常方式調(diào)用函數(shù)來(lái)隨意丟棄二次值：(+ 1 (truncate 3.14)) => 4：在 Python 中是不可能的，因?yàn)槟悴荒苡媚硞�(gè)東西對(duì)元組進(jìn)行求和。

[2] 實(shí)際上，這里的復(fù)雜度是 O(n^2)，這是由于使用了在 O(n) 中執(zhí)行集合成員測(cè)試的函數(shù) member，但這對(duì)整個(gè)概念來(lái)說(shuō)并不重要。如果期望使用數(shù)十個(gè)或數(shù)百個(gè)點(diǎn)調(diào)用 uf-disjoint，那么跟結(jié)構(gòu)必須更改為具有 O(1) 成員操作的哈希集。

作者介紹：

Vsevolod Dyomkin，Lisp 程序員，居住在烏克蘭基輔。精通烏克蘭語(yǔ)、俄語(yǔ)和英語(yǔ)。目前正在撰寫(xiě)關(guān)于 Lisp 的書(shū)籍 Programming Algorithms in Lisp，該書(shū)將使用 CC BY-NC-ND 許可(創(chuàng)作公用許可協(xié)議)，供公眾免費(fèi)閱讀。

譯者：Sambodhi

原文鏈接：LISP, THE UNIVERSE AND EVERYTHING

標(biāo)簽： 數(shù)據(jù)結(jié)構(gòu)

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請(qǐng)與原作者聯(lián)系。