数组、ArrayList、LinkedList查询及遍历性能分析

数组、ArrayList、LinkedList查询及遍历性能分析 收藏

最近研究spring框架时，发现它在存储以查询和遍历居多的数据时采用的数组，而不是现在很多书中推荐的List。并且之前也发现 tomcat在实现自己的service和connector时，也是多采用数组的方式。虽然之前也大概了解到list，特别是linkedList和数 组在数据查询上确实有差距，但是没有深入的分析过。所以这里就写了个程序测试一下数组、ArrayList、LinkedList在遍历和查询方面的性 能。

首先代码：

 

package test;

import java.util.ArrayList;
import java.util.LinkedList;

import org.junit.Before;
import org.junit.Test;

/**
 * 数组及List查询和遍历性能比对
 * @author gaoyusi
 * @see http://blog.csdn.net/gaoyusi4964238
 */
public class TestArrayAndList {

    /*
     * count:10,100,1000,10000,100000
     * idx:  6,60,600,6000,60000
     */
    private static final int COUNT=10000;

    private static final int IDX=6;

    private String[] array;

    private ArrayList<String> arrayList;

    private LinkedList<String> linkList;

    @Before
    public void init(){
        array=new String[COUNT];
        arrayList=new ArrayList<String>(COUNT);
        linkList=new LinkedList<String>();
        for(int i=0;i<COUNT;i++){
            array[i]="test";
            arrayList.add("test");
            linkList.add("test");
        }
    }

    @Test
    public void  testTraverse(){
        System.out.println("Traverse Time:");
        long startTime=System.nanoTime();
        array();
        System.out.println(">>>array:"+(System.nanoTime()-startTime));

        startTime=System.nanoTime();
        arrayList();
        System.out.println(">>>aList:"+(System.nanoTime()-startTime));

        startTime=System.nanoTime();
        linkList();
        System.out.println(">>>lList:"+(System.nanoTime()-startTime));
    }

    @Test
    public void  testQuery(){
        System.out.println("Query Time:");
        long startTime=System.nanoTime();
        String test=array[IDX];
        System.out.println(">>>array:"+(System.nanoTime()-startTime));

        startTime=System.nanoTime();
        arrayList.get(IDX);
        System.out.println(">>>aList:"+(System.nanoTime()-startTime));

        startTime=System.nanoTime();
        linkList.get(IDX);
        System.out.println(">>>lList:"+(System.nanoTime()-startTime));
    }

    public void array(){
        int i=0;
        for(String a:array){
            i++;
        }
    }

    public void arrayList(){
        int i=0;
        for(String a:arrayList){
            i++;
        }
    }

    public void linkList(){
        int i=0;
        for(String a:linkList){
            i++;
        }
    }
}

 

测试结果如下：

count:10,idx:  6

count:100,idx:  60

count:1000,idx:  600

count:10000,idx:  6000

count:100000,idx:  60000

从以上测试结果可得到以下结论：

1.array在容量在比较小时，遍历的性能优势不够明显，但是随着容量的不断增大，其遍历性能优势会不断显现。

2.array的查询性能要优于list,而且随着array容量增加，这种优势也更加突出。

3.linkedList在遍历上性能不够稳定。

4.在list容量较大情况下，ArrayList查询数据要远优于LinkedList

分析：

对于结论1和2，在容量比较小的情况下，有点困惑，估计是array和list对于资源消耗比较小。在容量较大情况下，list性能较差原因主要是 需要转型，对于ArrayList,其数据其实是存放于一个Obejct[]中的，那么他在查询和遍历返回时需要强制转型，这样隐形增加其开销，这个可以 从其源代码中看出:

 

public E get(int index) {
RangeCheck(index);

return (E) elementData[index];
   }

 

而对于LinkedList，虽然不需要强制转型，但是根据java中泛型的工作原理，jvm还是对相应的数据进行了隐性的转型。

虽然这中转型开销不是特别庞大，但是在大数据量的遍历过程中，其累加起来的消耗还是相当大的。

对于结论3和4，主要原因是因为LinkedList是利用双向循环链表实现的，参见一下linkedList的构造函数：

 

public LinkedList() {
       header.next = header.previous = header;
   }

 

所以其在查询过程中，不能像array或arrayList那样直接定位到对应的数据节点，而是必须遍历到具体的位置来实现，对于大容量数据来说，这个过程会相当消耗时间（不过这也造就了其在频繁修改和增加数据时的高性能）。

发表于 @ 2010年05月23日　12:00:00 | 评论( 0 ) | 举报| 收藏

旧一篇:求数组中相邻元素最大和问题的两种快速算法 | 新一篇:在一个无序整型数组中找出第k小数字的时间复杂度为O(nlog^n)的算法