为什么第一次将对象添加到ArrayList或LinkedList需要更多的时间

Question

为什么第一次将对象添加到ArrayList或LinkedList需要更多的时间？

我正在测试ArrayList和LinkedList的性能。结果是我所期望的。ArrayList通常更适合随机访问，每次插入LinkedList都需要类似的时间。但我发现，将对象添加到ArrayList或LinkedList的第一次需要比其他多得多的时间。

我已经在Mac和Linux上测试了代码，情况类似。您可以从这里下载代码和完整的结果。

java PlayArrayList       
0 to 10, elapsedTime: 716362
10 to 20, elapsedTime: 19765
20 to 30, elapsedTime: 10895
$ java PlayLinkedList 
0 to 10, elapsedTime: 704209
10 to 20, elapsedTime: 5867
20 to 30, elapsedTime: 5378

PS：它们是以纳秒为单位测量的。

/* Untilty Class for measuring elapsed time */
public class BenmarkTimer {
    private long startTime;
    private long endTime;
    /* Getter */
    public long getStartTime(){
        return startTime;
    }
    public long getEndTime(){
        return endTime;
    }
    /* Setter */
    private void setStartTime(long t){
        startTime = t;
    }
    private void setEndTime(long t){
        endTime = t;
    }
    /* Method */
    public void start(){
        setStartTime(System.nanoTime());
    } 
    public long end(){
        setEndTime(System.nanoTime());
        return getDuration();
    }
    public void cancel(){
        setStartTime(0);
        setEndTime(0);
    }
    public long getDuration(){
        return getEndTime() - getStartTime();
    }
    /* Unit testing */
    public static void main (String [] args){
        BenmarkTimer timer = new BenmarkTimer();
        timer.start();
        System.out.println("Hello, World for timer");
        timer.end();
        long t = timer.getDuration();
        System.out.println("Start time "+ timer.getStartTime());
        System.out.println("End time "+ timer.getEndTime());
        System.out.println("Elaped time "+ t);
    }
}

import java.util.*;
public class PlayArrayList{
    private int itemCount;
    private BenmarkTimer timer;
    private List<Integer> list; 
    public PlayArrayList(){
        itemCount = 0;
        timer = new BenmarkTimer();
        list = getList();
    }
    public long addTenIntegers(){
        timer.start();
        for (int i=itemCount; i<(itemCount + 10); i++ ) {
            list.add(i);
        }
        long elapsedTime = timer.end();
        itemCount += 10;
        return elapsedTime;
    }
    public long randomRemove(){
        Random r = new Random();
        int s = list.size();
        int i = r.nextInt(s);
        timer.start();
        list.remove(i);
        return timer.end();
    }
    public String toString(){
        return list.toString();
    }
    /* Factory method */
    protected List<Integer> getList(){
        return new ArrayList<Integer>();
    }
    public static void main (String [] args){
        PlayArrayList playAList = new PlayArrayList();
        /* Add 99 integers */
        long elapsedTime;
        for (int i=0; i<10; i++){
            elapsedTime = playAList.addTenIntegers();
            System.out.print(i*10 + " to " + (i*10+10));
            System.out.println(", elapsedTime: "+ elapsedTime);
        }
        System.out.println("Array content");
        System.out.println(playAList.toString());

        /* Remove 99 integer */
        for (int i=0; i<99; i++){
            elapsedTime = playAList.randomRemove();
            System.out.print("Remove a integer");
            System.out.println(", elapsedTime: "+ elapsedTime);
        }
    }
} 
import java.util.*;
public class PlayLinkedList extends PlayArrayList{
    /* Factory method */
    @Override
    protected List<Integer> getList(){
        return new LinkedList<Integer>();
    }
    public static void main (String [] args){
        PlayLinkedList playAList = new PlayLinkedList();
        /* Add 99 integers */
        long elapsedTime;
        for (int i=0; i<10; i++){
            elapsedTime = playAList.addTenIntegers();
            System.out.print(i*10 + " to " + (i*10+10));
            System.out.println(", elapsedTime: "+ elapsedTime);
        }
        System.out.println("Array content");
        System.out.println(playAList.toString());

        /* Remove 99 integer */
        for (int i=0; i<99; i++){
            elapsedTime = playAList.randomRemove();
            System.out.print("Remove a integer");
            System.out.println(", elapsedTime: "+ elapsedTime);
        }
    }
} 

Answer 1

我想这个问题的主要原因是这里的规则4，新类的初始化效果。我首先创建了另一个对象来进行初始化操作。第一次使用的类总是需要更长的初始化时间。之后，操作的持续时间将大大缩短。

   PlayArrayList playAListInit = new PlayArrayList();
   long firstTime = playAListInit.addTenIntegers();
   System.out.println("First time: "+ firstTime);
   PlayArrayList playAList = new PlayArrayList();

然后结果看起来像：

java PlayArrayList
First time: 710000
0 to 10, elapsedTime: 6000
10 to 20, elapsedTime: 12000
20 to 30, elapsedTime: 9000