面試官: 100萬(wàn)個(gè)成員的數(shù)組取第一個(gè)和最后一個(gè)有性能差距嗎?

本文首發(fā)于微信公眾號(hào)「程序員面試官」

數(shù)組幾乎可以是所有軟件工程師最常用到的數(shù)據(jù)結(jié)構(gòu),正是因?yàn)槿绱?很多開(kāi)發(fā)者對(duì)其不夠重視.

而面試中經(jīng)常有這樣一類(lèi)問(wèn)題: 「100萬(wàn)個(gè)成員的數(shù)組取第一個(gè)和最后一個(gè)有性能差距嗎?為什么?」


除此之外,我們?cè)谄綍r(shí)的業(yè)務(wù)開(kāi)發(fā)中會(huì)經(jīng)常出現(xiàn)數(shù)組一把梭的情況,大多數(shù)情況下我們都會(huì)用數(shù)組的形式進(jìn)行操作,而有讀源碼習(xí)慣的開(kāi)發(fā)者可能會(huì)發(fā)現(xiàn),在一些底層庫(kù)中,我們可能平時(shí)用數(shù)組的地方,底層庫(kù)卻選擇了另外的數(shù)據(jù)結(jié)構(gòu),這又是為什么?

希望大家?guī)е陨系膯?wèn)題我們進(jìn)行討論.

什么是數(shù)組

數(shù)組是計(jì)算機(jī)科學(xué)中最基本的數(shù)據(jù)結(jié)構(gòu)了,絕大多數(shù)編程語(yǔ)言都內(nèi)置了這種數(shù)據(jù)結(jié)構(gòu),也是開(kāi)發(fā)者最常見(jiàn)的數(shù)據(jù)結(jié)構(gòu).

數(shù)組（英語(yǔ)：Array），是由相同類(lèi)型的元素（element）的集合所組成的數(shù)據(jù)結(jié)構(gòu)，分配一塊連續(xù)的內(nèi)存來(lái)存儲(chǔ).

當(dāng)然,在一些動(dòng)態(tài)語(yǔ)言中例如Python的列表或者JavaScript的數(shù)組都可能是非連續(xù)性的內(nèi)存,也可以存儲(chǔ)不同類(lèi)型的元素.

比如我們有如下一個(gè)數(shù)組:
arr = [1, 2, 3, 4, 5] 復(fù)制代碼
其在內(nèi)存中的表現(xiàn)應(yīng)該是這樣的:

?

?

我們可以看到,這個(gè)數(shù)組在內(nèi)存中是以連續(xù)線性的形式儲(chǔ)存的,這個(gè)連續(xù)線性的儲(chǔ)存形式既有其優(yōu)勢(shì)又有其劣勢(shì),只有我們搞清楚優(yōu)劣才能在以后的開(kāi)發(fā)中更好地使用數(shù)組.

數(shù)組的特性

一個(gè)數(shù)據(jù)結(jié)構(gòu)通常都有「插入、查找、刪除、讀取」這四種基本的操作,我們會(huì)逐一分析這些操作帶來(lái)的性能差異.

首先我們要辨析一個(gè)概念--性能.

這里的性能并不是絕對(duì)意義上速度的快慢,因?yàn)椴煌脑O(shè)備其硬件基礎(chǔ)就會(huì)產(chǎn)生巨大的速度差異,這里的性能是我們?cè)谒惴ǚ治鲋械摹笍?fù)雜度」概念.

復(fù)雜度的概念可以移步算法分析
<https://link.juejin.im?target=https%3A%2F%2Fwww.cxymsg.com%2Fguide%2Falgorithm.html%23%25E6%258E%2592%25E5%25BA%258F%25E7%25AE%2597%25E6%25B3%2595>

插入性能

我們已經(jīng)知道數(shù)組是一段連續(xù)儲(chǔ)存的內(nèi)存，當(dāng)我們要將新元素插入到數(shù)組k的位置時(shí)呢?這個(gè)時(shí)候需要將k索引處之后的所有元素往后挪一位,并將k索引的位置插入新元素.

?

?

我們看到這個(gè)時(shí)候需要進(jìn)行操作的工作量就大多了,通常情況下,插入操作的時(shí)間復(fù)雜度是O(n).

刪除性能


刪除操作其實(shí)與插入很類(lèi)似,同樣我要?jiǎng)h除數(shù)組之內(nèi)的k索引位置的元素,我們就需要將其刪除后,為了保持內(nèi)存的連續(xù)性,需要將k之后的元素通通向前移動(dòng)一位,這個(gè)情況的時(shí)間復(fù)雜度也是O(n).

?

?

查找性能

比如我們要查找一個(gè)數(shù)組中是否存在一個(gè)為2的元素,那么計(jì)算機(jī)需要如何操作呢?

如果是人的話,在少量數(shù)據(jù)的情況下我們自然可以一眼找到是否有2的元素,而計(jì)算機(jī)不是,計(jì)算機(jī)需要從索引0開(kāi)始往下匹配,直到匹配到2的元素為止.

?

?

這個(gè)查找的過(guò)程其實(shí)就是我們常見(jiàn)的線性查找,這個(gè)時(shí)候需要匹配的平均步數(shù)與數(shù)組的長(zhǎng)度n有關(guān),這個(gè)時(shí)間復(fù)雜度同樣是O(n).

讀取性能

我們已經(jīng)強(qiáng)調(diào)過(guò)數(shù)組的特點(diǎn)是擁有相同的數(shù)據(jù)類(lèi)型和一塊連續(xù)的線性?xún)?nèi)存
,那么正是基于以上的特點(diǎn),數(shù)組的讀取性能非常的卓越,時(shí)間復(fù)雜度為O(1),相比于鏈表、二叉樹(shù)等數(shù)據(jù)結(jié)構(gòu),它的優(yōu)勢(shì)非常明顯.

那么數(shù)組是如何做到這么低的時(shí)間復(fù)雜度呢?

假設(shè)我們的數(shù)組內(nèi)存起始地址為start,而元素類(lèi)型的長(zhǎng)度為size,數(shù)組索引為i,那么我們很容易得到這個(gè)數(shù)組內(nèi)存地址的尋址公式:
arr[i]_address = start + size * i 復(fù)制代碼
比如我們要讀取arr[3]的值,那么只需要把3代入尋址公式,計(jì)算機(jī)就可以一步查詢(xún)到對(duì)應(yīng)的元素,因此數(shù)組讀取的時(shí)間復(fù)雜度只有O(1).

性能優(yōu)化

我們已經(jīng)知道除了「讀取」這一個(gè)操作以外,其他操作的時(shí)間復(fù)雜度都在O(n),那么有沒(méi)有有效的方法進(jìn)行性能優(yōu)化呢?

查找性能優(yōu)化

當(dāng)數(shù)組的元素是無(wú)序狀態(tài)下,我們只能用相對(duì)不太快的線性查找進(jìn)行查找,當(dāng)元素是有序狀態(tài)(遞增或者遞減),我們可以用另一種更高效的方法--二分查找.

假設(shè)我們有一個(gè)有int類(lèi)型組成的數(shù)組,以遞增的方式儲(chǔ)存:
arr = [1, 2, 3, 4, 5, 6, 7] 復(fù)制代碼
如果我們要查找值為6元素,按照線性查找的方式需要根據(jù)數(shù)組索引從0依次比對(duì),直到碰到索引5的元素.

而二分查找的效率則更高,由于我們知道此數(shù)組的元素是有序遞增排列的:

* 我們可以取一個(gè)索引為3的元素為中間值p
* 將p與目標(biāo)值6進(jìn)行對(duì)比,發(fā)現(xiàn)p的值4<6,那么此時(shí)由于是遞增數(shù)組,目標(biāo)值一定在索引3之后的元素中
* 此時(shí),再在索引3之后到尾部的元素中取出新的中間值p與目標(biāo)值比對(duì),再重復(fù)下去,直到找到目標(biāo)值
我們可以發(fā)現(xiàn)這樣的操作每一次對(duì)比都能排除當(dāng)前元素?cái)?shù)量一半的元素,整體下來(lái)的時(shí)間復(fù)雜度只有O(log n),這表示此方法的效率極高.


這種高效的方法在數(shù)據(jù)量越大的情況下,越能體現(xiàn)出來(lái),比如目前有一個(gè)10億成員的數(shù)組是有序遞增,如果按照線性查找,最差的情況下需要10億此查找操作才能找到結(jié)果,而二分查找僅僅需要7次.

插入性能優(yōu)化

比如有以下數(shù)組,我們要將一個(gè)新成員orange插入索引1的位置,通常情況下需要后三位成員后移,orange占據(jù)索引1的位置.

但是如果我們的需求并不一定需要索引的有序性呢?也就是說(shuō),我們可以把數(shù)組當(dāng)成一個(gè)集合概念,我們可以在索引1的位置插入orange
并在數(shù)組的尾部開(kāi)辟一個(gè)新內(nèi)存將原本在1位置的banana存入新內(nèi)存中,這樣雖然索引的亂了,但是整個(gè)操作僅僅需要O(1)的時(shí)間復(fù)雜度.
arr = ['apple', 'banana', 'grape', 'watermelon'] 復(fù)制代碼
刪除性能優(yōu)化

刪除操作需要將產(chǎn)出位置后的元素集體向前移動(dòng),這非常消耗性能,尤其是在頻繁的刪除、插入操作中更是如此。


我們可以先記錄下相關(guān)的操作,但是并不立即進(jìn)行刪除,當(dāng)?shù)揭欢ǖ墓?jié)點(diǎn)時(shí)我們?cè)僖淮涡砸罁?jù)記錄對(duì)數(shù)組進(jìn)行操作,這樣數(shù)組成員的反復(fù)頻繁移動(dòng)變成了一次性操作,可以很大程度上提高性能.

?

?

這個(gè)思想應(yīng)用非常廣泛:

* 前端框架的虛擬DOM就是將對(duì)DOM的大量操作先儲(chǔ)存在差異隊(duì)列中,然后再一次性更新,避免了DOM的回流和重繪.
* V8和JVM中的標(biāo)記清除算法也是基于此思想,標(biāo)記清除算法分為兩個(gè)階段,標(biāo)記階段對(duì)訪問(wèn)到的對(duì)象都打上一個(gè)標(biāo)識(shí),在清除階段發(fā)現(xiàn)某個(gè)對(duì)象沒(méi)有標(biāo)記則進(jìn)行回收.
小結(jié)


回到題目中的問(wèn)題,我們現(xiàn)在已經(jīng)可以很清楚地知道「100萬(wàn)個(gè)成員的數(shù)組取第一個(gè)和最后一個(gè)是否有性能差距」,答案顯然是沒(méi)有,因?yàn)閿?shù)組是一塊線性連續(xù)的內(nèi)存,我們可以通過(guò)尋址公式一步取出對(duì)應(yīng)的成員,這跟成員的位置沒(méi)有關(guān)系.

最后我們經(jīng)常在面試或者LeetCode中碰到這樣一類(lèi)問(wèn)題,即數(shù)組中的子元素問(wèn)題.

比如: 給定一個(gè)整數(shù)數(shù)組，計(jì)算長(zhǎng)度為 'k' 的連續(xù)子數(shù)組的最大總和。

?

?

什么方法可以盡可能地降低時(shí)間復(fù)雜度?說(shuō)出你的思路即可.

?

• ? 上一篇：jenkins在windows上自動(dòng)化部署.Net（.Net Core）項(xiàng)目
• ? 下一篇：Docker 學(xué)習(xí)線路