哪怕只寫過幾行代碼的人都會發(fā)現(xiàn)，編程基本上就是在跟數(shù)據(jù)打交道。計算機(jī)程序總是在接收數(shù)據(jù)、操作數(shù)據(jù)或返回數(shù)據(jù)。不管是求兩數(shù)之和的小程序，還是管理公司的企業(yè)級軟件，都運(yùn)行在數(shù)據(jù)之上。

數(shù)據(jù)是一個廣義的術(shù)語，可以指代各種類型的信息，包括最基本的數(shù)字和字符串。在經(jīng)典的“Hello World!”這個簡單程序中，字符串"Hello World!"就是一條數(shù)據(jù)。事實(shí)上，無論是多么復(fù)雜的數(shù)據(jù)，我們都可以將其拆成一堆數(shù)字和字符串來看待。

數(shù)據(jù)結(jié)構(gòu)則是指數(shù)據(jù)的組織形式。看看以下代碼。

x = "Hello!"y = "How are you"z = "today?"print x + y + z

這個非常簡單的程序把3 條數(shù)據(jù)串成了一句連貫的話。如果要描述該程序中的數(shù)據(jù)結(jié)構(gòu)，我們會說，這里有3 個獨(dú)立的變量，分別引用著3 個獨(dú)立的字符串。

在這里，你將學(xué)到，數(shù)據(jù)結(jié)構(gòu)不只是用于組織數(shù)據(jù)，它還極大地影響著代碼的運(yùn)行速度。因為數(shù)據(jù)結(jié)構(gòu)不同，程序的運(yùn)行速度可能相差多個數(shù)量級。如果你寫的程序要處理大量的數(shù)據(jù)，或者要讓數(shù)千人同時使用，那么你采用何種數(shù)據(jù)結(jié)構(gòu)，將決定它是能夠運(yùn)行，還是會因為不堪重負(fù)而崩潰。

一旦對各種數(shù)據(jù)結(jié)構(gòu)有了深刻的理解，并明白它們對程序性能方面的影響，你就能寫出快速而優(yōu)雅的代碼，從而使軟件運(yùn)行得快速且流暢。當(dāng)然，你的編程技能也會更上一層樓。

接下來我們將會分析兩種比較相似的數(shù)據(jù)結(jié)構(gòu)：數(shù)組和集合。它們從表面上看好像差不多，但通過即將介紹的分析工具，你將會觀察到它們在性能上的差異。

基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)：數(shù)組

數(shù)組是計算機(jī)科學(xué)中最基本的數(shù)據(jù)結(jié)構(gòu)之一。如果你用過數(shù)組，那么應(yīng)該知道它就是一個含有數(shù)據(jù)的列表。它有多種用途，適用于各種場景，下面就舉個簡單的例子。

一個允許用戶創(chuàng)建和使用購物清單的食雜店應(yīng)用軟件，其源代碼可能會包含以下的片段。

array = ["Apples", "bananas", "cucumbers", "dates", "elderberries"]

這就是一個數(shù)組，它剛好包含5 個字符串，每個代表我會從超市買的食物。

此外，我們會用一些名為索引的數(shù)字來標(biāo)識每項數(shù)據(jù)在數(shù)組中的位置。

在大多數(shù)的編程語言中，索引是從0 算起的，因此在這個例子中，"apples"的索引為0，"elderberries"的索引為4，如下所示。

若想了解某個數(shù)據(jù)結(jié)構(gòu)（例如數(shù)組）的性能，得分析程序怎樣操作這一數(shù)據(jù)結(jié)構(gòu)。

一般數(shù)據(jù)結(jié)構(gòu)都有以下4 種操作（或者說用法）。

• 讀取：查看數(shù)據(jù)結(jié)構(gòu)中某一位置上的數(shù)據(jù)。對于數(shù)組來說，這意味著查看某個索引所指的數(shù)據(jù)值。例如，查看索引2 上有什么食品，就是一種讀取。
• 查找：從數(shù)據(jù)結(jié)構(gòu)中找出某個數(shù)據(jù)值的所在。對于數(shù)組來說，這意味著檢查其是否包含某個值，如果包含，那么還得給出其索引。例如，檢查"dates"是否存在于食品清單之中，給出其對應(yīng)的索引，就是一種查找。
• 插入：給數(shù)據(jù)結(jié)構(gòu)增加一個數(shù)據(jù)值。對于數(shù)組來說，這意味著多加一個格子并填入一個值。例如，往購物清單中多加一項"figs"，就是一種插入。
• 刪除：從數(shù)據(jù)結(jié)構(gòu)中移走一個數(shù)據(jù)值。對于數(shù)組來說，這意味著把數(shù)組中的某個數(shù)據(jù)項移走。例如，把購物清單中的"bananas"移走，就是一種刪除。

接下來我們將會研究這些操作在數(shù)組上的運(yùn)行速度。同時，我們也將學(xué)到第一個重要理論：操作的速度，并不按時間計算，而是按步數(shù)計算。

為什么呢？

因為，你不可能很絕對地說，某項操作要花5 秒。它在某臺機(jī)器上要跑5 秒，但換到一臺舊一點(diǎn)的機(jī)器，可能就要多于5 秒，而換到一臺未來的超級計算機(jī)，運(yùn)行時間又將顯著縮短。所以，受硬件影響的計時方法，非常不可靠。

然而，若按步數(shù)來算，則確切得多。如果A 操作要5 步，B 操作要500 步，那么我們可以很肯定地說，無論是在什么樣的硬件上對比，A 都快過B。因此，衡量步數(shù)是分析速度的關(guān)鍵。

此外，操作的速度，也常被稱為時間復(fù)雜度。本文中，我們提到速度、時間復(fù)雜度、效率、性能，它們其實(shí)指的都是步數(shù)。

事不宜遲，我們現(xiàn)在就來探索上述4 種操作方式在數(shù)組上要花多少步。

1. 讀取

首先看看讀取，即查看數(shù)組中某個索引所指的數(shù)據(jù)值。

這只要一步就夠了，因為計算機(jī)本身就有跳到任一索引位置的能力。在["apples","bananas", "cucumbers", "dates", "elderberries"]的例子中，如果要查看索引2 的值，那么計算機(jī)就會直接跳到索引2，并告訴你那里有"cucumbers"。

計算機(jī)為什么能一步到位呢？原因如下。

計算機(jī)的內(nèi)存可以被看成一堆格子。下圖是一片網(wǎng)格，其中有些格子有數(shù)據(jù)，有些則是空白。

當(dāng)程序聲明一個數(shù)組時，它會先劃分出一些連續(xù)的空格子以備使用。換句話說，如果你想創(chuàng)建一個包含5 個元素的數(shù)組，計算機(jī)就會找出5 個排成一行的空格子，將其當(dāng)成數(shù)組。

內(nèi)存中的每個格子都有各自的地址，就像街道地址，例如大街123 號。不過內(nèi)存地址就只用一個普通的數(shù)字來表示。而且，每個格子的內(nèi)存地址都比前一個大1，如下圖所示。

購物清單數(shù)組的索引和內(nèi)存地址，如下圖所示。

計算機(jī)之所以在讀取數(shù)組中某個索引所指的值時，能直接跳到那個位置上，是因為它具備以下條件。

(1) 計算機(jī)可以一步就跳到任意一個內(nèi)存地址上。（就好比，要是你知道大街123 號在哪兒，那么就可以直奔過去。）

(2) 數(shù)組本身會記有第一個格子的內(nèi)存地址，因此，計算機(jī)知道這個數(shù)組的開頭在哪里。

(3) 數(shù)組的索引從0 算起。

回到剛才的例子，當(dāng)我們叫計算機(jī)讀取索引3 的值時，它會做以下演算。

(1) 該數(shù)組的索引從0 算起，其開頭的內(nèi)存地址為1010。

(2) 索引3 在索引0 后的第3 個格子上。

(3) 于是索引3 的內(nèi)存地址為1013，因為1010 + 3 = 1013。

當(dāng)計算機(jī)一步跳到1013 時，我們就能獲取到"dates"這個值了。

所以，數(shù)組的讀取是一種非常高效的操作，因為它只要一步就好。一步自然也是最快的速度。這種一步讀取任意索引的能力，也是數(shù)組好用的原因之一。

如果我們問的不是“索引3 有什么值”，而是“"dates"在不在數(shù)組里”，那么這就需要進(jìn)行查找操作了。下面我們就來看看。

2.查找

如前所述，對于數(shù)組來說，查找就是檢查它是否包含某個值，如果包含，還得給出其索引。

那么，我們就試試在數(shù)組中查找"dates"要用多少步。

對于我們?nèi)藖碚f，可以一眼就看到這個購物清單上的"dates"，并數(shù)出它的索引為3。但是，計算機(jī)并沒有眼睛，它只能一步一步地檢查整個數(shù)組。

想要查找數(shù)組中是否存在某個值，計算機(jī)會先從索引0 開始，檢查其值，如果不匹配，則繼續(xù)下一個索引，以此類推，直至找到為止。

我們用以下圖來演示計算機(jī)如何從購物清單中查找"dates"。

首先，計算機(jī)檢查索引0。

因為索引0 的值是"apples"，并非我們所要的"dates"，所以計算機(jī)跳到下一個索引上。

索引1 也不是"dates"，于是計算機(jī)再跳到索引2。

但索引2 的值仍不匹配，計算機(jī)只好再跳到下一格。

啊，真是千辛萬苦，我們找到"dates"了，它就在索引3 那里。自此，計算機(jī)不用再往后跳了，因為結(jié)果已經(jīng)得到。

在這個例子中，因為我們檢查了4 個格子才找到想要的值，所以這次操作總計是4 步。

這種逐個格子去檢查的做法，就是最基本的查找方法——線性查找。當(dāng)然還可以學(xué)習(xí)其他查找方法，但在那之前，我們再思考一下，在數(shù)組上進(jìn)行線性查找最多要多少步呢？

如果我們要找的值剛好在數(shù)組的最后一個格子里（如本例的elderberries），那么計算機(jī)從頭到尾檢查每個格子，會在最后才找到。同樣，如果我們要找的值并不存在于數(shù)組中，那么計算機(jī)也還是得查遍每個格子，才能確定這個值不在數(shù)組中。

于是，一個5 格的數(shù)組，其線性查找的步數(shù)最大值是5，而對于一個500 格的數(shù)組，則是500。

以此類推，一個N 格的數(shù)組，其線性查找的最多步數(shù)是N（N 可以是任何自然數(shù)）。

可見，無論是多長的數(shù)組，查找都比讀取要慢，因為讀取永遠(yuǎn)都只需要一步，而查找卻可能需要多步。

接下來，我們再研究一下插入，準(zhǔn)確地說，是插入一個新值到數(shù)組之中。

3.插入

往數(shù)組里插入一個新元素的速度，取決于你想把它插入到哪個位置上。

假設(shè)我們想要在購物清單的末尾插入"figs"。那么只需一步。因為之前說過了，計算機(jī)知道數(shù)組開頭的內(nèi)存地址，也知道數(shù)組包含多少個元素，所以可以算出要插入的內(nèi)存地址，然后一步跳到那里插入就行了。圖示如下。

但在數(shù)組開頭或中間插入，就另當(dāng)別論了。這種情況下，我們需要移動其他元素以騰出空間，于是得花費(fèi)額外的步數(shù)。

例如往索引2 處插入"figs"，如下所示。

為了達(dá)到目的，我們必須先把"cucumbers"、"dates"和"elderberries"往右移，以便空出索引2。而這也不是一步就能移好，因為我們首先要將"elderberries"右移一格，以空出位置給"dates"，然后再將"dates"右移，以空出位置給"cucumbers"，下面來演示這個過程。

第1 步："elderberries"右移。

第2 步："date"右移。

第3 步："cucembers"右移。

第4 步：至此，可以在索引2 處插入"figs"了。

如上所示，整個過程有4 步，開始3 步都是在移動數(shù)據(jù)，剩下1 步才是真正的插入數(shù)據(jù)。

最低效（花費(fèi)最多步數(shù)）的插入是插入在數(shù)組開頭。因為這時候需要把數(shù)組所有的元素都往右移。于是，一個含有N 個元素的數(shù)組，其插入數(shù)據(jù)的最壞情況會花費(fèi)N + 1 步。即插入在數(shù)組開頭，導(dǎo)致N 次移動，加上一次插入。

最后要說的“刪除”，則相當(dāng)于插入的反向操作。

4.刪除

數(shù)組的刪除就是消掉其某個索引上的數(shù)據(jù)。

我們找回最開始的那個數(shù)組，刪除索引2 上的值，即"cucumbers"。

第1 步：刪除"cucumbers"。

雖然刪除"cucumbers"好像一步就搞定了，但這帶來了新的問題：數(shù)組中間空出了一個格子。因為數(shù)組中間是不應(yīng)該有空格的，所以，我們得把"dates"和"elderberries"往左移。

第2 步：將"dates"左移。

第3 步：將"elderberries"左移。

結(jié)果，整個刪除操作花了3 步。其中第1 步是真正的刪除，剩下的2 步是移數(shù)據(jù)去填空格。

所以，刪除本身只需要1 步，但接下來需要額外的步驟將數(shù)據(jù)左移以填補(bǔ)刪除所帶來的空隙。

跟插入一樣，刪除的最壞情況就是刪掉數(shù)組的第一個元素。因為數(shù)組不允許空元素，當(dāng)索引0 空出，那么剩下的所有元素都要往左移去填空。

對于含有5 個元素的數(shù)組，刪除第一個元素需要1 步，左移剩余的元素需要4 步。而對于500個元素的數(shù)組，刪除第一個元素需要1 步，左移剩余的元素需要499 步。可以推出，對于含有N個元素的數(shù)組，刪除操作最多需要N 步。

既然學(xué)會了如何分析數(shù)據(jù)結(jié)構(gòu)的時間復(fù)雜度，那就可以開始探索各種數(shù)據(jù)結(jié)構(gòu)的性能差異了。了解這些非常重要，因為數(shù)據(jù)結(jié)構(gòu)的性能差異會直接造成程序的性能差異。

下一個要介紹的數(shù)據(jù)結(jié)構(gòu)是集合，它跟數(shù)組似乎很像，甚至讓人以為就是同一種東西。然而，我們將會看到它跟數(shù)組在性能上是有區(qū)別的。

集合：一條規(guī)則決定性能

來看看另一種數(shù)據(jù)結(jié)構(gòu)：集合。它是一種不允許元素重復(fù)的數(shù)據(jù)結(jié)構(gòu)。

其實(shí)集合是有不同形式的，但現(xiàn)在我們只討論基于數(shù)組的那種。這種集合跟數(shù)組差不多，都是一個普通的元素列表，唯一的區(qū)別在于，集合不允許插入重復(fù)的值。

要是你想往集合["a", "b", "c"]再插入一個"b"，計算機(jī)是不會允許的，因為集合中已經(jīng)有"b"了。

集合就是用于確保數(shù)據(jù)不重復(fù)。

如果你要創(chuàng)建一個線上電話本，你應(yīng)該不會希望相同的號碼出現(xiàn)兩次吧。事實(shí)上，現(xiàn)在我的本地電話本就有這種狀況：我家的電話號碼不單指向我這里，還錯誤地指向了一個叫Zirkind 的家庭（這是真的）。接聽那些要找Zirkind 的電話或留言真的挺煩的。

不過，估計Zirkind 一家也在納悶為什么總是接不到電話。而當(dāng)我想要打電話告訴Zirkind 號碼錯了的時候，我妻子就會去接電話了，因為我撥的就是我家號碼（好吧，這是開玩笑）。如果這個電話本程序用集合來處理，那就不會搞出這種麻煩了。

總之，集合就是一個帶有“不允許重復(fù)”這種簡單限制的數(shù)組。而該限制也導(dǎo)致它在4 種基本操作中有1 種與數(shù)組性能不同。

下面就來分析讀取、查找、插入和刪除在基于數(shù)組的集合上表現(xiàn)如何。

集合的讀取跟數(shù)組的讀取完全一樣，計算機(jī)只要一步就能獲取指定索引上的值。如之前解釋的那樣，這是因為計算機(jī)知道集合開頭的內(nèi)存地址，所以能夠一步跳到集合的任意索引。

集合的查找也跟數(shù)組的查找無異，需要N 步去檢查某個值在不在集合當(dāng)中。刪除也是，總共需要N 步去刪除和左移填空。

但插入就不同了。先看看在集合末尾的插入。對于數(shù)組來說，末尾插入是最高效的，它只需要1 步。

而對于集合，計算機(jī)得先確定要插入的值不存在于其中——因為這就是集合：不允許重復(fù)值。

于是每次插入都要先來一次查找。

假設(shè)我們的購物清單是一個集合——用集合還是不錯的，畢竟你不會想買重復(fù)的東西。如果當(dāng)前集合是["apples", "bananas", "cucumbers", "dates", "elderberries"]，然后想插入"figs"，那么就需要做一次如下的查找。

第1 步：檢查索引0 有沒有"figs"。

沒有，不過說不定其他索引會有。為了在真正插入前確保它不存在于任何索引上，我們繼續(xù)。

第2 步：檢查索引1。

第3 步：檢查索引2。

第4 步：檢查索引3。

第5 步：檢查索引4。

直到檢查完整個集合，才能確定插入"figs"是安全的。于是，到最后一步。

第6 步：在集合末尾插入"figs"。

在集合的末尾插入也屬于最好的情況，不過對于一個含有5 個元素的集合，你仍然要花6 步。因為，在最終插入的那一步之前，要把5 個元素都檢查一遍。

換句話說，在N 個元素的集合中進(jìn)行插入的最好情況需要N + 1 步——N 步去確認(rèn)被插入的值不在集合中，加上最后插入的1 步。

最壞的情況則是在集合的開頭插入，這時計算機(jī)得檢查N 個格子以保證集合不包含那個值，然后用N 步來把所有值右移，最后再用1 步來插入新值。總共2N + 1 步。

這是否意味著因為它的插入比一般的數(shù)組慢，所以就不要用了呢？當(dāng)然不是。在需要保證數(shù)據(jù)不重復(fù)的場景中，集合是非常重要的（真希望有一天我的電話本能恢復(fù)正常）。但如果沒有這種需求，那么選擇插入比集合快的數(shù)組會更好一些。具體哪種數(shù)據(jù)結(jié)構(gòu)更合適，當(dāng)然要根據(jù)你的實(shí)際應(yīng)用場景而定。

總結(jié)

理解數(shù)據(jù)結(jié)構(gòu)的性能，關(guān)鍵在于分析操作所需的步數(shù)。采取哪種數(shù)據(jù)結(jié)構(gòu)將決定你的程序是能夠承受住壓力，還是崩潰。本文特別講解了如何通過步數(shù)分析來判斷某種應(yīng)用該選擇數(shù)組還是集合。

不同的數(shù)據(jù)結(jié)構(gòu)有不同的時間復(fù)雜度，類似地，不同的算法（即使是用在同一種數(shù)據(jù)結(jié)構(gòu)上）也有不同的時間復(fù)雜度。既然我們已經(jīng)學(xué)會了時間復(fù)雜度的分析方法，那么現(xiàn)在就可以用它來對比各種算法，找出能夠發(fā)揮代碼極限性能的那個吧。這也正是《數(shù)據(jù)結(jié)構(gòu)與算法圖解》的第2章中所要講的。

作者：杰伊•溫格羅

譯者：袁志鵬

定價：49.00元 / 電子書 24.99元

頁數(shù)：168

 

• 讓自學(xué)編程人員掌握專業(yè)知識，編寫出靈活且具可擴(kuò)展性的代碼
• 讓計算機(jī)專業(yè)學(xué)生以更通俗易懂的方式加深理解數(shù)據(jù)結(jié)構(gòu)和算法
• 讓初級開發(fā)人員鞏固計算機(jī)科學(xué)基本概念，優(yōu)化代碼，提升技能

數(shù)據(jù)結(jié)構(gòu)與算法并不只是抽象的概念，掌握好的話可以寫出更高效、運(yùn)行得更快的代碼，這對于如今盛行的網(wǎng)頁和移動應(yīng)用開發(fā)來說尤為重要。如果你最近一次使用算法是在大學(xué)課堂上或求職面試時，那你應(yīng)該還沒見識到它的真正威力。

這個主題的大多數(shù)資料都有一種通病——晦澀難懂。滿紙的數(shù)學(xué)術(shù)語，搞得除非你是數(shù)學(xué)家，不然真不知道作者在說什么。即使是一些聲稱“簡化”過的書，看起來也好像已經(jīng)認(rèn)定讀者都掌握了高深的數(shù)學(xué)知識。這就導(dǎo)致了很多人對此主題望而生畏，以為自己的智商不足以理解這些概念。

但事實(shí)上，數(shù)據(jù)結(jié)構(gòu)與算法都是能夠從常識推導(dǎo)出來的。數(shù)學(xué)符號只是一種特定的語言，數(shù)學(xué)里的一切都是可以用常識去解釋的。本書用到的數(shù)學(xué)知識就只有加減乘除和指數(shù)，所有的概念都可以用文字來解釋。作者還采用了大量的圖表以便讀者輕松地理解。

一旦掌握了這些知識，你就能寫出高效、快速、優(yōu)雅的代碼。你還能權(quán)衡各種寫法的優(yōu)劣，并能合理判斷適用于給定情況的最優(yōu)方案。

一些讀者可能是因為學(xué)校開設(shè)了這門課或者為準(zhǔn)備技術(shù)面試而閱讀本書的。本書對計算機(jī)科學(xué)基礎(chǔ)的解釋能有效地幫助你達(dá)到目的。此外，我還鼓勵你正視這些概念在日常編程中的實(shí)用價值。為此，作者將書中闡述的概念與實(shí)際結(jié)合，其中的用例都可供大家使用。