<rt id="bn8ez"></rt>
<label id="bn8ez"></label>

  • <span id="bn8ez"></span>

    <label id="bn8ez"><meter id="bn8ez"></meter></label>

    蘋果的成長日記

    我還是個青蘋果呀!

      BlogJava :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理 ::
      57 隨筆 :: 0 文章 :: 74 評論 :: 0 Trackbacks
    SDK提供了有序集合接口java.util.List的幾種實現,其中三種最為人們熟知的是Vector、ArrayList和LinkedList。有關這些List類的性能差別是一個經常被問及的問題。在這篇文章中,我要探討的就是LinkedList和Vector/ArrayList之間的性能差異。

    為全面分析這些類之間的性能差異,我們必須知道它們的實現方法。因此,接下來我首先從性能的角度出發,簡要介紹這些類的實現特點。

    一、Vector和ArrayList的實現

    Vector和ArrayList都帶有一個底層的Object[]數組,這個Object[]數組用來保存元素。通過索引訪問元素時,只需簡單地通過索引訪問內部數組的元素:

    public Object get(int index)
    { //首先檢查index是否合法...此處不顯示這部分代碼 return
    elementData[index]; }


    內部數組可以大于Vector/ArrayList對象擁有元素的數量,兩者的差值作為剩余空間,以便實現快速添加新元素。有了剩余空間,添加元素變得非常簡單,只需把新的元素保存到內部數組中的一個空余的位置,然后為新的空余位置增加索引值:

    public boolean add(Object o)
    { ensureCapacity(size + 1); //稍后介紹 elementData[size++] = o; return true;
    //List.add(Object) 的返回值 }


    把元素插入集合中任意指定的位置(而不是集合的末尾)略微復雜一點:插入點之后的所有數組元素都必須向前移動一個位置,然后才能進行賦值:

    public void add(int index, Object element) {
    //首先檢查index是否合法...此處不顯示這部分代碼
    ensureCapacity(size+1);
    System.arraycopy(elementData, index, elementData, index + 1,
    size - index);
    elementData[index] = element;
    size++;
    }


    剩余空間被用光時,如果需要加入更多的元素,Vector/ArrayList對象必須用一個更大的新數組替換其內部Object[]數組,把所有的數組元素復制到新的數組。根據SDK版本的不同,新的數組要比原來的大50%或者100%(下面顯示的代碼把數組擴大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類的主要不同之處在于同步除了兩個只用于串行化的方法,沒有一個ArrayList的方法具有同步執行的能力;相反,Vector的大多數方法具有同步能力,或直接或間接。因此,Vector是線程安全的,但ArrayList不是這使得ArrayList要比Vector快速。對于一些最新的JVM,兩個類在速度上的差異可以忽略不計:嚴格地說,對于這些JVM,這兩個類在速度上的差異小于比較這些類性能的測試所顯示的時間差異。

    通過索引訪問和更新元素時,Vector和ArrayList的實現有著卓越的性能,因為不存在除范圍檢查之外的其他開銷。除非內部數組空間耗盡必須進行擴展,否則,向列表的末尾添加元素或者從列表的末尾刪除元素時,都同樣有著優秀的性能。插入元素和刪除元素總是要進行數組復制(當數組先必須進行擴展時,需要兩次復制)。被復制元素的數量和[size-index]成比例,即和插入/刪除點到集合中最后索引位置之間的距離成比例。對于插入操作,把元素插入到集合最前面(索引0)時性能最差,插入到集合最后面時(最后一個現有元素之后)時性能最好。隨著集合規模的增大,數組復制的開銷也迅速增加,因為每次插入操作必須復制的元素數量增加了。

    二、LinkedList的實現

    LinkedList通過一個雙向鏈接的節點列表實現。要通過索引訪問元素,你必須查找所有節點,直至找到目標節點:

    public Object get(intindex) {
    //首先檢查index是否合法...此處不顯示這部分代碼
    Entry e = header; //開始節點
    //向前或者向后查找,具體由哪一個方向距離較
    //近決定
    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;
    }


    把元素插入列表很簡單:找到指定索引的節點,然后緊靠該節點之前插入一個新節點:


    public void add(int index, Object element) {
    //首先檢查index是否合法...此處不顯示這部分代碼
    Entry e = header; //starting node
    //向前或者向后查找,具體由哪一個方向距離較
    //近決定
    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得到一個線程安全的LinkedList,你可以利用一個同步封裝器從Collections.synchronizedList(List)得到一個。然而,使用同步封裝器相當于加入了一個間接層,它會帶來昂貴的性能代價。當封裝器把調用傳遞給被封裝的方法時,每一個方法都需要增加一次額外的方法調用,經過同步封裝器封裝的方法會比未經封裝的方法慢二到三倍。對于象搜索之類的復雜操作,這種間接調用所帶來的開銷不是很突出;但對于比較簡單的方法,比如訪問功能或者更新功能,這種開銷可能對性能造成嚴重的影響。

    這意味著,和Vector相比,經過同步封裝的LinkedList在性能上處于顯著的劣勢,因為Vector不需要為了線程安全而進行任何額外的間接調用。如果你想要有一個線程安全的LinkedList,你可以復制LinkedList類并讓幾個必要的方法同步,這樣你可以得到一個速度更快的實現。對于所有其它集合類,這一點都同樣有效:只有List和Map具有高效的線程安全實現(分別是Vector和Hashtable類)。有趣的是,這兩個高效的線程安全類的存在只是為了向后兼容,而不是出于性能上的考慮。

    對于通過索引訪問和更新元素,LinkedList實現的性能開銷略大一點,因為訪問任意一個索引都要求跨越多個節點。插入元素時除了有跨越多個節點的性能開銷之外,還要有另外一個開銷,即創建節點對象的開銷。在優勢方面,LinkedList實現的插入和刪除操作沒有其他開銷,因此,插入-刪除開銷幾乎完全依賴于插入-刪除點離集合末尾的遠近。

    三、性能測試

    這些類有許多不同的功能可以進行測試。LinkedList應用比較頻繁,因為人們認為它在隨機插入和刪除操作時具有較好的性能。所以,下面我分析的重點將是插入操作的性能,即,構造集合。我測試并比較了LinkedList和ArrayList,因為這兩者都是非同步的。

    插入操作的速度主要由集合的大小和元素插入的位置決定。當插入點的位置在集合的兩端和中間時,最差的插入性能和最好的插入性能都有機會出現。因此,我選擇了三個插入位置(集合的開頭、末尾和中間),三種典型的集合大小:中等(100個元素),大型(10,000個元素),超大型(1,000,000個元素)。

    在本文的測試中,我使用的是JAVA SDK 1.2.0和1.3.0系列的SUN JVM。此外,我還用HOTSPOT JVM 2.0進行了測試,這個版本可以在1.3.0 SDK找到。在下面的表格中,各個測量得到的時間都以其中一次SDK 1.2 VM上的測試時間(表格中顯示為100%的單元)為基準顯示。測試期間使用了默認的JVM配置,即啟用了JIT編譯,因此對于所有JVM,堆空間都必須進行擴展,以避免內存溢出錯誤。表格中記錄的時間是多次測試的平均時間。為了避免垃圾收集的影響,在各次測試之間我強制進行了完全的內存清理(參見測試源代碼了解詳情)。磁盤監測確保磁盤分頁不會在測試過程中出現(任何測試,如果它顯示出嚴重的磁盤分頁操作,則被丟棄)。所有顯示出數秒應答時間的速度太慢的測試都重復進行,直至記錄到一個明顯合理的時間。

    表1:構造一個中等大小的集合(100個元素)。括號中的數字針對預先確定大小的集合。
      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%


    對于規模較小的集合,ArrayList和LinkedList的性能很接近。當元素插入到集合的末尾時,即追加元素時,ArrayList的性能出現了突變。然而,追加元素是ArrayList特別為其優化的一個操作:如果你只想要一個固定大小的靜態集合,Java數組(例如Object[])比任何集合對象都具有更好的性能。除了追加操作,測量得到的時間數據差別不是很大,它們反映了各個JVM的優化程度,而不是其他什么東西。

    例如,對于把元素插入到集合的開始位置來說(表1的前兩行),HotSpot 2.0 JVM加LinkedList具有最好的性能(85.3%),處于第二位的是 1.2 JVM加ArrayList(100%)。這兩個結果顯示出,1.2中簡單的JIT編譯器在執行迭代和復制數組等簡單的操作時具有很高的效率。在HotSpot中復雜的JVM加上優化的編譯器能夠改進復雜操作的性能,比如對象創建(創建LinkedList節點),并能夠利用代碼內嵌(code-inlining)的優勢。1.3 JVM的結果似乎顯示出,在簡單操作方面它的性能有著很大的不足,這一點很可能在以后的JVM版本中得到改進。

    在這里我特別進行測試的是ArrayList相對于LinkedList的另一個優點,即預先確定集合大小的能力。具體地說,創建ArrayList的時候允許指定一個具體的大小(例如,在測試中ArrayList可以創建為擁有100個元素的容量),從而避免所有隨著元素增多而增加集合規模的開銷。表1括號中的數字顯示了預先確定集合大小時性能的提高程度。LinkedList(直到 SDK 1.3)不能預先確定大小。

    此外,ArrayList只生成少量的需要進行垃圾收集的對象,即,用來保存元素的內部數組對象,以及每次ArrayList容量不足需要進行擴展時創建的附加內部數組對象。LinkedList不管可能出現的任何刪除操作,都為每一個插入操作生成一個節點對象。因此,LinkedList會給垃圾收集器帶來相當多的工作。考慮到這些因素,對于任何中小規模的集合,我會選擇使用ArrayList而不是LinkedList。

    表2:構造一個大型集合(10,000個元素)
      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顯示了大規模集合的測試結果。可以看到,在出現大規模插入操作的時候,我們開始遭遇嚴厲的性能懲罰。正如我們前面分析類的實現所得到的結果,對于LinkedList來說最差的情形出現在把元素插入到集合中間時。另外我們還可以看到,與使用ArrayList時把元素插入到集合開頭的最差性能相比,使用LinkedList時把元素插入到集合中間的性能更差一些。和這兩種性能最差的情況相比,把元素插入到ArrayList中間的性能顯然要好得多。

    總地看來,ArrayList再一次在大多數情形下表現出更好的性能,包括根據索引把元素插入到隨機位置的情形。如果你總是要把元素插入到集合中靠前的位置,LinkedList具有更好的性能;然而,此時你可以利用一個反向的ArrayList得到更好的性能,即,使用一個專用的實現,或者通過[size -index]映射翻轉索引在集合中的位置。


    表3:構造一個超大集合(1,000,000個元素)
      1.2 JVM 1.3 JVM HotSpot 2.0 JVM
    總是插入到ArrayList的開頭 太長 太長 太長
    總是插入到LinkedList的開頭 100% 179.5% 144.1%
    總是插入到ArrayList的中間 太長 太長 太長
    總是插入到LinkedList的中間 太長 太長 太長
    總是插入到ArrayList的末尾 38.3% 47.7% 42.9%
    總是插入到LinkedList的末尾 65.1% 161.5% 139.9%


    表3顯示了超大集合的測試結果,從該表可以得出的結論與表2非常相似。然而,表3強調的是,超大集合要求數據、集合類型、數據處理算法之間的恰到好處的配合;否則,你將得到事實上不可接受的性能表現。至于性能優化,你可以構造一個針對該問題的專用集合類。對于超大集合來說,為了獲得可接受的性能,構造專用集合類往往是很有必要的。

    四、查詢的性能

    在類的內部實現查詢時查詢的性能最高。對于查詢這些列表來說,迭代所有元素所需要的時間是一個限制因素。ArrayList/Vector類中實現的查詢將對類的元素進行迭代。下面的例子計算空元素的總數量:

    int count = 0;
    for (int i = 0; i < size; i++)
    if(elementData[i] == null)
    count++;LinkedList類中實現的查詢將搜索所有的節點。下面的例子計算所有空元素的總數量:
    node = header.next;
    count = 0;
    for (int i = 0; i < repeat; i++, node = node.next)
    if (node.element == null)
    count++;


    表4顯示出,ArrayList的性能顯著地超過了LinkedList,它再一次顯示出ArrayList應該是我們首選的類。表5顯示了利用從List.listIterator(int)獲得的ListIterator對象迭代所有元素所需要的時間,如果查詢機制不能在List內部實現,這些迭代器是必需的。ArrayList再一次顯示出了較高的性能,但這次性能的差異程度不象表4顯示的那樣不可思議。注意,表5所顯示的絕對時間相當于表4顯示絕對時間的10倍,即,ArrayList內部遍歷大約比ArrayList利用ListIterator迭代要快10倍。


    表4:通過內部訪問迭代集合中的所有元素
      1.2 JVM 1.3 JVM HotSpot 2.0 JVM
    ArrayList內部搜索 100% 106% 197%
    LinkedList內部搜索 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%


    結束語

    實際測量和我們所考慮的其他因素都清楚地顯示出,ArrayList和Vector通常比LinkedList和同步封裝之后的LinkedList有著更好的性能。即使在你認為LinkedList可能提供更高性能的情況下,你也可以通過修改元素加入的方式從ArrayList爭取更好的性能,例如翻轉集合元素的次序。

    有些情況下LinkedList會有更好的性能,例如,當大量元素需要同時加入到大型集合的開頭和末尾時。但一般而言,我建議你優先使用ArrayList/Vector類,只有當它們存在明顯的性能問題而LinkedList能夠改進性能時,才使用LinkedList。
    posted on 2005-06-23 21:07 蘋果 閱讀(349) 評論(1)  編輯  收藏 所屬分類: J2EE/JAVA學習

    評論

    # re: 【轉載至賽迪網】Java列表對象的性能分析和測試 2005-06-23 21:09 蘋果
    Java Q&A

    Vector or ArrayList -- which is better?
    Find out the difference between Vector and ArrayList

    By Tony Sintes

    Printer-friendly version | Mail this to a friend


    Vector or ArrayList -- which is better and why?

    Sometimes Vector is better; sometimes ArrayList is better; sometimes you don't want to use either. I hope you weren't looking for an easy answer because the answer depends upon what you are doing. There are four factors to consider:


    API
    Synchronization
    Data growth
    Usage patterns
    Let's explore each in turn.

    API
    In The Java Programming Language (Addison-Wesley, June 2000) Ken Arnold, James Gosling, and David Holmes describe the Vector as an analog to the ArrayList. So, from an API perspective, the two classes are very similar. However, there are still some major differences between the two classes.

    Synchronization
    Vectors are synchronized. Any method that touches the Vector's contents is thread safe. ArrayList, on the other hand, is unsynchronized, making them, therefore, not thread safe. With that difference in mind, using synchronization will incur a performance hit. So if you don't need a thread-safe collection, use the ArrayList. Why pay the price of synchronization unnecessarily?

    Data growth
    Internally, both the ArrayList and Vector hold onto their contents using an Array. You need to keep this fact in mind while using either in your programs. When you insert an element into an ArrayList or a Vector, the object will need to expand its internal array if it runs out of room. A Vector defaults to doubling the size of its array, while the ArrayList increases its array size by 50 percent. Depending on how you use these classes, you could end up taking a large performance hit while adding new elements. It's always best to set the object's initial capacity to the largest capacity that your program will need. By carefully setting the capacity, you can avoid paying the penalty needed to resize the internal array later. If you don't know how much data you'll have, but you do know the rate at which it grows, Vector does possess a slight advantage since you can set the increment value.

    Usage patterns
    Both the ArrayList and Vector are good for retrieving elements from a specific position in the container or for adding and removing elements from the end of the container. All of these operations can be performed in constant time -- O(1). However, adding and removing elements from any other position proves more expensive -- linear to be exact: O(n-i), where n is the number of elements and i is the index of the element added or removed. These operations are more expensive because you have to shift all elements at index i and higher over by one element. So what does this all mean?

    It means that if you want to index elements or add and remove elements at the end of the array, use either a Vector or an ArrayList. If you want to do anything else to the contents, go find yourself another container class. For example, the LinkedList can add or remove an element at any position in constant time -- O(1). However, indexing an element is a bit slower -- O(i) where i is the index of the element. Traversing an ArrayList is also easier since you can simply use an index instead of having to create an iterator. The LinkedList also creates an internal object for each element inserted. So you have to be aware of the extra garbage being created.

    Finally, in "PRAXIS 41" from Practical Java (Addison-Wesley, Feb. 2000) Peter Haggar suggests that you use a plain old array in place of either Vector or ArrayList -- especially for performance-critical code. By using an array you can avoid synchronization, extra method calls, and suboptimal resizing. You just pay the cost of extra development time.

      回復  更多評論
      

    主站蜘蛛池模板: 青柠影视在线观看免费高清 | 亚洲成在人线av| 一级免费黄色毛片| 亚洲AV无码成H人在线观看| 久久久久久久久无码精品亚洲日韩| 色窝窝免费一区二区三区| 亚洲一区在线视频| 一二三四免费观看在线电影| 亚洲免费视频播放| www.黄色免费网站| 亚洲七久久之综合七久久| 四虎永久免费地址在线网站| 男女啪啪免费体验区| 中文字幕不卡亚洲| 少妇人妻偷人精品免费视频| 亚洲中文字幕久在线| 日韩中文字幕免费| 一级特黄a大片免费| 亚洲乱亚洲乱妇无码麻豆| 99视频精品全部免费观看| 亚洲免费视频网址| 国产一级一片免费播放i| 国产V片在线播放免费无码 | www.999精品视频观看免费| 亚洲国产精品无码久久九九大片| 免费人成年轻人电影| a在线免费观看视频| 亚洲中文字幕在线无码一区二区| 国产免费直播在线观看视频| 国产精品hd免费观看| 亚洲毛片在线免费观看| 国产大片51精品免费观看| 国产高清视频免费在线观看 | 免费无码又爽又刺激网站| 亚洲精品国产情侣av在线| 国产大片91精品免费看3| 日本在线免费观看| 亚洲av永久无码精品秋霞电影秋 | 成人免费视频国产| a毛片免费观看完整| 亚洲日韩精品国产3区|