數組幾乎可以是所有軟體工程師最常用到的資料結構,正是因為如此,很多開發者對其不夠重視.
而面試中經常有這樣一類問題: 「100萬個成員的數組取第一個和最後一個有性能差距嗎?為什麼?」
除此之外,我們在平時的業務開發中會經常出現數組一把梭的情況,大多數情況下我們都會用數組的形式進行操作,而有讀源碼習慣的開發者可能會發現,在一些底層庫中,我們可能平時用數組的地方,底層庫卻選擇了另外的資料結構,這又是為什麼?
希望大家帶着以上的問題我們進行讨論.
什麼是數組
數組是計算機科學中最基本的資料結構了,絕大多數程式設計語言都内置了這種資料結構,也是開發者最常見的資料結構.
數組(英語：Array)，是由相同類型的元素(element)的集合所組成的資料結構，配置設定一塊連續的記憶體來存儲.
當然,在一些動态語言中例如Python的清單或者JavaScript的數組都可能是非連續性的記憶體,也可以存儲不同類型的元素.
比如我們有如下一個數組:
arr = [1, 2, 3, 4, 5]
其在記憶體中的表現應該是這樣的:
我們可以看到,這個數組在記憶體中是以連續線性的形式儲存的,這個連續線性的儲存形式既有其優勢又有其劣勢,隻有我們搞清楚優劣才能在以後的開發中更好地使用數組.
數組的特性
一個資料結構通常都有「插入、查找、删除、讀取」這四種基本的操作,我們會逐一分析這些操作帶來的性能差異.
首先我們要辨析一個概念--性能.
這裡的性能并不是絕對意義上速度的快慢,因為不同的裝置其硬體基礎就會産生巨大的速度差異,這裡的性能是我們在算法分析中的「複雜度」概念.
插入性能
我們已經知道數組是一段連續儲存的記憶體，當我們要将新元素插入到數組k的位置時呢?這個時候需要将k索引處之後的所有元素往後挪一位,并将k索引的位置插入新元素.
我們看到這個時候需要進行操作的工作量就大多了,通常情況下,插入操作的時間複雜度是O(n).
删除性能
删除操作其實與插入很類似,同樣我要删除數組之内的k索引位置的元素,我們就需要将其删除後,為了保持記憶體的連續性,需要将k之後的元素通通向前移動一位,這個情況的時間複雜度也是O(n).
查找性能
比如我們要查找一個數組中是否存在一個為2的元素,那麼計算機需要如何操作呢?
如果是人的話,在少量資料的情況下我們自然可以一眼找到是否有2的元素,而計算機不是,計算機需要從索引0開始往下比對,直到比對到2的元素為止.
這個查找的過程其實就是我們常見的線性查找,這個時候需要比對的平均步數與數組的長度n有關,這個時間複雜度同樣是O(n).
讀取性能
我們已經強調過數組的特點是擁有相同的資料類型和一塊連續的線性記憶體,那麼正是基于以上的特點,數組的讀取性能非常的卓越,時間複雜度為O(1),相比于連結清單、二叉樹等資料結構,它的優勢非常明顯.
那麼數組是如何做到這麼低的時間複雜度呢?
假設我們的數組記憶體起始位址為start,而元素類型的長度為size,數組索引為i,那麼我們很容易得到這個數組記憶體位址的尋址公式:
arr[i]_address = start + size * i
比如我們要讀取arr[3]的值,那麼隻需要把3代入尋址公式,計算機就可以一步查詢到對應的元素,是以數組讀取的時間複雜度隻有O(1).
性能優化
我們已經知道除了「讀取」這一個操作以外,其他操作的時間複雜度都在O(n),那麼有沒有有效的方法進行性能優化呢?
查找性能優化
當數組的元素是無序狀态下,我們隻能用相對不太快的線性查找進行查找,當元素是有序狀态(遞增或者遞減),我們可以用另一種更高效的方法--二分查找.
假設我們有一個有int類型組成的數組,以遞增的方式儲存:
arr = [1, 2, 3, 4, 5, 6, 7]
如果我們要查找值為6元素,按照線性查找的方式需要根據數組索引從0依次比對,直到碰到索引5的元素.
而二分查找的效率則更高,由于我們知道此數組的元素是有序遞增排列的:
- 我們可以取一個索引為3的元素為中間值p
- 将p與目标值6進行對比,發現p的值4<6,那麼此時由于是遞增數組,目标值一定在索引3之後的元素中
- 此時,再在索引3之後到尾部的元素中取出新的中間值p與目标值比對,再重複下去,直到找到目标值
我們可以發現這樣的操作每一次對比都能排除目前元素數量一半的元素,整體下來的時間複雜度隻有O(log n),這表示此方法的效率極高.
這種高效的方法在資料量越大的情況下,越能展現出來,比如目前有一個10億成員的數組是有序遞增,如果按照線性查找,最差的情況下需要10億此查找操作才能找到結果,而二分查找僅僅需要7次.
插入性能優化
比如有以下數組,我們要将一個新成員orange插入索引1的位置,通常情況下需要後三位成員後移,orange占據索引1的位置.
但是如果我們的需求并不一定需要索引的有序性呢?也就是說,我們可以把數組當成一個集合概念,我們可以在索引1的位置插入orange并在數組的尾部開辟一個新記憶體将原本在1位置的banana存入新記憶體中,這樣雖然索引的亂了,但是整個操作僅僅需要O(1)的時間複雜度.
arr = ['apple', 'banana', 'grape', 'watermelon']
删除性能優化
删除操作需要将産出位置後的元素集體向前移動,這非常消耗性能,尤其是在頻繁的删除、插入操作中更是如此。
我們可以先記錄下相關的操作,但是并不立即進行删除,當到一定的節點時我們再一次性依據記錄對數組進行操作,這樣數組成員的反複頻繁移動變成了一次性操作,可以很大程度上提高性能.
這個思想應用非常廣泛:
- 前端架構的虛拟DOM就是将對DOM的大量操作先儲存在差異隊列中,然後再一次性更新,避免了DOM的回流和重繪.
- V8和JVM中的标記清除算法也是基于此思想,标記清除算法分為兩個階段,标記階段對通路到的對象都打上一個辨別,在清除階段發現某個對象沒有标記則進行回收.
小結
回到題目中的問題,我們現在已經可以很清楚地知道「100萬個成員的數組取第一個和最後一個是否有性能差距」,答案顯然是沒有,因為數組是一塊線性連續的記憶體,我們可以通過尋址公式一步取出對應的成員,這跟成員的位置沒有關系.
最後我們經常在面試或者LeetCode中碰到這樣一類問題,即數組中的子元素問題.
比如: 給定一個整數數組，計算長度為 'k' 的連續子數組的最大總和。
什麼方法可以盡可能地降低時間複雜度?