哪個性能更好：對於LinkedList中的每個或迭代器？

我已經在通過程序遍歷鏈表被檢查的每個 VS 迭代性能：哪個性能更好：對於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)); 
    } 
}

的輸出繼電器，我得到的是不同的每一次即有時第一循環跑得快，有時第二。

我的問題：

我覺得每個循環應該運行比第二迭代緩慢。我認爲在for each循環中，鏈表應該從頭開始遍歷，每次複雜度爲O(n^2)，而O(n)複雜度爲Iterator。我對麼？如果是，那麼爲什麼結果不如我預期的那樣...

來源

2014-09-10 sagar

LinkedList總是從開始節點遍歷到結束。 – 2014-09-10 09:57:49

不，你不正確。每次foreach循環不需要從頭開始迭代。 – Sneftel 2014-09-10 10:01:26

@JunedAhsan我有一個想法，我的問題是爲什麼不是爲每個循環運行緩慢。 – sagar 2014-09-10 10:01:36

這兩者基本上是等價的，它們都是O（n），因爲每個元素都只是迭代一次。重複迭代都不重複。

for each loop使用引擎蓋下的迭代器。它是用於迭代實現Iterable的對象的語法糖，它依次創建一個Iterator。因此，當我說這兩者幾乎相當時，我的意思是字面意思。

微基準測試非常難以正確。最大的問題是我們最終認爲我們正在計時一件事，但實際上我們正在計時其他事情;並且需要大量的挖掘才能瞭解真正發生的事情。請閱讀以下相關文章的答案，這將解釋爲什麼時代會有很大差異，並且關於如何處理這個問題。 Why are floating point operations much faster with a warmup phase?。這個問題的SO與基準測試幾乎完全相同，只使用浮點運算而不是列表迭代。快速總結是1）JVM通過解釋器開始執行代碼，並優化動態代碼的熱區域，2）GC和其他背景進程可能會干擾，有些可能在JVM中，而其他可能是在JVM之外。

來源

2014-09-10 10:01:36

k謝謝你的回答 – sagar 2014-09-10 10:03:16

什麼是在你提供的鏈接中提到的熱身階段。 – sagar 2014-09-10 10:07:13

@sagar在該問題的答案中解釋，我已經在這個問題上對這篇文章做了一個非常快速的總結，但是我想避免在這裏重複這篇文章。 – 2014-09-10 10:08:01

哪個性能更好：對於LinkedList中的每個或迭代器？

回答

相關問題