6

我以为我在理论上非常了解 ArrayList 和 LinkedList 之间的区别。然而，这是第一次，我对它进行了一点测试，测试出来了，与我的预期大相径庭。

期望 ：

  1. Arraylist 在开头插入时会比 LinkedList 慢，因为它必须“移动”元素，对于linkedlist，它只是更新2个引用。

    现实：在大多数迭代中都是相同的。对于选择的几次迭代，它比较慢。

  2. Arraylist 在开始删除时会比 LinkedList 慢，因为它必须“移动”元素，对于 Linkedlist，它只是使一个元素无效。

    现实：从乞求中删除时性能相同。

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

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。

编辑：使用 System.nanotime() 后，它确实给了我预期的答案。同意，这只是一次试验，应该取平均值。

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
4

3 回答 3

6

你的前两个（奇怪的）测试号码的解释是：

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

但是，当您创建一个已经足够大以适合所有插入的 ArrayList 时（这是您的情况，因为您正在这样做new ArrayList(n+10)） - 它显然不会涉及任何数组复制操作。添加到它会比使用 LinkedList 更快，因为 LinkedList 必须处理它的“链接”（指针），而巨大的 ArrayList 只是在给定的（最后一个）索引处设置值。

此外，您的测试也不好，因为每次迭代都涉及自动装箱（从 int 转换为 Integer） - 它既需要额外的时间来做到这一点，也会因为整数缓存在第一次通过时被填充而搞砸结果。

于 2013-03-01T03:53:06.750 回答
2

int n = 1000000;太小。你得到0 ms并不意味着它不需要时间来完成插入或删除。这意味着经过的时间小于 1ms 。尝试增加int n = 1000000;. 那你就可以看出区别了。

编辑：我误读了你的代码。我以为您n在数组列表的前面插入元素。您绝对应该插入多个项目，而不是只插入一个。

另一个编辑：如果您插入n元素，则不需要提高n. 相反，您可能希望减少它，因为在 ArrayList 的前面插入是一个缓慢的操作。

于 2013-03-01T03:43:21.897 回答
0

使用 ArrayList，中间操作的插入操作将是理论上 Big Oh 的两个步骤：

  • O(1) 找到位置并插入新值
  • O(n) 将剩余的值向前移动。

使用LinkedList，如果相关Node还不知道（从头节点循环），也是两步：

  • O(n) 找到该位置的节点
  • O(1) 插入新值

但是，除了预期的算法复杂性之外，还有其他几点可能会对实际运行时产生影响：

  • 特定的语言实现可能会使特定过程的某些部分更快。在这种情况下，ArrayList 使用的 Java 的 arraycopy() 比复制每个值的 for 循环更快。这可能不适用于所有数组（大小、类型）——同样，这将是特定于实现的。

  • Big Oh 会忽略可能对某些数据集产生影响的常量。例如，冒泡排序是 O(n*n)，但可以检测 O(n) 中的预排序数组，并且对于几乎排序的数组非常快。

  • LinkedList 需要向虚拟机请求更多内存（创建 Node 对象）。需要更多内存来请求的进程有时会成为瓶颈的原因。

总结：提防理论假设并始终进行测量，最好使用真实世界的数据和操作:)。

于 2017-05-29T23:27:59.937 回答