정렬된 배열이 더 빠른 탐색을 한다.

질의는 다음과 같다->

무작위로 값을 넣은 정수 배열에서 일정한 조건을 만족한 숫자들의 합을 구하는데

정렬하기 전과 정렬 후의 탐색시간의 차이가 극명하게 달라진다 왜그런가?

import java.util.Arrays;
import java.util.Random;

public class testsorted {

    public static void main(String[] args) {
        // Generate data
        int arraySize = 32768;
        int[] data = new int[arraySize];
        int[] data2 = new int[arraySize];

        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c)
            data[c] = rnd.nextInt() % 256;

        System.out.println("정렬 전 test");
        test(data,arraySize);

        Arrays.sort(data);

        System.out.println("정렬 후 test");
        test(data,arraySize);
    }

    static void test(int[] data, int arraySize){
        long start = System.nanoTime();
        long sum = 0;
        for (int i = 0; i < 100000; ++i)
        {
            for (int c = 0; c < arraySize; ++c)
            {   // Primary loop
                if (data[c] >= 128)
                    sum += data[c];
//                int t = (data[c] - 128) >> 31;
//                sum += ~t & data[c];
            }
        }
        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}
//result:
//정렬 전 test
//8.4610122
//sum = 155184200000
//정렬 후 test
//1.6775919
//sum = 155184200000

결론적으로 이는 컴파일러의 분기 예측로 일어난 일이다.

 분기점은 if (data[c] >= 128)이 곳이다. 컴파일러는 정렬된 배열의 경우

똑똑하게도 128을 기준으로 그 전에 것의 인덱스는 F 그 이후는 T로 일괄적으로 판단해 

매번 조건문을 실행하지 않고 분기적으로 최적화 시켜버린다.

 

 

추가적으로 만약 컴파일러가 이런 분기예측으로 최적화할 수 없는 상황이라면

이러한 비트 연산으로 최적화 할 수 있다.

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

 

대체시 아래와 같은 결과가 나온다

정렬 전 test
1.6214724
sum = 155184200000
정렬 후 test
1.6052886
sum = 155184200000

 

+분기예측에 대한 내용은 좀 더 추가할 예정