4

我正在使用 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）插入链接列表需要8毫秒

2）插入链接列表需要 17 毫秒

4

3 回答 3

1

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

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

  • 首先，微基准测试在最好的时候很糟糕，尤其是在像 Java 这样的语言中，你有一个 JIT，它会“预热”并改变过程中的性能。要么在现实世界的场景中对其进行基准测试，要么您几乎可以告别任何真实的性能指标。

  • 其次，ArrayList多年来已经看到了很多优化，以至于我什至注意到它在某些情况下表现得更快，而这些情况下你通常会期望LinkedList获胜。

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

于 2013-05-31T12:08:37.213 回答
0

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

于 2013-05-31T14:28:02.977 回答
-1

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

  • JIT 预热（您的第一次基准测试结果通常会比以后更糟）
  • DCE 又名死代码淘汰。这不是你的情况，但了解它也很有用

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

于 2013-05-31T12:21:53.953 回答