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

 

 

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

 

 

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

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

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

譯注：

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

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

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

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

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

與此同時，一些經(jīng)驗豐富的開發(fā)人員指出，當(dāng)找到正確的數(shù)據(jù)結(jié)構(gòu)時，算法幾乎會“自動”地編寫出來。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)一書中，對同一個想法提出了不那么尖銳的版本，稱之為“表示原則”(Rule of Representation)：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

元組

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

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

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

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

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

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

(defstruct pair
left right)

這個 defstruct 宏，實際上，生成了若干個定義：結(jié)構(gòu)類型的構(gòu)造函數(shù)，被稱為 make-pair，并具有 2 個關(guān)鍵字參數(shù)：:left 和 :right 以及字段訪問器：pair-left 和 pair-right。此外，結(jié)構(gòu)常見的 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 是互補的 Lisp 函數(shù)，它們允許以計算機(jī)可讀的形式打印值(如果提供了適當(dāng)?shù)?print-function(打印函數(shù)))，并將其讀取回來。理想情況下，良好的 print-representations 對人類和計算機(jī)來說都是可讀的，對于代碼透明度非常重要，不應(yīng)該被忽視。

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

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

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

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

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

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

 

 

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

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

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

(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) 就會向我們的集合中添加一個包含單個項的新子集。

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

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

d
^ ^ ^
| | |
a b c

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

下面是優(yōu)化版本的實現(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 的多個值很方便，可以簡化代碼。有關(guān)它們的更多細(xì)節(jié)，請參見腳注 [1]。

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

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

(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)

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

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

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

腳注：

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

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

作者介紹：

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

譯者：Sambodhi

原文鏈接：LISP, THE UNIVERSE AND EVERYTHING

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

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