더 나은 성능 : LinkedList의 각 반복자에 대해?

Question

내가이 프로그램을 통해 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)); 
    } 
} 

OUPUT은 때마다 즉, 때때로 첫번째 루프가 빠르고, 때로는 두 번째 실행 다르다 .

는

내 질문 :

나는 두 번째 반복자에 비해 속도가 느린 실행해야 각 루프에 대한 생각합니다. 나는 for each 루프에서 링크 목록은 복잡도가 O(n^2) 일 때마다 매초마다 횡단해야한다고 생각한다. 과 비교된다. 나 맞아? 그렇다면 왜 내가 예상했던대로 결과가 나오지 않습니까?

Answer 1

둘은 거의 동일합니다. 두 요소 모두 O (n)이고 각 요소는 정확히 한 번 반복됩니다. 어느 쪽도 반복을 반복하지 않습니다.

각 루프마다 후드 아래의 반복기를 사용합니다. Iterable을 구현하는 객체에 대한 반복을위한 문법적 설탕으로 차례대로 반복자를 만듭니다. 그리고 두 사람이 꽤 비슷하다고 말했을 때 나는 문자 그대로를 의미했습니다.

마이크로 벤치마킹은 매우 어렵습니다. 가장 큰 문제는 우리가 한 가지 타이밍을 밟고 있다고 생각하게되지만, 실제로는 다른 타이밍을 잡는 것입니다. 실제로 일어나고있는 일을 이해하기 위해 모든 것을 따로 따로 파기 위해 많은 파기가 필요합니다. 다음의 관련 게시물에 대한 답변을 읽으십시오. 그러면 왜 시간이 많이 달라지는 지 그리고 어떻게 작업 할 수 있는지에 대해 설명합니다. Why are floating point operations much faster with a warmup phase?. 그 질문의 SO는 벤치 마크에 대한 자신의 견해와 거의 같았으며 목록 반복보다는 부동 소수점 연산만을 사용했습니다.

간단한 요약은 1) JVM이 인터프리터를 통해 코드 실행을 시작하고 즉시 코드의 핫 영역을 최적화합니다. 2) GC 및 기타 백그라운드 프로세스가 간섭을 일으킬 수 있으며 일부는 JVM에있을 수 있으며 다른 프로세스가있을 수 있습니다. JVM 외부.