불필요한 조건으로 코드가 더 빠릅니까?

두 개의 정렬 된 배열에서 공통 요소를 계산하려면 다음 Java 함수가 있어야합니다. 물음표가있는 줄을 기록하십시오. 분명히 불필요한 조건으로 코드가 더 빠릅니까?

public static int overlap(int[] a, int[] b) 
{ 
    int i = 0, j = 0; 

    int res = 0; 

    while(i < a.length && j < b.length) 
    { 
     if(a[i] > b[j]) 
      j ++; 
     else if(a[i] < b[j]) 
      i ++; 
     else if(a[i] == b[j]) // ? 
     { 
      res ++; 
      i ++; 
      j ++; 
     } 
    } 

    return res; 
}

, 마지막 경우 문이있을 필요가 없습니다 : 그 시점에서 우리는 두 개의 값이 같은 것을 알고있다. 그러나 속도를 테스트 할 때 (나는 수표의 순서가 어떤 차이가 있는지 확인하고 있었다), 불필요한 수표를 사용한 방법은없는 것보다 항상 빠르다 (때로는 2 배).

여기에 무슨 일이 일어나고 있습니까? 신비한 최적화? 나는 명백한 것을 간과하고 있는가? 나는 스탠드 컴파일러, 버전 1.8을 사용하고있다. 나는 바이트 코드를 읽을 수 없으므로, 두포에서 무슨 일이 일어나고 있는지 모른다. 여기

은 전체 테스트 클래스입니다 : https://gist.github.com/pbloem/1523283211454ec58ce9c5b45204eebd

바이트 코드 :의 https://gist.github.com/pbloem/ce4f6758f0bb1424c155c26e83ca88a1

출처

2016-09-23 Peter

언어를 태그하면 도움이 될 것이라고 생각합니다. 그것은 나에게 자바처럼 보인다. –

@HorseFace 실수로 태그를 제거해야합니다. 감사. – Peter

_ 관련 _ 관련 : [지점 예측] (http://stackoverflow.com/questions/11227809/why-is-it-faster-to-process-a-sorted-array-than-an-unsorted-array) – noahnu

아마도 JIT 교환 순서들 최상의 성능을 얻을 수 있지만 "는없이 (그냥"다른 "의 순서를 바꿀 수 없다"만일 " if "를 처음에 다른"if "와 비교하여"else "다음에"if "를 추가 할 때 첫 번째 검사로 시도하고 배열 겹침이 % 90과 같은 경우 마지막"if " 처음에는. 어레이

가 겹치는 배열보다 무작위 A> B 또는 B < 주문시

if(a[i] == b[j]) // say %70 probability after N iterations 
    {     // or less randomized branching 
     res ++; 
     i ++; 
     j ++; 
    } 
    else if(a[i] > b[j]) // %20 probability, medium branching 
     j ++; 
    else if(a[i] < b[j]) // %10, totally random branching, not predictable 
     i ++;

가능하다.

+ if + else가있는 경우 JIT가 그 의미를 예측하지 못할 수 있습니다. 평등을 추가하면 방정식을 제외한 많은 경우를 생략 할 수 있습니다.

주문한 배열과 완전히 무작위로 배열로 시도해 주실 수 있습니까?

@noahnu가 코멘트에서 말한 것처럼 CPU의 분기 예측자를 돕는 것뿐입니다.

출처

2016-09-23 15:45:37

다른 스레드에서 액세스 할 수있는 함수 매개 변수 때문에 JIT에서이를 재정렬 할 수 있다고 생각하지 않습니다. –

그러나 어떤 경우에도 명시 적 동기화가 없습니다. 두 개의 코드는 모든 i와 j 값에 대해 동일하게 동작해야합니다. –

호그 워시! 이 함수 호출자가 'a'와'b'를 변경 한 스레드를 방금 시작했다면 어떻게 될까요? –

-1

System.currentTimeMillis()을 사용하면 JIT 최적화로 인해 때로는 잘못 될 수 있으므로 프로그램의 정확한 경과 시간을 알 수 없습니다. System.nanoTime()을 사용해보십시오.

적절한 마이크로 벤치 마크를 위해 시간 계산에 사용되는 변수를 전역 변수로 사용하십시오.

double sumWith = 0.0; double sumWithout = 0.0;

출처

2016-09-23 16:12:07

불필요한 조건으로 코드가 더 빠릅니까?

답변

관련 문제