ArrayList与LinkedList

Question

我之前关于此的帖子说:

对于LinkedList

• 得到的是O(n)
• 加是O(1)
• 删除是O(n)
• Iterator.remove是O(1)

对于ArrayList

• 得到的是O(1)
• add是O(1)摊销,但O(n)最坏情况,因为必须调整和复制数组
• 删除是O(n)

因此,通过观察这一点,我得出结论,如果我只是在我的集合中为5000000个元素执行顺序插入,那么LinkedList将会超出ArrayList.

如果我只是通过迭代来获取集合中的元素,即不在中间抓取元素,仍然LinkedList会超出`ArrayList.

现在要验证我的上述两个陈述,我在下面写了示例程序...但我很惊讶我的上述陈述被证明是错误的.

ArrayListLinkedlist在两个案件中都超过了.花费的时间少于LinkedList添加以及从Collection中获取它们所花费的时间.有什么我做错了,或有关初步陈述LinkedList和ArrayList尺寸为500万的收藏品不成立？

我提到了尺寸,因为如果我将元素数量减少到50000,那么LinkedList表现更好,初始语句也成立.

long nano1 = System.nanoTime();

List<Integer> arr = new ArrayList();
for(int i = 0; i < 5000000; ++i) {
    arr.add(i);
}
System.out.println( (System.nanoTime() - nano1) );

for(int j : arr) {
    ;
}
System.out.println( (System.nanoTime() - nano1) );

long nano2 = System.nanoTime();

List<Integer> arrL = new LinkedList();
for(int i = 0; i < 5000000; ++i) {
    arrL.add(i);
}
System.out.println( (System.nanoTime() - nano2) );

for(int j : arrL) {
    ;
}
System.out.println( (System.nanoTime() - nano2) );

Answer 1

请记住,big-O复杂性描述渐近行为,可能无法反映实际的实现速度.它描述了每个操作的成本如何随列表的大小而增长,而不是每个操作的速度.例如,以下实现add是O(1)但不是很快:

public class MyList extends LinkedList {
    public void add(Object o) {
        Thread.sleep(10000);
        super.add(o);
    }
}

我怀疑在你的情况下ArrayList表现良好,因为它相当积极地增加了它的内部缓冲区大小,因此不会有大量的重新分配.当缓冲区不需要调整大小时,ArrayList将具有更快的adds.

进行此类分析时,您还需要非常小心.我建议您更改分析代码以进行预热阶段(因此JIT有机会在不影响结果的情况下进行一些优化)并在多次运行中平均结果.

private final static int WARMUP = 1000;
private final static int TEST = 1000;
private final static int SIZE = 500000;

public void perfTest() {
    // Warmup
    for (int i = 0; i < WARMUP; ++i) {
        buildArrayList();
    }
    // Test
    long sum = 0;
    for (int i = 0; i < TEST; ++i) {
        sum += buildArrayList();
    }
    System.out.println("Average time to build array list: " + (sum / TEST));
}

public long buildArrayList() {
    long start = System.nanoTime();
    ArrayList a = new ArrayList();
    for (int i = 0; i < SIZE; ++i) {
        a.add(i);
    }
    long end = System.nanoTime();
    return end - start;
}

... same for buildLinkedList

(注意,sum可能会溢出,你可能会更好用System.currentTimeMillis()).

编译器也可能正在优化你的空get循环.确保循环实际上做了一些事情以确保调用正确的代码.

Answer 2

这是一个糟糕的基准IMO.

• 需要循环重复多次来预热jvm
• 需要在迭代循环中做一些事情,或者它可以是优化的数组
• ArrayList调整大小,这是昂贵的.如果你建造了ArrayList为new ArrayList(500000)你构建一个打击,然后所有的分配将是相当便宜的(一个预分配备份阵列)
• 您没有指定内存JVM - 它应该使用-xMs == -Xmx(所有预先分配的)运行并且足够高以至于不会触发GC
• 此基准测试未涵盖LinkedList最令人不愉快的方面 - 随机访问.(迭代器不一定是同一个东西).如果您提供大型集合大小的10%作为随机选择,list.get您会发现链接列表很难抓取除第一个或最后一个元素之外的任何内容.

对于一个arraylist:jdk get是你所期望的:

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

    return elementData[index];
}

(基本上只返回索引数组元素.,

对于链表:

public E get(int index) {
    return entry(index).element;
}

看起来很相似 不完全的.entry是一种方法而不是原始数组,看看它必须做什么:

private Entry<E> entry(int index) {
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("Index: "+index+
                                            ", Size: "+size);
    Entry<E> e = header;
    if (index < (size >> 1)) {
        for (int i = 0; i <= index; i++)
            e = e.next;
    } else {
        for (int i = size; i > index; i--)
            e = e.previous;
    }
    return e;
}

这是正确的,如果你要求说list.get(250000),它必须从头开始并反复迭代下一个元素.250000次访问左右(代码中的优化是从头部或尾部开始,具体取决于哪些访问次数较少.)

Answer 3

ArrayList是比LinkedList更简单的数据结构.ArrayList在连续的内存位置中有一个指针数组.如果数组扩展超出其分配的大小,则只需重新创建它.

LinkedList由一系列节点组成; 每个节点都是分开分配的,并且具有指向其他节点的前后指针.

那么这是什么意思？除非您需要插入中间,拼接,删除中间等,否则ArrayList通常会更快.它需要更少的内存分配,具有更好的引用局部性(这对于处理器缓存很重要)等.

Answer 4

要理解为什么你得到的结果不会与"大O"特征相矛盾.我们需要回到第一原则; 即定义.

设f(x)和g(x)是在实数的某个子集上定义的两个函数.一个写道

f(x) = O(g(x)) as x -> infinity

当且仅当对于足够大的x值,f(x)最多为常数乘以绝对值g(x).也就是说,f(x)= O(g(x))当且仅当存在正实数M和实数x0使得

|f(x)| <= M |g(x)| for all x > x_0.

在许多情况下,当变量x变为无穷大时我们对增长率感兴趣的假设未被陈述,并且更简单地写入f(x)= O(g(x)).

因此,声明add1 is O(1)意味着add1大小为N的列表上的操作的时间成本倾向于恒定的C _add1,因为N倾向于无穷大.

并且声明add2 is O(1) amortized over N operations意味着N个操作序列之一的平均时间成本add2倾向于恒定的C _add2,因为N倾向于无穷大.

什么是不说是那些常数C _add1和C _add2是什么.实际上,在您的基准测试中,LinkedList比ArrayList慢的原因是C _add1大于C _add2.

经验教训是,大O符号并不能预测绝对甚至相对的表现.所有它预测的是性能函数的形状,因为控制变量变得非常大.这很有用,但它并没有告诉你需要知道的一切.