Java中ArrayList和LinkedList之间的区别-性能的原因 [英] Difference between ArrayList and LinkedList in Java - the whys for performance

问题描述

我认为我从理论上很好地理解了ArrayList和LinkedList之间的区别.但是，这是我第一次进行一些测试，测试结果出来了，与我的期望大不相同.

I thought I understood the difference between ArrayList and LinkedList theoretically pretty well. However, its the first time, I put it to a little test, and the tests came out, well different to my expectations.

期望:

1. 在列表中插入时，Arraylist的速度将比LinkedList慢.开始，因为它必须移动"元素，对于链表，其只需更新2个参考.

1. Arraylist will be slower than LinkedList when inserting at the beginning, since it has to "shift" the elements, for linkedlist, its just updating 2 references.

现实:在大多数迭代中，结果都是相同的.对于一些选择迭代，它比较慢.

Reality : came out to be same on most iterations. For a select few iterations, it was slower.

在开始删除时，Arraylist的速度将比LinkedList慢，因为它必须移动"元素，对于Linkedlist来说，它只是使一个元素无效.

Arraylist will be slower than LinkedList when deleting at the beginning, since it has to "shift" the elements, for Linkedlist, its just nullifying one element.

现实:从乞讨删除时的性能相同.

Reality : Performance was same when deleting from beg.

测试用例:1,000,000个元素

Test Case : 1,000,000 elements

public static void main(String[] args) {
    int n = 1000000;

    List arrayList = new ArrayList(n+10);
    long milis = System.currentTimeMillis();
    for(int i= 0 ;i<n;i++){
        arrayList.add(i);
    }
    System.out.println("insert arraylist takes "+(System.currentTimeMillis()-milis)+" ms");

    List linkedList = new LinkedList();
    milis = System.currentTimeMillis();
    for(int i= 0 ;i<n;i++){
        linkedList.add(i);
    }
    System.out.println("insert linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");

    //System.out.println("Adding at end");
    milis = System.currentTimeMillis();
    arrayList.add(n-5,n+1);
    System.out.println("APPEND arraylist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    linkedList.add(n-5,n+1);
    System.out.println("APPEND linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");

    //add at front
    milis = System.currentTimeMillis();
    arrayList.add(0,0);
    System.out.println("INSERT BEG arraylist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    linkedList.add(0,0);
    System.out.println("INSERT BEG linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");

    //add at middle
    milis = System.currentTimeMillis();
    arrayList.add(n/2,n/2);
    System.out.println("INSERT MIDDLE arraylist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    linkedList.add(n/2,n/2);
    System.out.println("INSERT MIDDLE linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");

    //get from front, mid, end
    milis = System.currentTimeMillis();
    arrayList.get(0);
    System.out.println("get front arraylist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    linkedList.get(0);
    System.out.println("get front linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    arrayList.get(n/2);
    System.out.println("get MIDDLE arraylist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    linkedList.get(n/2);
    System.out.println("get MIDDLE linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    arrayList.get(n-4);
    System.out.println("get last arraylist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    linkedList.get(n-4);
    System.out.println("get last linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");

    //delete from front, mid, end.
    milis = System.currentTimeMillis();
    arrayList.remove(0);
    System.out.println("del front arraylist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    linkedList.remove(0);
    System.out.println("del front linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    arrayList.remove(n/2);
    System.out.println("del mid arraylist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    linkedList.remove(n/2);
    System.out.println("del mid linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    arrayList.remove(n-4);
    System.out.println("del end arraylist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    linkedList.remove(n-4);
    System.out.println("del end linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");

}

输出日志

insert arraylist takes 141 ms
insert linkedlist takes 312 ms
APPEND arraylist takes 0 ms
APPEND linkedlist takes 0 ms
INSERT BEG arraylist takes 0 ms
INSERT BEG linkedlist takes 0 ms
INSERT MIDDLE arraylist takes 0 ms
INSERT MIDDLE linkedlist takes 0 ms
get front arraylist takes 0 ms
get front linkedlist takes 0 ms
get MIDDLE arraylist takes 0 ms
get MIDDLE linkedlist takes 16 ms
get last arraylist takes 0 ms
get last linkedlist takes 0 ms
del front arraylist takes 0 ms
del front linkedlist takes 0 ms
del mid arraylist takes 0 ms
del mid linkedlist takes 15 ms
del end arraylist takes 0 ms
del end linkedlist takes 0 ms

那是什么原因?使用了JDK 1.6.

So what's the reason? JDK 1.6 used.

使用System.nanotime()之后，它确实给了我预期的答案.同意，仅一次试验，应平均.

EDIT : After using System.nanotime(), it did give me answers as I expected. Agreed, its only a single trial, and should be averaged.

insert arraylist takes 137076082 ns
insert linkdlist takes 318985917 ns
APPEND arraylist takes 69751 ns
APPEND linkdlist takes 98126 ns
**INSERT BEG arraylist takes 2027764 ns
INSERT BEG linkdlist takes 53522 ns**
INSERT MIDDLE arraylist takes 1008253 ns
INSERT MIDDLE linkdlist takes 10395846 ns
get front arraylist takes 42364 ns
get front linkdlist takes 77473 ns
get MIDDLE arraylist takes 39499 ns
get MIDDLE linkdlist takes 9645996 ns
get last arraylist takes 46165 ns
get last linkdlist takes 43446 ns
**del front arraylist takes 1720329 ns
del front linkdlist takes 108063 ns**
del mid arraylist takes 1157398 ns
del mid linkdlist takes 11845077 ns
del end arraylist takes 54149 ns
del end linkdlist takes 49744 ns

推荐答案

前两个(怪异)测试编号的解释是:

The explanation for your first two (weird) test numbers is:

插入ArrayList通常较慢，因为一旦到达边界，它就必须增长.它必须创建一个更大的新数组，并从原始数组中复制数据.

Inserting into ArrayList is generally slower because it has to grow once you hit its boundaries. It will have to create a new bigger array, and copy data from the original one.

但是当您创建一个已经足够大 的ArrayList来容纳所有插入内容时(这就是您的情况，因为您正在执行 new ArrayList(n + 10))-很显然，它不会涉及任何数组复制操作.添加它比使用LinkedList甚至更快，因为LinkedList必须处理其链接"(指针)，而巨大的ArrayList只是在给定(最后)索引处设置值.

But when you create an ArrayList that is already huge enough to fit all your inserts (which is your case since you're doing new ArrayList(n+10)) - it will obviously not involve any array copying operations. Adding to it will be even faster than with LinkedList because LinkedList will have to deal with its "links" (pointers), while huge ArrayList just sets value at given (last) index.

您的测试也不好，因为每次迭代都涉及自动装箱(从int到Integer的转换)-这不仅会花费额外的时间，而且由于

Also your tests are not good because each iteration involves autoboxing (conversion from int to Integer) - it will both take additional time to do that and will also screw up the results because of the Integers cache that will get filled on the first pass.

这篇关于Java中ArrayList和LinkedList之间的区别-性能的原因的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！