570
外匯
Java中List效率的比較
inkfish原創，請勿商業性質轉載，轉載請注明來源（https://blog.csdn.net/inkfish ）。
Java Collections Framework(JCF)
是Java SE中一個基本的類集，幾乎所有的項目都會用到，其中的List
則是JCF中最最常用的一個接口。圍繞List
接口，有很多實現，諸如常用的ArrayList
、LinkedList
、Vector
、Stack
，還有Java5之後引入的CopyOnWriteArrayList
，也有不少List
的開源實現，如Apache commons-collections中的各類List
。（來源：https://blog.csdn.net/inkfish）
這麼多的List
實現，如何選擇？他們的運行效率具體怎樣？本篇文章將用具體的代碼來檢測其中最最常用的一些List
實現。（來源：https://blog.csdn.net/inkfish）
測試環境：
處理器：Intel Core 2 Duo P8600 2.4GHz
內存：2G
硬盤：160G 7200rpm
Java：SUN JDK 1.6.0_15
開發環境：Eclipse 3.5
第三方類庫：Apache commons-lang 2.4、Apache commons-collections 3.2.1（來源：https://blog.csdn.net/inkfish）
主要測試對象：
java.util.ArrayList;
（來源：https://blog.csdn.net/inkfish）
java.util.LinkedList;
java.util.Stack;
java.util.Vector;
java.util.concurrent.CopyOnWriteArrayList;
org.apache.commons.collections.FastArrayList;
org.apache.commons.collections.list.TreeList;
測試用例：
1.測試List
1.1順序添加
1.2隨機插入
1.3隨機刪除
1.4隨機訪問
1.5隨機更新
1.5順序迭代
2.測試List
在三種情況下的排序效率
2.1初始時List
中元素已從小到大有序排列（最優情況）
2.2初始時List
中元素已從大到小有序排列（最差情況）
2.3初始時List
中元素隨機排列，無序
3.測試List
互相轉換的效率
3.1轉化為TreeList
3.2轉化為ArrayList
3.3轉化為LinkedList
3.4轉化為CopyOnWriteArrayList
3.5轉化為Vector
（來源：https://blog.csdn.net/inkfish）
測試代碼： （來源：https://blog.csdn.net/inkfish）
package test; import static java.lang.System.out; import java.util.ArrayList; import java.util.Collections; import java.util.Iterator; import java.util.LinkedList; import java.util.List; import java.util.Stack; import java.util.Vector; import java.util.concurrent.CopyOnWriteArrayList; import org.apache.commons.collections.FastArrayList; import org.apache.commons.collections.list.TreeList; import org.apache.commons.lang.StringUtils; import org.apache.commons.lang.time.StopWatch; @SuppressWarnings("unchecked") public class ListPerformance { public static void main(String[] args) { ListPerformance test = new ListPerformance(10 * 10000); out.print(StringUtils.center("Test List Performance: loop=" + test.loop, 80, '-')); out.printf("/n%20s%10s%10s%10s%10s%10s%10s", "", "add", "insert", "remove", "get", "set", "iterator"); test.benchmark(new FastArrayList()); test.benchmark(new TreeList()); test.benchmark(new ArrayList()); test.benchmark(new LinkedList()); test.benchmark(new CopyOnWriteArrayList()); test.benchmark(new Vector()); test.benchmark(new Stack()); //2.測試排序 out.print("/n/n"); out.print(StringUtils.center("Test List sort Performance: loop=" + test.loop, 80, '-')); out.printf("/n%20s%10s%10s%10s", "", "optimize", "worst", "random"); test.benchmarkSort(new FastArrayList()); test.benchmarkSort(new TreeList()); test.benchmarkSort(new ArrayList()); test.benchmarkSort(new LinkedList()); //test.benchmarkSort(new CopyOnWriteArrayList());//UnsupportedOperationException test.benchmarkSort(new Vector()); test.benchmarkSort(new Stack()); //3.測試各種數據結構間轉化 out.print("/n/n"); out.print(StringUtils.center("Test List convert Performance: loop=" + test.loop, 80, '-')); out.printf("/n%20s%10s%10s%10s%10s%10s", "", "Tree", "Array", "Linked", "CopyOnWrite", "Vector"); test.benchmarkConvert(new FastArrayList()); test.benchmarkConvert(new TreeList()); test.benchmarkConvert(new ArrayList()); test.benchmarkConvert(new LinkedList()); test.benchmarkConvert(new CopyOnWriteArrayList()); } /**測試循環次數*/ private int loop = 10000; public ListPerformance(int loop) { this.loop = loop; } public void benchmark(List list) { out.printf("/n%20s", list.getClass().getSimpleName()); int j; StopWatch watch = null; //1.測試順序性能(Add) (watch = new StopWatch()).start(); for (int i = 0; i < loop; i++) { list.add(new Integer(i)); } watch.stop(); out.printf("%10d", watch.getTime()); //2.測試隨機插入性能(Random insert) (watch = new StopWatch()).start(); for (int i = 0; i < loop; i++) { j = (int) (Math.random() * loop); list.add(j, new Integer(-j)); } watch.stop(); out.printf("%10d", watch.getTime()); //3.測試隨機索引刪除(Random remove) (watch = new StopWatch()).start(); for (int i = 0; i < loop; i++) { j = (int) (Math.random() * loop); list.remove(j); } watch.stop(); out.printf("%10d", watch.getTime()); //4.測試隨機取數性能(Random get) (watch = new StopWatch()).start(); for (int i = 0; i < loop; i++) { j = (int) (Math.random() * loop); list.get(j); } watch.stop(); out.printf("%10d", watch.getTime()); //5.測試隨機更新性能(Random set) (watch = new StopWatch()).start(); for (int i = 0; i < loop; i++) { j = (int) (Math.random() * loop); list.set(j, j); } watch.stop(); out.printf("%10d", watch.getTime()); //6.測試迭代性能(Iterator) (watch = new StopWatch()).start(); Iterator<Object> iter = list.iterator(); while (iter.hasNext()) { iter.next(); } watch.stop(); out.printf("%10d", watch.getTime()); } public void benchmarkConvert(List list) { out.printf("/n%20s", list.getClass().getSimpleName()); StopWatch watch = null; //1.轉TreeList (watch = new StopWatch()).start(); new TreeList(list); watch.stop(); out.printf("%10d", watch.getTime()); //2.轉ArrayList (watch = new StopWatch()).start(); new ArrayList(list); watch.stop(); out.printf("%10d", watch.getTime()); //3.轉LinkedList (watch = new StopWatch()).start(); new LinkedList(list); watch.stop(); out.printf("%10d", watch.getTime()); //4.轉CopyOnWriteArrayList (watch = new StopWatch()).start(); new CopyOnWriteArrayList(list); watch.stop(); out.printf("%10d", watch.getTime()); //5.轉Vector (watch = new StopWatch()).start(); new Vector(list); watch.stop(); out.printf("%10d", watch.getTime()); } public void benchmarkSort(List list) { out.printf("/n%20s", list.getClass().getSimpleName()); StopWatch watch = null; //1.順序List for (int i = 0; i < loop; i++) { list.add(new Integer(i)); } (watch = new StopWatch()).start(); Collections.sort(list); watch.stop(); out.printf("%10d", watch.getTime()); //2.逆序List for (int i = loop - 1; i > 0; i--) { list.add(new Integer(i)); } (watch = new StopWatch()).start(); Collections.sort(list); watch.stop(); out.printf("%10d", watch.getTime()); //3.隨機順序List for (int i = 0, j = 0; i < loop; i++) { j = (int) (Math.random() * loop); list.add(new Integer(j)); } (watch = new StopWatch()).start(); Collections.sort(list); watch.stop(); out.printf("%10d", watch.getTime()); } }
測試結果： （來源：https://blog.csdn.net/inkfish）
-----------------------Test List Performance: loop=100000----------------------- add insert remove get set iterator FastArrayList 16 8609 8360 15 47 0 TreeList 110 187 156 47 110 78 ArrayList 15 8313 8344 0 15 0 LinkedList 47 50110 80671 59016 55391 78 CopyOnWriteArrayList 54016 484003 370891 16 105406 0 Vector 15 8266 8328 0 16 0 Stack 31 8281 8266 0 16 0 --------------------Test List sort Performance: loop=100000--------------------- optimize worst random FastArrayList 47 78 110 TreeList 15 47 110 ArrayList 32 47 78 LinkedList 15 109 125 Vector 0 63 94 Stack 16 46 78 -------------------Test List convert Performance: loop=100000------------------- Tree Array LinkedCopyOnWrite Vector FastArrayList 0 0 0 0 0 TreeList 0 0 0 0 0 ArrayList 0 0 0 0 0 LinkedList 0 0 0 0 0 CopyOnWriteArrayList 0 0 0 0 0
結論：
1.隨機插入、隨機刪除操作中，用TreeList
效率最高；
2.在隻需要追加、迭代的環境下，LinkedList
效率最高；
3.平均效率來講，ArrayList
相對平衡，但如果海量隨機操作，還是會造成性能瓶頸；
4.CopyOnWriteArrayList
因為線程安全的原因，致使性能降低很多，所以慎用；
5.Vector
沒有傳說中那麼低的效率；
6.讓Stack
來做List
的事可以，不過語義上Stack
不應該做過多的List
的事情；
7.在排序中，ArrayList
具有最好的性能，TreeList
平均性能也不錯，LinkedList
的排序效率受元素初始狀態的影響很大。
8.各種List
間轉換幾乎沒有時間損耗。（來源：https://blog.csdn.net/inkfish）
最後更新：2017-04-02 04:01:45