Java Collection - 성능 비교

직접 구현한 코드로 재활용하자.

직접 구현한 List, LinkedList

public class Main {
    public static void main(String[] args) {
        int size = 50_000;
        int loop = 10_000;

        System.out.println("**& List 성능 &**");
        CList<Integer> arr = new CList<>();
        System.out.println("List 앞에 추가");
        addFirst(arr, size);
        System.out.println("List 중간 추가");
        addMid(arr, size);
        System.out.println("List 뒤에 추가");
        addLast(arr, size);
        System.out.println("List 조회");
        getIndex(arr, loop, 0);
        getIndex(arr, loop, size / 2);
        getIndex(arr, loop, size - 1);
        System.out.println("List 검색");
        search(arr, loop,0);
        search(arr, loop,size / 2);
        search(arr, loop,size - 1);


        System.out.println("**& LinkedList 성능 &**");
        CLinkedList<Integer> link = new CLinkedList<>();
        System.out.println("LinkedList 앞에 추가");
        addFirst(link, size);
        System.out.println("LinkedList 중간 추가");
        addMid(link, size);
        System.out.println("LinkedList 뒤에 추가");
        addLast(link, size);
        System.out.println("LinkedList 조회");
        getIndex(link, loop, 0);
        getIndex(link, loop, size / 2);
        getIndex(link, loop, size - 1);
        System.out.println("LinkedList 검색");
        search(link, loop,0);
        search(link, loop,size / 2);
        search(link, loop,size - 1);
    }

    private static void addFirst(IList<Integer> list, int size) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add(0, i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("IList 앞의 추가 크기: " + size + ", 성능: " + (endTime - startTime) + "ms");
    }

    private static void addMid(IList<Integer> list, int size) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add(i / 2, i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("IList 중간의 추가, 크기: " + size + ", 성능: " + (endTime - startTime) + "ms");
    }



    private static void addLast(IList<Integer> list, int size) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add(i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("IList 마지막 추가, 크기: " + size + ", 성능: " + (endTime - startTime) + "ms");
    }

    private static void getIndex(IList<Integer> list, int loop, int index) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < loop; i++) {
            list.get(index);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("IList 인덱스 : " + index + ", 반복: " + loop + ", 조회 시간: " + (endTime - startTime) + "ms");
    }

    private static void search(IList<Integer> list, int loop, int value) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < loop; i++) {
            list.indexOf(value);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("value : " + value + ", 반복: " + loop + ", 조회 시간: " + (endTime - startTime) + "ms");
    }
}

**& List 성능 &**
List 앞에 추가
IList 앞의 추가 크기: 50000, 성능: 1468ms
List 중간 추가
IList 중간의 추가, 크기: 50000, 성능: 3628ms
List 뒤에 추가
IList 마지막 추가, 크기: 50000, 성능: 2ms
List 조회
IList 인덱스 : 0, 반복: 10000, 조회 시간: 1ms
IList 인덱스 : 25000, 반복: 10000, 조회 시간: 0ms
IList 인덱스 : 49999, 반복: 10000, 조회 시간: 0ms
List 검색
value : 0, 반복: 10000, 조회 시간: 271ms
value : 25000, 반복: 10000, 조회 시간: 199ms
value : 49999, 반복: 10000, 조회 시간: 126ms

**& LinkedList 성능 &**
LinkedList 앞에 추가
IList 앞의 추가 크기: 50000, 성능: 2ms
LinkedList 중간 추가
IList 중간의 추가, 크기: 50000, 성능: 792ms
LinkedList 뒤에 추가
IList 마지막 추가, 크기: 50000, 성능: 14139ms
LinkedList 조회
IList 인덱스 : 0, 반복: 10000, 조회 시간: 0ms
IList 인덱스 : 25000, 반복: 10000, 조회 시간: 363ms
IList 인덱스 : 49999, 반복: 10000, 조회 시간: 666ms
LinkedList 검색
value : 0, 반복: 10000, 조회 시간: 1443ms
value : 25000, 반복: 10000, 조회 시간: 1069ms
value : 49999, 반복: 10000, 조회 시간: 738ms

다음으로 자바에서 제공하는 컬렉션 프레임워크로 변경해 실행시켜보자.

Java Collection List - ArrayList, LinkedList 측정 결과

**& List 성능 &**
List 앞에 추가
IList 앞의 추가 크기: 50000, 성능: 83ms
List 중간 추가
IList 중간의 추가, 크기: 50000, 성능: 211ms
List 뒤에 추가
IList 마지막 추가, 크기: 50000, 성능: 5ms
List 조회
IList 인덱스 : 0, 반복: 10000, 조회 시간: 1ms
IList 인덱스 : 25000, 반복: 10000, 조회 시간: 0ms
IList 인덱스 : 49999, 반복: 10000, 조회 시간: 1ms
List 검색
value : 0, 반복: 10000, 조회 시간: 380ms
value : 25000, 반복: 10000, 조회 시간: 234ms
value : 49999, 반복: 10000, 조회 시간: 131ms

**& LinkedList 성능 &**
LinkedList 앞에 추가
IList 앞의 추가 크기: 50000, 성능: 4ms
LinkedList 중간 추가
IList 중간의 추가, 크기: 50000, 성능: 1718ms
LinkedList 뒤에 추가
IList 마지막 추가, 크기: 50000, 성능: 3ms
LinkedList 조회
IList 인덱스 : 0, 반복: 10000, 조회 시간: 1ms
IList 인덱스 : 25000, 반복: 10000, 조회 시간: 699ms
IList 인덱스 : 49999, 반복: 10000, 조회 시간: 1385ms
LinkedList 검색
value : 0, 반복: 10000, 조회 시간: 1411ms
value : 25000, 반복: 10000, 조회 시간: 1069ms
value : 49999, 반복: 10000, 조회 시간: 752ms

비교 표

성능 비교 표 - 직접 구현한 List, LinkedList

성능 비교 표 - 자바 자료구조 ArrayList, LinkedList

정리

시간 복잡도와 실제 성능

• 이론적으로는 LinkedList 의 중간 삽입 연산이 ArrayList 보다 빠르다고 하나,
  실제로는 메모리 할당 및 해제 비용이 발생하고, CPU 캐시 활용도와 메모리 순차 접근으로 인한 영향을 받아 배열리스트가 대부분 빠르다.
  • ArrayList는 한 칸씩 옮기지 않고 메모리 고속 복사를 이용함
• ArrayList같이 배열처럼 메모리에 연속된 위치인 경우 CPU 캐시가 높으며, 메모리 접근 속도가 빠르다.
• LinkedList는 요소가 별도의 객체로 존재하며 다음 요소를 참조로 저장해 CPU 캐시 활용도가 떨어지는 편이다. 참조 값으로 이루어져 있기에 메모리 접근 속도도 ArrayList 비하면 느린 편이다.

ArrayList vs LinkedList

데이터가 앞에서 입력하고 꺼내는 경우 LinkedList 자료구조로 사용하고, 그외의는 ArrayList로 사용하는 것이 좋다.