为什么当插入到LinkedList和ArrayList时得到不同的输出

我正在使用LinkedList和ArrayList，我知道将元素添加到ArrayList和LinkedList中的概念，但是当我运行检查插入时间的代码时，我得到了对于LinkedList和ArrayList，每次插入的时间都是不同的。

有时LinkedList的插入时间会更好，反之亦然，到底是怎么回事，有人能告诉我吗?

import java.util.ArrayList;
public class Time
   {
   public static void main(String args[])
    {
       int n=100000;
       long milis = System.currentTimeMillis();
       ArrayList obj=new ArrayList();
    for(int k=0;k<=n;k++)
    {
        obj.add(k);

    }
    System.out.println("insert arraylist takes "
            +(System.currentTimeMillis()-milis)+" ms");
}
  }

这个程序的输出是

1)插入数组列表耗时13毫秒2)插入数组列表耗时9毫秒

第二个代码是

 import java.util.LinkedList;
  public class Time1 
  {
        public static void main(String args[])
{
      int n=100000;
      long milis = System.currentTimeMillis();
      LinkedList obj=new LinkedList();
    for(int k=0;k<=n;k++)
    {
        obj.add(k);

    }
    System.out.println("insert linklist takes "
           +(System.currentTimeMillis()-milis)+" ms");
}
 }

的输出

1)插入链表占用8ms

一般来说，链表在除列表末尾以外的任何地方添加和删除元素会更有效，但在列表中查找任意索引时会慢得多。要在任何位置添加或删除元素，LinkedList只需要更改几个引用，但在ArrayList中，该点之后的所有内容都需要移动。在查找任意索引方面，ArrayList只是跳到内存中的那个位置，LinkedList必须遍历每个项直到那个点。

这是一个简单的例子。有两个主要原因导致您没有看到上面的内容:

首先，微基准测试在最好的情况下也很糟糕，尤其是在Java这样的语言中，JIT会在过程中"预热"并改变性能。要么在真实的场景中对它进行基准测试，要么你就可以对任何真实的性能指标说再见了。
其次，ArrayList多年来进行了大量优化，我甚至注意到它在某些情况下执行得更快，而你通常期望LinkedList胜出。

就我个人而言，我会将ArrayList放在我正在使用的实际应用程序中，而不是微基准测试中，并测量性能。如果性能无法接受，我会将实现切换到LinkedList(这应该是一行更改)，然后再次运行基准测试来检查。如果没有这些检查，几乎不可能说什么在您的场景中会表现得更好。

您需要以某种方式使用obj来避免热点优化整个for循环。

每次开始对java进行基准测试时，您都必须非常怀疑您的结果。大多数时候，你的结果会显示出与你所期望的不同的结果。影响程序性能的因素太多了。要进行正确的基准测试，您需要对JVM有深入的了解。我能说出的最简单的几点:

JIT预热(您的第一次基准测试结果通常会比之后的结果差得多)
DCE又名死代码消除。这不是你的情况，但了解它也是有用的

为了获得可以正确解释结果的良好基准测试，我建议查看Java Harness并仔细检查并运行所有示例。

相关内容

最新更新

热门标签：