프로파일 - LinkedListAddBeginning

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

 

연결 리스트에서는 기존 요소를 시프트할 필요 없이 시작에 새로운 요소를 추가할 수 있다. 따라서 LinkedList 시작에 n번 추가하는 연산의 전체 시간은 선형이다.

 

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

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

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

몇 가지만 변경되었다. ArrayListfmf LinkedList 클래스로 변경하였고, 좋은 데이터를 얻기 위해 startN과 endMillis 값을 조정하였다. 측정 값은 이전 배치보다 잡음이 좀 더 커졌다. 결과는 다음과 같다.

128000, 43
256000, 99
512000, 126
1024000, 161
2048000, 397
4096000, 3639
Estimated slope= 1.0965674454715024

이번에는 그래프가 직선이 아니고 기울기도 정확히 1이 아니다. 최소제곱의 기울기도 1.08이다. 하지만 이 결과는 LinkedList 시작에 n번 추가하는 연산의 전체 시간이 적어도 O(n)에 근사함을 나타내므로 각 add 메서드는 상수 시간이다.