資料結構是電腦科學重要基礎學科,許多程式庫都提供了資料結構高效實作,然而即便現代開發者不需全盤瞭解資料結構實作細節,但仍需瞭解基本資料結構實作與特性,以在正確場合選用具正確特性的實作,避免時間或空間上的效能問題,或者有能力選用正確的第三方程式庫,避免自行以繁瑣程式實作所需功能。

認識Java標準資料結構實作
在我上一篇專欄中談到的數列(List)、集合(Set)以及對應(Map)三種基本資料型態,是以高階特性來大致分類,具體實作方式仍各有差異。以Java來說,List介面的實作基本上就有ArrayList與LinkedList;Set介面的實作基本上有HashSet與TreeSet;Map介面的實作基本上有HashMap與TreeMap。

ArrayList內部實作使用陣列來保存物件,陣列根據索引隨機存取時速度快,若操作上有這類需求時,像是排序,使用ArrayList可得到較好的速度表現;然而若操作時會引發索引順序調整時,會有較差的表現,特別是移除索引0的元素。陣列長度固定也是要考量的問題,在ArrayList內部陣列長度不夠時,會建立新陣列並複製舊陣列元素參考,如果能事先建立足夠長度的內部陣列,可以節省上述成本。LinkedList內部採用了鏈結(Link)結構,鏈結每個元素參考下一個元素,有利在數列前端調整元素;然而想要指定索引隨機存取物件時,基本上是從第一個元素逐一查找下一元素,效率較差,像數列排序就不適合使用LinkedList。

在Set與Map的基本實作方面,以雜湊(Hash)為實作基礎的有HashSet與HashMap。

雜湊基本特性是用記憶體空間換取存取時間,新增物件時,直接根據物件或鍵的雜湊值分配至適當位置,新增物件時速度表現較佳,然而物件數量多時耗費更多雜湊空間(Heap space),若有必要迭代整個HashSet或HashMap,效能表現較為不佳。

以樹狀結構為實作的TreeSet與TreeMap,在新增或刪除時,必須耗費少量成本維持樹的節點順序與平衡,然而已排序的結構在進行元素查找時有較好效能。

常用操作的效能考量

對各種資料型態,主要必須瞭解使用了陣列、鏈結、雜湊或樹狀哪種結構來實作,才能依需求選用對應的實作成品。

以單純地新增元素來說,ArrayList、LinkedList、HashSet的add(o)基本上是O(1),而TreeSet會是O(log n);使用contains(o)查找元素或remove(o)刪除元素時,線性結構的ArrayList、LinkedList會是O(n),基於雜湊值來查找的HashSet會是O(1),而TreeSet會是O(log n);在使用Iterator的next逐一迭代元素時,ArrayList、LinkedList會是O(1),HashSet會是與雜湊空間及元素個數相關的O(h/n),而TreeSet仍是O(log n)。

在基於索引的操作方面,由於數列本身是線性結構,因此對於指定索引位置的add(i, o)與remove(i)等操作來說,ArrayList必須調整索引順序,而LinkedList必須走訪元素以確認索引,因此都是O(n);indexOf(o)必須逐一比對元素,所以也都會是O(n),在指定索引以取得元素的get(i)操作上,ArrayList會是O(1),而LinkedList會是O(n)。

基於以上資料結構的實作特性,也可以推斷出相關類型的變化實作與操作可能耗費的成本。例如Queue或Deque亦有陣列或鏈結相關實作,而LinkedHashSet本身實作了Set介面,內部使用雜湊與鏈結實作,鏈結主要是用來維護迭代順序,使迭代時的元素順序為新增元素時的順序,因此add(o)、contains(o)與remove(o)與HashSet的對應操作同為O(1),然而使用Iterator的next逐一迭代元素時會是O(1)。

如果要管理一組元素,多數開發者會直覺使用List。

然而若該組元素是無序的,且沒有迭代整組元素的需求,應該使用HashSet而不是List相關實作,因為在add(o)、contains(o)、remove(o)都會有很好的表現,然而耗用的記憶體較多。如果元素具有自然順序(Natural order),則可以使用TreeSet。如果元素是有索引順序的,那麼可使用ArrayList或LinkedList,若元素索引不常變動,且經常要隨機指定索引取得元素,那麼使用ArrayList;如果經常要從前端移除元素,那就使用LinkedList。

從基本資料結構延伸而出的型態
有些問題可使用List、Set以及Map等資料型態與相關實作解決,但會撰寫出複雜邏輯。例如想要統計學生考試分數中,每個得分各有幾人,雖然基本上可以使用Map的juni來實現,像是for(Integer score : scores) { juni.put(score, juni.get(score) == null ? 1 : juni.get(score) + 1); }。最後juni.get(93)就可得知93分的人數。

然而這個需求實際上需要的容器,像是個可以分類的袋子(Bag),將重複元素加以分類,最後可詢問各分類的元素個數。

guava-libraries對此一型態的實現為Multiset(實際上不是Set,它是Collection的子介面),例如相同需求可以Multiset scoresMultiset = HashMultiset.create()建立HashMultiset實作,接著scoresMultiset.addAll(scores)在Multiset中,加入所有分數,然後以scoresMultiset.count(93),來取得93分的人數。

經常地,對於Map中的一個鍵會想要有多個對應的值。

例如想統計全國各年度多個地區的最高溫,會想要有{1949=[111, 78, ...], 1950=[22, 30, ...], ...}這種以年份為鍵,而一組各地區最高溫為值的結構。基本上,可以使用Map>或Map>,來組合出具有{k1=[v1, v2, v3], k2=[v4, v5, v6],....}的對應關係。guava-libraries對此一型態的實現為Multimap(實際不是Map,它沒有繼承自任何介面),例如可以用Multimap yearToTempers = HashMultimap.create()建立Multimap的實作物件,其put(k, v)方法可以將相同鍵的多個物件管理在一個Collection中,get(k)方法可以取得鍵對應的Colleciton物件。

Map基本上是單向關聯,由鍵對應至值,然而有時會想要從值對應至鍵,也就是想要類似一對一雙向關聯的操作。

解決方法之一,是透過Map的entrySet方法取回一組Map.Entry,在迭代過程中藉由Map.Entry的getValue判斷是否為指定的值,若是則使用getKey取得對應的鍵。guava-libraries對此一型態的實現為BiMap(為Map的子介面),其實作物件的inverse方法可以對調鍵與值,例如若原BiMap的鍵為學生而值為宿舍,inverse傳回的BiMap實作物件,就會以宿舍作為鍵,而學生作為值的部份。

不重複打造輪子不代表可忽略理論基礎
現代開發者也許沒什麼機會對相關理論進行實作,非必要也不建議重新打造輪子,畢竟許多程式庫都經過一定數量的驗證,自行實作未必能加以超越,然而這並不代表程式設計只能是組裝過程。忽略理論基礎中的特性,容易選用不正確資料結構、採用了不正確的預設值。

實務開發若能以理論為基礎,可改進程式運行的時間與空間等效能議題,也會有能力,選用正確輪子,或者自行封裝程式,改進可讀性,提高程式開發效率。

 

作者簡介


Advertisement

更多 iThome相關內容