프로파일 - ArrayListAddBeginning

>>>>>>> 소스코드.git

 

ArrayList의 시작에 새로운 요소를 추가하는 연산의 성능을 테스트한다. 앞의 분석(ArrayListAddEnd)에 근거하여 각 메서드는 선형이여야 한다. 이는 다른 요소들을 오른쪽으로 시프트하기 때문이다. 따라서 n번 추가 연산은 이차가 된다.

public static void profileArrayListAddBeginning() {
    Timeable timeable = new Timeable() {
        List<String> list;

        public void setup(int n) {
            list = new ArrayList<String>();
        }

        public void timeMe(int n) {
            for (int i = 0; i < n; i++) {
                list.add(0, "a string");
            }
        }
    };
    int startN = 4000;
    int endMillis = 10000;
    runProfiler("ArrayList add beginning", timeable, startN, endMillis);
}

이 메서드는 profileArrayListAddEnd 메서드와 거의 동일하다. 유일한 차이점은 timeMe 메서드로, timeMe 메서드는 인덱스 0에 새로운 요소를 추가하는 두 인자 버전의 add 메서드를 호출한다. 또한, 추가 데이터를 얻고자 endMillis 변수를 키웠다.

 

실행 결과는 다음과 같다.

4000, 24
8000, 39
16000, 171
32000, 694
64000, 2737
128000, 13253
Estimated slope= 1.8847204596149398

 

다음 그림은 문제 크기 대비 실행시간의 그래프를 보여준다.

이 그래프에서 직선은 알고리즘이 선형임을 의미하지 않는다. 오히려 실행시간이 어떤 지수 k에 대해 nᴷ에 비례한다면 결과 그래프는 기울기 k인 직선이 된다. 이때 n번 추가하는 연산의 전체 시간이 n²에 비례하므로 직선의 기울기는 2가 된다.