ArrayList 与 LinkedList

Question

我正在关注 之前的一篇帖子，上面写着：

对于链表

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

对于数组列表

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

因此，通过查看这个，我得出结论，如果我必须在我的集合中顺序插入 5000000 个元素， LinkedList 将 ArrayList 。

如果我只能通过迭代从集合中获取元素，即不在中间获取元素，仍然 LinkedList 将 ArrayList 。

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

ArrayList Linkedlist 在这两种情况下都优于 —。它比 LinkedList 花费更少的时间来添加以及从 Collection 中获取它们。我做错了什么，或者关于 LinkedList 和 ArrayList 的初始陈述不适用于大小为 5000000 的集合？

我提到大小，因为如果我将元素数量减少到 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) {
    // Do nothing
}
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) {
    // Do nothing
}
System.out.println(System.nanoTime() - nano2);

原文由 Vicky 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

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

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

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

进行此类分析时，您还需要非常小心。我建议您更改分析代码以执行预热阶段（以便 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 循环。确保循环确实执行某些操作以确保调用正确的代码。

原文由 Cameron Skinner 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

这是一个糟糕的基准 IMO。

• 需要在循环中重复多次来预热jvm
• 需要在你的迭代循环中做一些事情或者它可以被优化数组
• ArrayList 调整大小，这是昂贵的。如果你构建了 ArrayList 作为 new ArrayList(500000) 你会一口气构建，然后所有分配都会非常便宜（一个预分配支持数组）
• 您没有指定您的内存 JVM - 它应该与 -xMs == -Xmx （所有预分配的东西）一起运行并且足够高以至于不会触发任何 GC
• 这个基准测试没有涵盖 LinkedList 最令人不快的方面——随机访问。 （迭代器不一定是同一件事）。如果你将大型集合大小的 10% 作为随机选择 list.get 你会发现链表对于抓取除第一个或最后一个元素以外的任何东西都很糟糕。

对于数组列表：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 次访问（代码中有一个优化，它从头部或尾部开始，具体取决于哪个访问次数较少。）

原文由 MJB 发布，翻译遵循 CC BY-SA 3.0 许可协议