java - ArrayList 与 LinkedList

Question

我关注的是 previous post上面写着:

For LinkedList

• get is O(n)
• add is O(1)
• remove is O(n)
• Iterator.remove is O(1)

For ArrayList

• get is O(1)
• add is O(1) amortized, but O(n) worst-case since the array must be resized and copied
• remove is O(n)

所以通过查看这个，我得出结论，如果我只需要在我的集合中按顺序插入 5000000 个元素，LinkedList 将超越 ArrayList。

如果我只是通过迭代从集合中获取元素，即不抓取中间的元素，仍然 LinkedList 将超越 ArrayList。

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

ArrayList 在这两种情况下都优于 Linkedlist。从集合中添加和获取它们比 LinkedList 花费的时间更少。有什么我做错了吗，或者关于 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);

Answer 1

请记住，大 O 复杂度描述的是渐近行为，可能无法反射(reflect)实际的实现速度。它描述了每个操作的成本如何随着列表的大小而不是每个操作的速度而增长。例如，以下 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 循环。确保循环确实做了一些事情来确保调用正确的代码。