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

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

數據結構則是指數據的組織形式。看看以下代碼。

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

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

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

一旦對各種數據結構有了深刻的理解，并明白它們對程序性能方面的影響，你就能寫出快速而優雅的代碼，從而使軟件運行得快速且流暢。當然，你的編程技能也會更上一層樓。

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

基礎數據結構：數組

數組是計算機科學中最基本的數據結構之一。如果你用過數組，那么應該知道它就是一個含有數據的列表。它有多種用途，適用于各種場景，下面就舉個簡單的例子。

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

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

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

此外，我們會用一些名為索引的數字來標識每項數據在數組中的位置。

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

若想了解某個數據結構（例如數組）的性能，得分析程序怎樣操作這一數據結構。

一般數據結構都有以下4 種操作（或者說用法）。

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

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

為什么呢？

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

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

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

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

1. 讀取

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

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

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

計算機的內存可以被看成一堆格子。下圖是一片網格，其中有些格子有數據，有些則是空白。

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

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

購物清單數組的索引和內存地址，如下圖所示。

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

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

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

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

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

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

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

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

當計算機一步跳到1013 時，我們就能獲取到"dates"這個值了。

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

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

2.查找

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

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

對于我們人來說，可以一眼就看到這個購物清單上的"dates"，并數出它的索引為3。但是，計算機并沒有眼睛，它只能一步一步地檢查整個數組。

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

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

首先，計算機檢查索引0。

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

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

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

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

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

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

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

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

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

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

接下來，我們再研究一下插入，準確地說，是插入一個新值到數組之中。

3.插入

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

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

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

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

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

第1 步："elderberries"右移。

第2 步："date"右移。

第3 步："cucembers"右移。

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

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

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

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

4.刪除

數組的刪除就是消掉其某個索引上的數據。

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

第1 步：刪除"cucumbers"。

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

第2 步：將"dates"左移。

第3 步：將"elderberries"左移。

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

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

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

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

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

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

集合：一條規則決定性能

來看看另一種數據結構：集合。它是一種不允許元素重復的數據結構。

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

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

集合就是用于確保數據不重復。

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

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

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

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

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

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

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

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

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

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

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

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

第2 步：檢查索引1。

第3 步：檢查索引2。

第4 步：檢查索引3。

第5 步：檢查索引4。

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

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

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

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

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

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

總結

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

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

作者：杰伊•溫格羅

譯者：袁志鵬

定價：49.00元 / 電子書 24.99元

頁數：168

 

• 讓自學編程人員掌握專業知識，編寫出靈活且具可擴展性的代碼
• 讓計算機專業學生以更通俗易懂的方式加深理解數據結構和算法
• 讓初級開發人員鞏固計算機科學基本概念，優化代碼，提升技能

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

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

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

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

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