java - 哪个性能更好: for each or iterator in LinkedList?

Question

我一直在检查 foreach 与 Iterator 在通过程序遍历 LinkedList 时的性能:

public class ListTraversePerformance {
    public static void main(String... args){
        List<String> list = new LinkedList<String>();
        for(int i=0;i<100000;i++){
            list.add("Any String" + i);
        }
        Iterator i = list.iterator();
        String x;
        long t1 = System.currentTimeMillis();
        for(String j: list){
             x = j;

        }
        long t2 = System.currentTimeMillis();
        while(i.hasNext()){ 
            x= (String)i.next();

        }
        long t3 = System.currentTimeMillis();
        System.out.print((t2-t1) + "  " + (t3-t2));
    }
}

我每次得到的输出都是不同的，即有时第一个循环运行得很快，有时第二个循环运行得很快。

我的问题:

我认为foreach循环应该比第二个迭代器运行得慢。我认为在 for every 循环中，链表每次都应该从头开始遍历，使其复杂度 O(n^2) 与 O(n) 迭代器的复杂性。我对么？如果是的话为什么结果不符合我的预期......

Answer 1

两者几乎是等价的，而且它们的复杂度都是 O(n)，因为每个元素都被精确地迭代一次。都不重复迭代。

foreach循环在底层使用了一个迭代器。它是对实现 Iterable 的对象进行迭代的语法糖。 ，这又创建了一个迭代器。因此，当我说两者几乎相同时，我的意思是字面意思。

正确进行微观基准测试非常困难。最大的问题是，我们最终认为我们正在为一件事计时，但实际上我们正在为另一件事计时；需要进行大量挖掘才能将其全部拆开才能了解到底发生了什么。请阅读以下相关帖子的答案，它将解释为什么时间差异如此之大，以及如何处理它。 Why are floating point operations much faster with a warmup phase? 。该问题的 SO 与您自己对基准的观察几乎相同，仅使用浮点运算而不是列表迭代。

简单总结是 1) JVM 通过解释器开始执行代码，并动态优化代码的热点区域，2) GC 和其他后台进程可能会干扰，有些可能在 JVM 中，有些可能在 JVM 之外JVM 的。