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更好。

现在，要验证我的上述两个语句，我编写了以下示例程序…但令我惊讶的是，我的上述语句被证明是错误的。

ArrayList``Linkedlist在这两种情况下都超过了。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循环。确保循环实际上执行了某些操作，以确保调用正确的代码。