|
仙人掌工作室
SDK提供了有序集合接口java.util.List的幾種實(shí)現(xiàn)，其中三種最為人們熟知的是Vector、ArrayList和LinkedList。有關(guān)這些List類的性能差別是一個(gè)經(jīng)常被問及的問題。在這篇文章中，我要探討的就是LinkedList和Vector/ArrayList之間的性能差異。
為全面分析這些類之間的性能差異，我們必須知道它們的實(shí)現(xiàn)方法。因此，接下來我首先從性能的角度出發(fā)，簡(jiǎn)要介紹這些類的實(shí)現(xiàn)特點(diǎn)。
一、Vector和ArrayList的實(shí)現(xiàn)
Vector和ArrayList都帶有一個(gè)底層的Object[]數(shù)組，這個(gè)Object[]數(shù)組用來保存元素。通過索引訪問元素時(shí)，只需簡(jiǎn)單地通過索引訪問內(nèi)部數(shù)組的元素：
public Object get(int index)
{ //首先檢查index是否合法...此處不顯示這部分代碼 return
elementData[index]; }
內(nèi)部數(shù)組可以大于Vector/ArrayList對(duì)象擁有元素的數(shù)量，兩者的差值作為剩余空間，以便實(shí)現(xiàn)快速添加新元素。有了剩余空間，添加元素變得非常簡(jiǎn)單，只需把新的元素保存到內(nèi)部數(shù)組中的一個(gè)空余的位置，然后為新的空余位置增加索引值：
public boolean add(Object o)
{ ensureCapacity(size + 1); //稍后介紹 elementData[size++] = o; return true;
//List.add(Object) 的返回值 }
把元素插入集合中任意指定的位置（而不是集合的末尾）略微復(fù)雜一點(diǎn)：插入點(diǎn)之上的所有數(shù)組元素都必須向前移動(dòng)一個(gè)位置，然后才能進(jìn)行賦值：
public void add(int index, Object element) {
//首先檢查index是否合法...此處不顯示這部分代碼
ensureCapacity(size+1);
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
剩余空間被用光時(shí)，如果需要加入更多的元素，Vector/ArrayList對(duì)象必須用一個(gè)更大的新數(shù)組替換其內(nèi)部Object[]數(shù)組，把所有的數(shù)組元素復(fù)制到新的數(shù)組。根據(jù)SDK版本的不同，新的數(shù)組要比原來的大50%或者100%（下面顯示的代碼把數(shù)組擴(kuò)大100%）：
public void ensureCapacity(int minCapacity) {
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = Math.max(oldCapacity * 2, minCapacity);
elementData = new Object[newCapacity];
System.arraycopy(oldData, 0, elementData, 0, size);
}
}
Vector類和ArrayList類的主要不同之處在于同步。除了兩個(gè)只用于串行化的方法，沒有一個(gè)ArrayList的方法具有同步執(zhí)行的能力；相反，Vector的大多數(shù)方法具有同步能力，或直接或間接。因此，Vector是線程安全的，但ArrayList不是。這使得ArrayList要比Vector快速。對(duì)于一些最新的JVM，兩個(gè)類在速度上的差異可以忽略不計(jì)：嚴(yán)格地說，對(duì)于這些JVM，這兩個(gè)類在速度上的差異小于比較這些類性能的測(cè)試所顯示的時(shí)間差異。
通過索引訪問和更新元素時(shí)，Vector和ArrayList的實(shí)現(xiàn)有著卓越的性能，因?yàn)椴淮嬖诔秶鷻z查之外的其他開銷。除非內(nèi)部數(shù)組空間耗盡必須進(jìn)行擴(kuò)展，否則，向列表的末尾添加元素或者從列表的末尾刪除元素時(shí)，都同樣有著優(yōu)秀的性能。插入元素和刪除元素總是要進(jìn)行數(shù)組復(fù)制（當(dāng)數(shù)組先必須進(jìn)行擴(kuò)展時(shí)，需要兩次復(fù)制）。被復(fù)制元素的數(shù)量和[size-index]成比例，即和插入/刪除點(diǎn)到集合中最后索引位置之間的距離成比例。對(duì)于插入操作，把元素插入到集合最前面（索引0）時(shí)性能最差，插入到集合最后面時(shí)（最后一個(gè)現(xiàn)有元素之后）時(shí)性能最好。隨著集合規(guī)模的增大，數(shù)組復(fù)制的開銷也迅速增加，因?yàn)槊看尾迦氩僮鞅仨殢?fù)制的元素?cái)?shù)量增加了。
二、LinkedList的實(shí)現(xiàn)
LinkedList通過一個(gè)雙向鏈接的節(jié)點(diǎn)列表實(shí)現(xiàn)。要通過索引訪問元素，你必須查找所有節(jié)點(diǎn)，直至找到目標(biāo)節(jié)點(diǎn)：
public Object get(intindex) {
//首先檢查index是否合法...此處不顯示這部分代碼
Entry e = header; //開始節(jié)點(diǎn)
//向前或者向后查找，具體由哪一個(gè)方向距離較
//近決定
if (index < size/2) {
for (int i = 0; i <= index; i++)
e = e.next;
} else {
for (int i = size; i > index; i--)
e = e.previous;
}
return e;
}
把元素插入列表很簡(jiǎn)單：找到指定索引的節(jié)點(diǎn)，然后緊靠該節(jié)點(diǎn)之前插入一個(gè)新節(jié)點(diǎn)：
public void add(int index, Object element) {
//首先檢查index是否合法...此處不顯示這部分代碼
Entry e = header; //starting node
//向前或者向后查找，具體由哪一個(gè)方向距離較
//近決定
if (index < size/2) {
for (int i = 0; i <= index; i++)
e = e.next;
} else {
for (int i = size; i > index; i--)
e = e.previous;
}
Entry newEntry = new Entry(element, e, e.previous);
newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
size++;
}
線程安全的LinkedList和其他集合
如果要從Java SDK得到一個(gè)線程安全的LinkedList，你可以利用一個(gè)同步封裝器從Collections.synchronizedList(List)得到一個(gè)。然而，使用同步封裝器相當(dāng)于加入了一個(gè)間接層，它會(huì)帶來昂貴的性能代價(jià)。當(dāng)封裝器把調(diào)用傳遞給被封裝的方法時(shí)，每一個(gè)方法都需要增加一次額外的方法調(diào)用，經(jīng)過同步封裝器封裝的方法會(huì)比未經(jīng)封裝的方法慢二到三倍。對(duì)于象搜索之類的復(fù)雜操作，這種間接調(diào)用所帶來的開銷不是很突出；但對(duì)于比較簡(jiǎn)單的方法，比如訪問功能或者更新功能，這種開銷可能對(duì)性能造成嚴(yán)重的影響。
這意味著，和Vector相比，經(jīng)過同步封裝的LinkedList在性能上處于顯著的劣勢(shì)，因?yàn)閂ector不需要為了線程安全而進(jìn)行任何額外的間接調(diào)用。如果你想要有一個(gè)線程安全的LinkedList，你可以復(fù)制LinkedList類并讓幾個(gè)必要的方法同步，這樣你可以得到一個(gè)速度更快的實(shí)現(xiàn)。對(duì)于所有其它集合類，這一點(diǎn)都同樣有效：只有List和Map具有高效的線程安全實(shí)現(xiàn)（分別是Vector和Hashtable類）。有趣的是，這兩個(gè)高效的線程安全類的存在只是為了向后兼容，而不是出于性能上的考慮。
對(duì)于通過索引訪問和更新元素，LinkedList實(shí)現(xiàn)的性能開銷略大一點(diǎn)，因?yàn)樵L問任意一個(gè)索引都要求跨越多個(gè)節(jié)點(diǎn)。插入元素時(shí)除了有跨越多個(gè)節(jié)點(diǎn)的性能開銷之外，還要有另外一個(gè)開銷，即創(chuàng)建節(jié)點(diǎn)對(duì)象的開銷。在優(yōu)勢(shì)方面，LinkedList實(shí)現(xiàn)的插入和刪除操作沒有其他開銷，因此，插入-刪除開銷幾乎完全依賴于插入-刪除點(diǎn)離集合末尾的遠(yuǎn)近。
三、性能測(cè)試
這些類有許多不同的功能可以進(jìn)行測(cè)試。LinkedList應(yīng)用比較頻繁，因?yàn)槿藗冋J(rèn)為它在隨機(jī)插入和刪除操作時(shí)具有較好的性能。所以，下面我分析的重點(diǎn)將是插入操作的性能，即，構(gòu)造集合。我測(cè)試并比較了LinkedList和ArrayList，因?yàn)檫@兩者都是非同步的。
插入操作的速度主要由集合的大小和元素插入的位置決定。當(dāng)插入點(diǎn)的位置在集合的兩端和中間時(shí)，最差的插入性能和最好的插入性能都有機(jī)會(huì)出現(xiàn)。因此，我選擇了三個(gè)插入位置（集合的開頭、末尾和中間），三種典型的集合大小：中等（100個(gè)元素），大型（10,000個(gè)元素），超大型（1,000,000個(gè)元素）。
在本文的測(cè)試中，我使用的是JAVA SDK 1.2.0和1.3.0系列的SUN JVM。此外，我還用HOTSPOT JVM 2.0進(jìn)行了測(cè)試，這個(gè)版本可以在1.3.0 SDK找到。在下面的表格中，各個(gè)測(cè)量得到的時(shí)間都以其中一次SDK 1.2 VM上的測(cè)試時(shí)間（表格中顯示為100%的單元）為基準(zhǔn)顯示。測(cè)試期間使用了默認(rèn)的JVM配置，即啟用了JIT編譯，因此對(duì)于所有JVM，堆空間都必須進(jìn)行擴(kuò)展，以避免內(nèi)存溢出錯(cuò)誤。表格中記錄的時(shí)間是多次測(cè)試的平均時(shí)間。為了避免垃圾收集的影響，在各次測(cè)試之間我強(qiáng)制進(jìn)行了完全的內(nèi)存清理（參見測(cè)試源代碼了解詳情）。磁盤監(jiān)測(cè)確保磁盤分頁(yè)不會(huì)在測(cè)試過程中出現(xiàn)（任何測(cè)試，如果它顯示出嚴(yán)重的磁盤分頁(yè)操作，則被丟棄）。所有顯示出數(shù)秒應(yīng)答時(shí)間的速度太慢的測(cè)試都重復(fù)進(jìn)行，直至記錄到一個(gè)明顯合理的時(shí)間。
表1：構(gòu)造一個(gè)中等大小的集合（100個(gè)元素）。括號(hào)中的數(shù)字針對(duì)預(yù)先確定大小的集合。
1.2 JVM 1.3 JVM HotSpot 2.0 JVM
總是插入到ArrayList的開頭 100% (48.0%) 184.9% (152.0%) 108.0% (66.7%)
總是插入到LinkedList的開頭 135.5% 109.1% 85.3%
總是插入到ArrayList的中間 130.0% (40.6%) 187.4% (158.0%) 84.7% (46.0%)
總是插入到LinkedList的中間 174.0% 135.0% 102.3%
總是插入到ArrayList的末尾 63.3% (20.7%) 65.9% (25.0%) 60.3% (29.3%)
總是插入到LinkedList的末尾 106.7% 86.3% 80.3%
對(duì)于規(guī)模較小的集合，ArrayList和LinkedList的性能很接近。當(dāng)元素插入到集合的末尾時(shí)，即追加元素時(shí)，ArrayList的性能出現(xiàn)了突變。然而，追加元素是ArrayList特別為其優(yōu)化的一個(gè)操作：如果你只想要一個(gè)固定大小的靜態(tài)集合，Java數(shù)組（例如Object[]）比任何集合對(duì)象都具有更好的性能。除了追加操作，測(cè)量得到的時(shí)間數(shù)據(jù)差別不是很大，它們反映了各個(gè)JVM的優(yōu)化程度，而不是其他什么東西。
例如，對(duì)于把元素插入到集合的開始位置來說（表1的前兩行），HotSpot 2.0 JVM加LinkedList具有最好的性能（85.3%），處于第二位的是 1.2 JVM加ArrayList（100%）。這兩個(gè)結(jié)果顯示出，1.2中簡(jiǎn)單的JIT編譯器在執(zhí)行迭代和復(fù)制數(shù)組等簡(jiǎn)單的操作時(shí)具有很高的效率。在HotSpot中復(fù)雜的JVM加上優(yōu)化的編譯器能夠改進(jìn)復(fù)雜操作的性能，比如對(duì)象創(chuàng)建（創(chuàng)建LinkedList節(jié)點(diǎn)），并能夠利用代碼內(nèi)嵌（code-inlining）的優(yōu)勢(shì)。1.3 JVM的結(jié)果似乎顯示出，在簡(jiǎn)單操作方面它的性能有著很大的不足，這一點(diǎn)很可能在以后的JVM版本中得到改進(jìn)。
在這里我特別進(jìn)行測(cè)試的是ArrayList相對(duì)于LinkedList的另一個(gè)優(yōu)點(diǎn)，即預(yù)先確定集合大小的能力。具體地說，創(chuàng)建ArrayList的時(shí)候允許指定一個(gè)具體的大小（例如，在測(cè)試中ArrayList可以創(chuàng)建為擁有100個(gè)元素的容量），從而避免所有隨著元素增多而增加集合規(guī)模的開銷。表1括號(hào)中的數(shù)字顯示了預(yù)先確定集合大小時(shí)性能的提高程度。LinkedList（直到 SDK 1.3）不能預(yù)先確定大小。
此外，ArrayList只生成少量的需要進(jìn)行垃圾收集的對(duì)象，即，用來保存元素的內(nèi)部數(shù)組對(duì)象，以及每次ArrayList容量不足需要進(jìn)行擴(kuò)展時(shí)創(chuàng)建的附加內(nèi)部數(shù)組對(duì)象。LinkedList不管可能出現(xiàn)的任何刪除操作，都為每一個(gè)插入操作生成一個(gè)節(jié)點(diǎn)對(duì)象。因此，LinkedList會(huì)給垃圾收集器帶來相當(dāng)多的工作。考慮到這些因素，對(duì)于任何中小規(guī)模的集合，我會(huì)選擇使用ArrayList而不是LinkedList。
表2：構(gòu)造一個(gè)大型集合（10,000個(gè)元素）
1.2 JVM 1.3 JVM HotSpot 2.0 JVM
總是插入到ArrayList的開頭 7773% 7537% 7500%
總是插入到LinkedList的開頭 100% 90.34% 65.6%
總是插入到ArrayList的中間 3318% 3412% 3121%
總是插入到LinkedList的中間 26264% 14315% 14209%
總是插入到ArrayList的末尾 41.4% 41.2% 37.5%
總是插入到LinkedList的末尾 66.4% 73.9% 61.7%
表2顯示了大規(guī)模集合的測(cè)試結(jié)果。可以看到，在出現(xiàn)大規(guī)模插入操作的時(shí)候，我們開始遭遇嚴(yán)厲的性能懲罰。正如我們前面分析類的實(shí)現(xiàn)所得到的結(jié)果，對(duì)于LinkedList來說最差的情形出現(xiàn)在把元素插入到集合中間時(shí)。另外我們還可以看到，與使用ArrayList時(shí)把元素插入到集合開頭的最差性能相比，使用LinkedList時(shí)把元素插入到集合中間的性能更差一些。和這兩種性能最差的情況相比，把元素插入到ArrayList中間的性能顯然要好得多。
總地看來，ArrayList再一次在大多數(shù)情形下表現(xiàn)出更好的性能，包括根據(jù)索引把元素插入到隨機(jī)位置的情形。如果你總是要把元素插入到集合中靠前的位置，LinkedList具有更好的性能；然而，此時(shí)你可以利用一個(gè)反向的ArrayList得到更好的性能，即，使用一個(gè)專用的實(shí)現(xiàn)，或者通過[size -index]映射翻轉(zhuǎn)索引在集合中的位置。
表3：構(gòu)造一個(gè)超大集合（1,000,000個(gè)元素）
1.2 JVM 1.3 JVM HotSpot 2.0 JVM
總是插入到ArrayList的開頭 太長(zhǎng) 太長(zhǎng) 太長(zhǎng)
總是插入到LinkedList的開頭 100% 179.5% 144.1%
總是插入到ArrayList的中間 太長(zhǎng) 太長(zhǎng) 太長(zhǎng)
總是插入到LinkedList的中間 太長(zhǎng) 太長(zhǎng) 太長(zhǎng)
總是插入到ArrayList的末尾 38.3% 47.7% 42.9%
總是插入到LinkedList的末尾 65.1% 161.5% 139.9%
表3顯示了超大集合的測(cè)試結(jié)果，從該表可以得出的結(jié)論與表2非常相似。然而，表3強(qiáng)調(diào)的是，超大集合要求數(shù)據(jù)、集合類型、數(shù)據(jù)處理算法之間的恰到好處的配合；否則，你將得到事實(shí)上不可接受的性能表現(xiàn)。至于性能優(yōu)化，你可以構(gòu)造一個(gè)針對(duì)該問題的專用集合類。對(duì)于超大集合來說，為了獲得可接受的性能，構(gòu)造專用集合類往往是很有必要的。
四、查詢的性能
在類的內(nèi)部實(shí)現(xiàn)查詢時(shí)查詢的性能最高。對(duì)于查詢這些列表來說，迭代所有元素所需要的時(shí)間是一個(gè)限制因素。ArrayList/Vector類中實(shí)現(xiàn)的查詢將對(duì)類的元素進(jìn)行迭代。下面的例子計(jì)算空元素的總數(shù)量：
int count = 0;
for (int i = 0; i < size; i++)
if(elementData[i] == null)
count++;
LinkedList類中實(shí)現(xiàn)的查詢將搜索所有的節(jié)點(diǎn)。下面的例子計(jì)算所有空元素的總數(shù)量：
node = header.next;
count = 0;
for (int i = 0; i < repeat; i++, node = node.next)
if (node.element == null)
count++;
表4顯示出，ArrayList的性能顯著地超過了LinkedList，它再一次顯示出ArrayList應(yīng)該是我們首選的類。表5顯示了利用從List.listIterator(int)獲得的ListIterator對(duì)象迭代所有元素所需要的時(shí)間，如果查詢機(jī)制不能在List內(nèi)部實(shí)現(xiàn)，這些迭代器是必需的。ArrayList再一次顯示出了較高的性能，但這次性能的差異程度不象表4顯示的那樣不可思議。注意，表5所顯示的絕對(duì)時(shí)間相當(dāng)于表4顯示絕對(duì)時(shí)間的10倍，即，ArrayList內(nèi)部遍歷大約比ArrayList利用ListIterator迭代要快10倍。
表4：通過內(nèi)部訪問迭代集合中的所有元素
1.2 JVM 1.3 JVM HotSpot 2.0 JVM
ArrayList內(nèi)部搜索 100% 106% 197%
LinkedList內(nèi)部搜索 470% 493% 448%
表5：通過ListIterator遍歷集合中的所有元素
1.2 JVM 1.3 JVM HotSpot 2.0 JVM
利用ListIterator迭代ArrayList 100% 118% 75.2%
利用ListIterator迭代ListedList 117% 186% 156%
■ 結(jié)束語(yǔ)
實(shí)際測(cè)量和我們所考慮的其他因素都清楚地顯示出，ArrayList和Vector通常比LinkedList和同步封裝之后的LinkedList有著更好的性能。即使在你認(rèn)為L(zhǎng)inkedList可能提供更高性能的情況下，你也可以通過修改元素加入的方式從ArrayList爭(zhēng)取更好的性能，例如翻轉(zhuǎn)集合元素的次序。
有些情況下LinkedList會(huì)有更好的性能，例如，當(dāng)大量元素需要同時(shí)加入到大型集合的開頭和末尾時(shí)。但一般而言，我建議你優(yōu)先使用ArrayList/Vector類，只有當(dāng)它們存在明顯的性能問題而LinkedList能夠改進(jìn)性能時(shí)，才使用LinkedList。
|
