Collection List

Collection중에 가장 많이 사용하는 것은 아마도 List일것입니다. List에는 여러 구현체가 있습니다.

ArrayList, LinkedList, Vector 가 있는데 오늘 알아볼것은 ArrayList와 LinkedList입니다.

최적화를 알아보기 전에 ArrayList와 LinkedList에 대해서 간략하게 공부하고 넘어가겠습니다.

ArrayList

• 내부 배열에 객체를 저장해서 INDEX로 관리합니다.
• 객체를 추가하는경우 자동적으로 저장 용량이 늘어납니다.
• INDEX를 중간에 추가 또는 삭제할 경우 해당 INDEX 바로 뒤 부터 마지막 INDEX까지 모두 한칸 이동시키고 해당 INDEX에 객체를 추가 또는 삭제시킵니다.

LinkedList

• 각 객체마다 노드를 연결하여 관리합니다.
• 객체를 추가 또는 삭제할 때 노드의 연결위치를 변경해 추가 또는 삭제합니다.

InitialCapacity

List를 많이 다루어봤어도 아마 InitialCapacity는 생소할 수도 있습니다.

보통 기본생성자나 리스트를 copy할 목적으로 사용했지만 사실 ArrayList에는 initialCapacity라는 값도 받고있었습니다.

위에 ArrayList의 특징에 객체를 추가하는경우 자동적으로 저장 용량이 늘어납니다. 라고 적어놓았었는데 여기에는 initialCapacity가 관여합니다.

    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA; // = {};
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

initialCapacity를 설정한다는 것은 ArrayList의 배열의 길이를 설정한다는 것과 같습니다.

다르게말하면 객체를 추가할 때 저장용량을 늘리는 작업을 하지 않게되면 속도가 더 빨라진다는 말이죠.

initialCapacity의 기본값은 10입니다. ArrayList의 길이가 10이 넘어가면 저장용량을 확장하게되는데, List에 저장할 데이터의 수를 이미 알고있다면 initialCapacity를 설정하는것만으로 속도를 향상 시킬 수 있습니다.

속도 테스트 전 테스트 환경

    private static int LOOP = 200;

    public static void speed(String methodTitle, CallbackMethod callback) {

        int avg = 0;
        for (int i = 0; i < LOOP; i++) {

            long startTime = System.currentTimeMillis();

            callback.execute();

            long endTime = System.currentTimeMillis();

            int totalTime= (int) (endTime - startTime);

            avg += totalTime;
        }

        avg /= LOOP;

        System.out.printf("%s Method Average Speed : %dms \n", methodTitle, avg);
    }

평균값을 얻기위해 200번 callback (테스트 메서드가 들어올 callback함수) 메서드를 실행해서 최종 평균값을 확인해보겠습니다.

속도비교

private static final int LIST_SIZE = 1000000; // 1_000_000

    public static void main(String[] args) {

        OptimalTest.speed("ArrayList", ListTest::arrayListTest);
        OptimalTest.speed("InitialCapacity ArrayList", ListTest::initialCapacityTest);

//        ArrayList Method Average Speed : 60ms
//        InitialCapacity ArrayList Method Average Speed : 46ms
//        속도 차이 : 14ms
    }
    
    private static void arrayListTest() {
        List<String> test = new ArrayList<>();
        for (int i = 0; i < LIST_SIZE; i++) {
            test.add(String.valueOf(i));
        }
    }
    private static void initialCapacityTest() {
        List<String> test = new ArrayList<>(LIST_SIZE);
        for (int i = 0; i < LIST_SIZE; i++) {
            test.add(String.valueOf(i));
        }
    }

실제로 capacity 값을 미리 설정해준다면 유의미한 속도향상을 확인할 수 있었습니다.

ArrayList vs LinkedList

어느정도 예상하시겠지만 ArrayList와 LinkedList의 속도도 비교해보았습니다.

    private static final int LIST_SIZE = 1000000; // 1_000_000

    public static void main(String[] args) {
        OptimalTest.speed("ArrayList", ListTest::arrayListTest);
        OptimalTest.speed("InitialCapacity ArrayList", ListTest::initialCapacityTest);
        OptimalTest.speed("LinkedList", ListTest::linkedListTest);
//        ArrayList Method Average Speed : 63ms 
//        InitialCapacity ArrayList Method Average Speed : 47ms
//        LinkedList Method, Speed : 42ms
//        속도 차이 : 22ms
    }

    private static void arrayListTest() {
        ArrayList<String> test = new ArrayList<>();
        for (int i = 0; i < LIST_SIZE; i++) {
            test.add(String.valueOf(i));
        }
    }
    private static void initialCapacityTest() {
        ArrayList<String> test = new ArrayList<>(LIST_SIZE);
        for (int i = 0; i < LIST_SIZE; i++) {
            test.add(String.valueOf(i));
        }
    }
    private static void linkedListTest() {
        LinkedList<String> test = new LinkedList<>();
        for (int i = 0; i < LIST_SIZE; i++) {
            test.add(String.valueOf(i));
        }
    }

저장용량을 늘릴 필요가 없는 LinkedList가 가장 빨랐고,

저장용량을 설정한 ArrayList가 두번째,

저장용량을 설정하지 않은 ArrayList가 가장 느렸습니다.

Remove

    public static void main(String[] args) {
        OptimalTest.speed("ArrayList", () -> arrayListRemove(arraylist));
        OptimalTest.speed("LinkedList", () -> linkedListRemove(linkedlist));
//        ArrayList Remove Method Average Speed : 146ms
//        LinkedList Remove Method Average Speed : 0ms
    }
    
    private static void arrayListRemove(List<String> arraylist) {
        for (int i = 0; i < 1000; i++) {
             arraylist.remove(0);
        }
    }

    private static void linkedListRemove(List<String> linkedlist) {
        for (int i = 0; i < 1000; i++) {
            linkedlist.remove(0);
        }
    }

200번의 테스트때문에 1000번씩 0번 INDEX를 Remove 한 결과입니다.

노드의 경로만 변경해주면되는 LinkedList와는 다르게 ArrayList는 0번 INDEX를 제외한 나머지 배열을 한칸 앞으로 이동해야하기 때문에 속도 차이가 많이 벌어진것입니다.

Add

    public static void main(String[] args) {
        OptimalTest.speed("ArrayList Add", () -> arrayListRemove(arraylist));
        OptimalTest.speed("LinkedList Add", () -> linkedListRemove(linkedlist));
//        ArrayList Add Method Average Speed : 277ms 
//        LinkedList Add Method Average Speed : 0ms 
    }
    
    private static void arrayListRemove(ArrayList<String> arraylist) {
        for (int i = 0; i < 1000; i++) {
             arraylist.add(0, String.valueOf(i));
        }
    }

    private static void linkedListRemove(LinkedList<String> linkedlist) {
        for (int i = 0; i < 1000; i++) {
            linkedlist.add(0, String.valueOf(i));
        }
    }

0번 INDEX에 Add도 마찬가지였습니다.

여기서 중요한건 가장 뒤에 add하는 것은 LinkedList와 ArrayList와의 차이가 나지않을정도로 작습니다.

모든 결과를 보았을 때 전체적으로 LinkedList가 훨씬 좋아보입니다. 그렇다면 이제 ArrayList를 사용하지 않고 LinkedList만 사용해야할 까요?

    public static void main(String[] args) {
        OptimalTest.speed("ArrayList Get", () -> arrayListRemove(arraylist));
        OptimalTest.speed("LinkedList Get", () -> linkedListRemove(linkedlist));
//        ArrayList Get Method Average Speed : 0ms 
//        LinkedList Get Method Average Speed : 712ms 
    }
    
    private static void arrayListGet(ArrayList<String> arraylist) {
        for (int i = 0; i < LIST_SIZE; i++) {
            arraylist.get(LIST_SIZE / 2);
        }
    }

    private static void linkedListGet(LinkedList<String> linkedlist) {
        for (int i = 0; i < 100; i++) {
            linkedlist.get(LIST_SIZE / 2);
        }
    }

INDEX로 값을 가져오는부분에서는 ArrayList가 압도적으로 빠릅니다. 그 이유는 ArrayList는 배열의 INDEX로 값을 가져오기 때문에 O(1)의 속도로 바로 값을 가져오지만 LinkedList는 head부터 해당 index가 나올때까지 값을 검색하기 때문에 최대 O(n)의 속도를 가지기 때문입니다.

실제로 i를 100만번 수행시켰지만 도저히 끝날 기미가 보이지 않아 linkedListGet 메서드의 i를 100으로 설정시켜서 테스트했습니다.

ArrayList는 100만번 수행시켜도 0ms인 값이 변하지 않았습니다.

결론

• ArrayList를 사용할 때, List에 들어갈 데이터의 수를 알고있다면 initialCapacity를 설정하자
• 데이터의 수의 대략적인 수를 알고있다면 initialCapacity를 넉넉하게 설정해도 좋다. 정확하게 설정하는것보다는 느리지만 기본생성자로 설정하는것보다 유의미한 속도향상이 있었다. ( LIST_SIZE = 100만일때,  LIST_SIZE + LIST_SIZE 의 크기로 설정해도 5ms 내외의 차이정도밖에 확인되지 않았다)
• INDEX를 자주사용하는 메서드에서는 무조건 ArrayList를 사용하자.
• List 내에서 추가, 삭제가 빈번히 발생한다면 LinkedList를 사용하자.

# 혼자 공부하고 작성한 글이기 때문에 정확하지 않을 수 있습니다. 대략적인 가이드? 같은것이기 때문에 참고용도로만 사용해주세요.