您现在的位置:主页 > java下午茶 > >

Java中List效率的比较



时间: 2014-08-25 15:15     来源 : CSDN      点击:

关键词: java    List    Collections   


  Java Collections Framework(JCF) 是Java SE中一个基本的类集,几乎所有的项目都会用到,其中的List 则是JCF中最最常用的一个接口。围绕List 接口,有很多实现,诸如常用的ArrayList 、LinkedList 、Vector 、Stack,还有Java5之后引入的CopyOnWriteArrayList ,也有不少List 的开源实现,如Apache commons-collections中的各类List 。 IT学习者(www.itxxz.com)

  这么多的List 实现,如何选择?他们的运行效率具体怎样?本篇文章将用具体的代码来检测其中最最常用的一些List 实现。

官网:http://www.itxxz.com

测试环境: 
  处理器: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

copyright www.itxxz.com

主要测试对象: 
  java.util.ArrayList;
  java.util.LinkedList;
  java.util.Stack;
  java.util.Vector;
  java.util.concurrent.CopyOnWriteArrayList;
  org.apache.commons.collections.FastArrayList;
  org.apache.commons.collections.list.TreeList;
本文来自www.itxxz.com

测试用例: 
  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 

官网:http://www.itxxz.com


   3.5转化为Vector
本文来自www.itxxz.com

[java]
 
  1. package test;  
  2. import static java.lang.System.out;  
  3. import java.util.ArrayList;  
  4. import java.util.Collections;  
  5. import java.util.Iterator;  
  6. import java.util.LinkedList;  
  7. import java.util.List;  
  8. import java.util.Stack;  
  9. import java.util.Vector;  
  10. import java.util.concurrent.CopyOnWriteArrayList;  
  11. import org.apache.commons.collections.FastArrayList;  
  12. import org.apache.commons.collections.list.TreeList;  
  13. import org.apache.commons.lang.StringUtils;  
  14. import org.apache.commons.lang.time.StopWatch;  
  15. @SuppressWarnings("unchecked")  
  16. public class ListPerformance {  
  17.     public static void main(String[] args) {  
  18.         ListPerformance test = new ListPerformance(10 * 10000);  
  19.         out.print(StringUtils.center("Test List Performance: loop=" + test.loop, 80'-'));  
  20.         out.printf("/n%20s%10s%10s%10s%10s%10s%10s""""add""insert""remove""get""set",  
  21.                 "iterator");  
  22.         test.benchmark(new FastArrayList());  
  23.         test.benchmark(new TreeList());  
  24.         test.benchmark(new ArrayList());  
  25.         test.benchmark(new LinkedList());  
  26.         test.benchmark(new CopyOnWriteArrayList());  
  27.         test.benchmark(new Vector());  
  28.         test.benchmark(new Stack());  
  29.         //2.测试排序  
  30.         out.print("/n/n");  
  31.         out.print(StringUtils.center("Test List sort Performance: loop=" + test.loop, 80'-'));  
  32.         out.printf("/n%20s%10s%10s%10s""""optimize""worst""random");  
  33.         test.benchmarkSort(new FastArrayList());  
  34.         test.benchmarkSort(new TreeList());  
  35.         test.benchmarkSort(new ArrayList());  
  36.         test.benchmarkSort(new LinkedList());  
  37.         //test.benchmarkSort(new CopyOnWriteArrayList());//UnsupportedOperationException  
  38.         test.benchmarkSort(new Vector());  
  39.         test.benchmarkSort(new Stack());  
  40.         //3.测试各种数据结构间转化  
  41.         out.print("/n/n");  
  42.         out.print(StringUtils.center("Test List convert Performance: loop=" + test.loop, 80'-'));  
  43.         out.printf("/n%20s%10s%10s%10s%10s%10s""""Tree""Array""Linked""CopyOnWrite",  
  44.                 "Vector");  
  45.         test.benchmarkConvert(new FastArrayList());  
  46.         test.benchmarkConvert(new TreeList());  
  47.         test.benchmarkConvert(new ArrayList());  
  48.         test.benchmarkConvert(new LinkedList());  
  49.         test.benchmarkConvert(new CopyOnWriteArrayList());  
  50.     }  
  51.     /**测试循环次数*/  
  52.     private int loop = 10000;  
  53.     public ListPerformance(int loop) {  
  54.         this.loop = loop;  
  55.     }  
  56.     public void benchmark(List list) {  
  57.         out.printf("/n%20s", list.getClass().getSimpleName());  
  58.         int j;  
  59.         StopWatch watch = null;  
  60.         //1.测试顺序性能(Add)  
  61.         (watch = new StopWatch()).start();  
  62.         for (int i = 0; i < loop; i++) {  
  63.             list.add(new Integer(i));  
  64.         }  
  65.         watch.stop();  
  66.         out.printf("%10d", watch.getTime());  
  67.         //2.测试随机插入性能(Random insert)  
  68.         (watch = new StopWatch()).start();  
  69.         for (int i = 0; i < loop; i++) {  
  70.             j = (int) (Math.random() * loop);  
  71.             list.add(j, new Integer(-j));  
  72.         }  
  73.         watch.stop();  
  74.         out.printf("%10d", watch.getTime());  
  75.         //3.测试随机索引删除(Random remove)  
  76.         (watch = new StopWatch()).start();  
  77.         for (int i = 0; i < loop; i++) {  
  78.             j = (int) (Math.random() * loop);  
  79.             list.remove(j);  
  80.         }  
  81.         watch.stop();  
  82.         out.printf("%10d", watch.getTime());  
  83.         //4.测试随机取数性能(Random get)  
  84.         (watch = new StopWatch()).start();  
  85.         for (int i = 0; i < loop; i++) {  
  86.             j = (int) (Math.random() * loop);  
  87.             list.get(j);  
  88.         }  
  89.         watch.stop();  
  90.         out.printf("%10d", watch.getTime());  
  91.         //5.测试随机更新性能(Random set)  
  92.         (watch = new StopWatch()).start();  
  93.         for (int i = 0; i < loop; i++) {  
  94.             j = (int) (Math.random() * loop);  
  95.             list.set(j, j);  
  96.         }  
  97.         watch.stop();  
  98.         out.printf("%10d", watch.getTime());  
  99.         //6.测试迭代性能(Iterator)  
  100.         (watch = new StopWatch()).start();  
  101.         Iterator<Object> iter = list.iterator();  
  102.         while (iter.hasNext()) {  
  103.             iter.next();  
  104.         }  
  105.         watch.stop();  
  106.         out.printf("%10d", watch.getTime());  
  107.     }  
  108.     public void benchmarkConvert(List list) {  
  109.         out.printf("/n%20s", list.getClass().getSimpleName());  
  110.         StopWatch watch = null;  
  111.         //1.转TreeList  
  112.         (watch = new StopWatch()).start();  
  113.         new TreeList(list);  
  114.         watch.stop();  
  115.         out.printf("%10d", watch.getTime());  
  116.         //2.转ArrayList  
  117.         (watch = new StopWatch()).start();  
  118.         new ArrayList(list);  
  119.         watch.stop();  
  120.         out.printf("%10d", watch.getTime());  
  121.         //3.转LinkedList  
  122.         (watch = new StopWatch()).start();  
  123.         new LinkedList(list);  
  124.         watch.stop();  
  125.         out.printf("%10d", watch.getTime());  
  126.         //4.转CopyOnWriteArrayList  
  127.         (watch = new StopWatch()).start();  
  128.         new CopyOnWriteArrayList(list);  
  129.         watch.stop();  
  130.         out.printf("%10d", watch.getTime());  
  131.         //5.转Vector  
  132.         (watch = new StopWatch()).start();  
  133.         new Vector(list);  
  134.         watch.stop();  
  135.         out.printf("%10d", watch.getTime());  
  136.     }  
  137.     public void benchmarkSort(List list) {  
  138.         out.printf("/n%20s", list.getClass().getSimpleName());  
  139.         StopWatch watch = null;  
  140.         //1.顺序List  
  141.         for (int i = 0; i < loop; i++) {  
  142.             list.add(new Integer(i));  
  143.         }  
  144.         (watch = new StopWatch()).start();  
  145.         Collections.sort(list);  
  146.         watch.stop();  
  147.         out.printf("%10d", watch.getTime());  
  148.         //2.逆序List  
  149.         for (int i = loop - 1; i > 0; i--) {  
  150.             list.add(new Integer(i));  
  151.         }  
  152.         (watch = new StopWatch()).start();  
  153.         Collections.sort(list);  
  154.         watch.stop();  
  155.         out.printf("%10d", watch.getTime());  
  156.         //3.随机顺序List  
  157.         for (int i = 0, j = 0; i < loop; i++) {  
  158.             j = (int) (Math.random() * loop);  
  159.             list.add(new Integer(j));  
  160.         }  
  161.         (watch = new StopWatch()).start();  
  162.         Collections.sort(list);  
  163.         watch.stop();  
  164.         out.printf("%10d", watch.getTime());  
  165.     }  
  166. }  
 
 

测试结果:

内容来自www.itxxz.com

  本文来自www.itxxz.com

[xhtml]
 
  1. -----------------------Test List Performance: loop=100000-----------------------  
  2.                            add    insert    remove       get       set  iterator  
  3.        FastArrayList        16      8609      8360        15        47         0  
  4.             TreeList       110       187       156        47       110        78  
  5.            ArrayList        15      8313      8344         0        15         0  
  6.           LinkedList        47     50110     80671     59016     55391        78  
  7. CopyOnWriteArrayList     54016    484003    370891        16    105406         0  
  8.               Vector        15      8266      8328         0        16         0  
  9.                Stack        31      8281      8266         0        16         0  
  10. --------------------Test List sort Performance: loop=100000---------------------  
  11.                       optimize     worst    random  
  12.        FastArrayList        47        78       110  
  13.             TreeList        15        47       110  
  14.            ArrayList        32        47        78  
  15.           LinkedList        15       109       125  
  16.               Vector         0        63        94  
  17.                Stack        16        46        78  
  18. -------------------Test List convert Performance: loop=100000-------------------  
  19.                           Tree     Array    LinkedCopyOnWrite    Vector  
  20.        FastArrayList         0         0         0         0         0  
  21.             TreeList         0         0         0         0         0  
  22.            ArrayList         0         0         0         0         0  
  23.           LinkedList         0         0         0         0         0  
  24. CopyOnWriteArrayList         0         0         0         0         0  

  本文来自www.itxxz.com

结论: 
  1.随机插入、随机删除操作中,用TreeList 效率最高;
  2.在只需要追加、迭代的环境下,LinkedList 效率最高;
  3.平均效率来讲,ArrayList 相对平衡,但如果海量随机操作,还是会造成性能瓶颈;
  4.CopyOnWriteArrayList 因为线程安全的原因,致使性能降低很多,所以慎用;
  5.Vector 没有传说中那么低的效率;
  6.让Stack 来做List 的事可以,不过语义上Stack 不应该做过多的List 的事情;
  7.在排序中,ArrayList 具有最好的性能,TreeList 平均性能也不错,LinkedList 的排序效率受元素初始状态的影响很大。

IT学习者(www.itxxz.com)


  8.各种List 间转换几乎没有时间损耗。

(via:inkfish本文来自www.itxxz.com






文章除注明转载外,均为IT学习者原创或编译
欢迎任何形式的转载,但务必请以超链接形式注明出处
本文出自:CSDN
链接地址:http://www.itxxz.com



微信公众号:喝咖啡的螃蟹

喝咖啡的螃蟹
评论列表(网友评论仅供网友表达个人看法,并不表明本站同意其观点或证实其描述)
-->