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

數(shù)據(jù)是一個(gè)廣義的術(shù)語，可以指代各種類型的信息，包括最基本的數(shù)字和字符串。在經(jīng)典的“Hello World!”這個(gè)簡單程序中，字符串"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

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

在這里，你將學(xué)到，數(shù)據(jù)結(jié)構(gòu)不只是用于組織數(shù)據(jù)，它還極大地影響著代碼的運(yùn)行速度。因?yàn)閿?shù)據(jù)結(jié)構(gòu)不同，程序的運(yùn)行速度可能相差多個(gè)數(shù)量級。如果你寫的程序要處理大量的數(shù)據(jù)，或者要讓數(shù)千人同時(shí)使用，那么你采用何種數(shù)據(jù)結(jié)構(gòu)，將決定它是能夠運(yùn)行，還是會因?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ì)算機(jī)科學(xué)中最基本的數(shù)據(jù)結(jié)構(gòu)之一。如果你用過數(shù)組，那么應(yīng)該知道它就是一個(gè)含有數(shù)據(jù)的列表。它有多種用途，適用于各種場景，下面就舉個(gè)簡單的例子。

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

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

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

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

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

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

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

為什么呢？

因?yàn)椋悴豢赡芎芙^對地說，某項(xiàng)操作要花5 秒。它在某臺機(jī)器上要跑5 秒，但換到一臺舊一點(diǎn)的機(jī)器，可能就要多于5 秒，而換到一臺未來的超級計(jì)算機(jī)，運(yùn)行時(shí)間又將顯著縮短。所以，受硬件影響的計(jì)時(shí)方法，非常不可靠。

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

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

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

1. 讀取

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

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

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

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

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

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

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

計(jì)算機(jī)之所以在讀取數(shù)組中某個(gè)索引所指的值時(shí)，能直接跳到那個(gè)位置上，是因?yàn)樗邆湟韵聴l件。

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

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

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

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

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

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

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

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

所以，數(shù)組的讀取是一種非常高效的操作，因?yàn)樗灰徊骄秃谩Ｒ徊阶匀灰彩亲羁斓乃俣取＿@種一步讀取任意索引的能力，也是數(shù)組好用的原因之一。

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

2.查找

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

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

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

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

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

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

因?yàn)樗饕? 的值是"apples"，并非我們所要的"dates"，所以計(jì)算機(jī)跳到下一個(gè)索引上。

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

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

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

在這個(gè)例子中，因?yàn)槲覀儥z查了4 個(gè)格子才找到想要的值，所以這次操作總計(jì)是4 步。

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

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

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

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

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

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