Java中List效率的比较 - ㄓㄤㄑㄧㄤ

link之家

链接快照平台

输入网页链接，自动生成快照
标签化管理网页链接

相关文章推荐

刚分手的肉夹馍 · 惊魂！汽车行进中，电池缘何突然掉落？_手机新浪网· 1 年前 ·

风流的乌冬面 · onlyfans网页 - 百度· 1 年前 ·

睿智的酸菜鱼 · 全能高手 ...· 1 年前 ·

豪情万千的消防车 · 某站国漫区进入改名热，无限恐怖黎明之剑作品都 ...· 1 年前 ·

另类的牛肉面 · 阿蒙森—斯科特站_百度百科· 1 年前 ·

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

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

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

主要测试对象：
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顺序迭代
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

测试代码：

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());
测试结果：
-----------------------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---------------------
结论： 
　　1.随机插入、随机删除操作中，用TreeList 效率最高；
　　2.在只需要追加、迭代的环境下，LinkedList 效率最高；
　　3.平均效率来讲，ArrayList 相对平衡，但如果海量随机操作，还是会造成性能瓶颈；
　　4.CopyOnWriteArrayList 因为线程安全的原因，致使性能降低很多，所以慎用；
　　5.Vector 没有传说中那么低的效率；
　　6.让Stack 来做List 的事可以，不过语义上Stack 不应该做过多的List 的事情；
　　7.在排序中，ArrayList 具有最好的性能，TreeList 平均性能也不错，LinkedList 的排序效率受元素初始状态的影响很大。
　　8.各种List 间转换几乎没有时间损耗。
                      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
原文：http://blog.csdn.net/inkfish/article/details/5185320