`

Java中List效率的比较

 
阅读更多
Java Collections Framework(JCF) 是Java SE中一个基本的类集，几乎所有的项目都会用到，其中的List 则是JCF中最最常用的一个接口。围绕List 接口，有很多实现，诸如常用的ArrayList 、LinkedList 、Vector 、Stack ，还有Java5之后引入的CopyOnWriteArrayList ，也有不少List 的开源实现，如Apache commons-collections中的各类List
　　这么多的List 实现，如何选择？他们的运行效率具体怎样？本篇文章将用具体的代码来检测其中最最常用的一些List 实现

主要测试对象：
　　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;
测试用例：
　　1.测试List
　　　1.1顺序添加
　　　1.2随机插入
　　　1.3随机删除
　　　1.4随机访问
　　　1.5随机更新
　　　1.5顺序迭代
      1.6for顺序迭代

　　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
测试代码： 
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 ssssssss", "", "add", "insert", "remove", "get", "set",  
                "iterator","for");  
        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 ssss", "", "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 ssssss", "", "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 s", 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("d", 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("d", 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("d", 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("d", 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("d", watch.getTime());  
        //6.测试迭代性能(Iterator)  
        (watch = new StopWatch()).start();  
        Iterator<Object> iter = list.iterator();  
        while (iter.hasNext()) {  
            iter.next();  
        }  
        watch.stop();  
        out.printf("d", watch.getTime());
      //7.测试迭代性能(Iterator)  
        (watch = new StopWatch()).start();  
     //   Iterator<Object> iter = list.iterator();  
        for (Object obj : list) {  
          
        }  
        watch.stop();  
        out.printf("d", watch.getTime());
    }  
    public void benchmarkConvert(List list) {  
        out.printf("\n s", list.getClass().getSimpleName());  
        StopWatch watch = null;  
        //1.转TreeList  
        (watch = new StopWatch()).start();  
        new TreeList(list);  
        watch.stop();  
        out.printf("d", watch.getTime());  
        //2.转ArrayList  
        (watch = new StopWatch()).start();  
        new ArrayList(list);  
        watch.stop();  
        out.printf("d", watch.getTime());  
        //3.转LinkedList  
        (watch = new StopWatch()).start();  
        new LinkedList(list);  
        watch.stop();  
        out.printf("d", watch.getTime());  
        //4.转CopyOnWriteArrayList  
        (watch = new StopWatch()).start();  
        new CopyOnWriteArrayList(list);  
        watch.stop();  
        out.printf("d", watch.getTime());  
        //5.转Vector  
        (watch = new StopWatch()).start();  
        new Vector(list);  
        watch.stop();  
        out.printf("d", watch.getTime());  
    }  
    public void benchmarkSort(List list) {  
        out.printf("\n s", 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("d", 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("d", 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("d", watch.getTime());  
    }  
}




测试结果：
-----------------------Test List Performance: loop=100000-----------------------
                           add    insert    remove       get       set  iterator       for
       FastArrayList        31     16344     16312        47        62         0         0
            TreeList       156       391       281       109       110        15         0
           ArrayList        47     16406     16500        16        47        16         0
          LinkedList        15    149719    264203    176125    179406         0        31
CopyOnWriteArrayList     27422    141797    160906        31     65375         0         0
              Vector        16     26391     24437        31        47        16         0
               Stack        31     25094     22703        31        16        16         0
--------------------Test List sort Performance: loop=100000---------------------
                      optimize     worst    random
       FastArrayList        31        78       188
            TreeList        32        94       343
           ArrayList        16        94       172
          LinkedList        16       266       219
              Vector        15        78       219
               Stack        15        94       156
-------------------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 间转换几乎没有时间损耗。

注：增强性for循环其实是对iterator循环的一种简单写法，在编译时增强性for循环会被编译为iterator的for循环写法。在测试结果中两者变现出来的性能有一点相差（不正确，有时变现的快，有时变现的慢一点，可能与其他因素有关系），从理论上说，应该基本一样。


http://blog.sina.com.cn
分享到：
| java判断字符串为空的5种方法及其效率
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    List效率的比较

    随机插入、随机删除操作中，用TreeList 效率最高； 　2.在只需要追加、迭代的环境下，LinkedList 效率最高； 　3.平均效率来讲，ArrayList 相对平衡，但如果海量随机操作，还是会造成性能瓶颈； 　4....

    java开发List提高效率

    java开发List提高效率

    JAVA容器效率深度分析List

    NULL 博文链接：https://wwwiteye.iteye.com/blog/1992312

    List.removeAll() 方法的性能效率

    List.removeAll() 方法的性能效率

    java集合类的效率测试

    我写的关于set集合和list集合相关性能测试，linkedList ArrayList HashSet 等类的增删改查性能测试

    List和Treemap排序实例及效率对比

    本资源提供了List对对象中的属性和TreeMap, String&gt;对键值排序，并针对100w条数据排序，对比List和TreeMap, String&gt;排序的效率。个人认为排序效率对比可以相信，但也可能存在不科学之处，还请高手给与指点，多多包涵...

    Java集合框架List接口.pdf

    Java集合框架中的List接口是一种有序的集合，它可以存储重复的元素。它是Collection接口的子接口，提供了一系列可以对列表进行操作的方法，如添加、插入、删除、获取元素等。List接口还可以通过索引访问元素，类似于...

    比较Java数组和各种List的性能小结

    主要是分别对Java数组、ArrayList、LinkedList和Vector进行随机访问和迭代等操作，并比较这种集合的性能。有需要的可以参考借鉴。

    Java实体类字段生成工具类-将数据库表列字段转为Java实体类驼峰字段

    1、在Java开发中，常常需要将数据库表列字段换成Java实体类字段。但是手动实现这个转换过程比较慢，且容易出错，影响开发效率。为了解决这个问题，开发了这个Java实体类字段生成工具类。 2、该工具类可以将数据库表...

    Java list三种遍历方法性能比较

    从c/c++语言转向java开发，学习java语言list遍历的三种方法，顺便测试各种遍历方法的性能，测试方法为在ArrayList中插入1千万条记录，然后遍历ArrayList，发现了一个奇怪的现象，测试代码例如以下： package ...

    list去掉重复对象

    一个list里面有多个对象，对象有几个字段，要求在对象里面不要有重复的数据的实现。

    Java8 Stream对两个 List 遍历匹配数据的优化处理操作

    主要介绍了Java8 Stream对两个 List 遍历匹配数据的优化处理操作，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧

    JAVA入门1.2.3：一个老鸟的JAVA学习心得 PART1（共3个）

    Java编程老鸟潜心写作，奉献高效率的Java学习心得 完全站在没有编程经验读者的角度，手把手教会读者学习Java 配16小时多媒体教学视频，高效、直观 一一击破Java入门可能会遇到的难点和疑惑 抽丝剥茧，层层推进，让...

    Java入门1·2·3：一个老鸟的Java学习心得.PART3（共3个）

    Java编程老鸟潜心写作，奉献高效率的Java学习心得 完全站在没有编程经验读者的角度，手把手教会读者学习Java 配16小时多媒体教学视频，高效、直观 一一击破Java入门可能会遇到的难点和疑惑 抽丝剥茧，层层推进，让...

    java实现csv导出千万级数据实例

    轻松解决普通poi形式导出Excel的中出现的栈溢出问题，此资源可实现千万级数据分批导出csv文件，测试实现16500000条数据大概80秒左右；具体表里内容。

    JAVA面试题最全集

    5.Java中的分页、效率考虑。 6.简单介绍您所了解的structs。 1.xml在项目中的作用 2.s-EJB 与 e-EJB的区别 3.会话面的作用 4.cmp与bmp的优缺点 5.j2me程序的必需的几个部分 6.c/s与b/s的区别 7.构建一...

    java summary(java笔记)

    学习java的一些笔记和个人总结 9、Collection 和 Collections的区别。 　Collection是集合类的上级接口，继承与他的接口主要有Set 和List.。Collections是针对集合类的一个帮助类，他提供一系列静态方法实现对各种...

    java后端宝典进阶版.zip

    Java集合框架：介绍Java中常用的集合类，如List、Set、Map等，以及它们的特点、用法和性能分析，帮助读者选择合适的集合类来解决实际问题。 Java并发编程：深入讲解Java中的线程、锁、并发容器等并发编程相关的知识...

    java8源码-csn-list:ArrayList、LinkedList、Vector、Stack源码分析

    与Java中的数组相比，它的容量能动态增长。不是线程安全的。ArrayList包含了两个重要的对象：elementData(Object[]类型的数组) 和 size 遍历ArrayList时，使用随机访问(即，通过索引序号访问)效率最高 转数组：...

    java 面试题 总结

    与cgi的区别在于servlet处于服务器进程中，它通过多线程方式运行其service方法，一个实例可以服务于多个请求，并且其实例一般不会销毁，而CGI对每个请求都产生新的进程，服务完成后就销毁，所以效率上低于servlet。...

Magicbox
Global site tag (gtag.js) - Google Analytics