[Java] List, Set 성능 비교

Jeerryy·2023년 2월 2일
1

java

목록 보기
1/1
post-thumbnail


문득 노션을 정리하던 중 한창 자바로 알고리즘 공부를 하던 시절에 알게 된 내용들을 정리해둔 글을 보게 됐다. (나의 영업 비밀)

내용을 정리한지도 2년이 넘었고 실무에서는 자바스크립트를 사용하고 있다보니 내가 쓴 글인데 한번에 와닿지가 않았다.
물론 알고리즘을 위한 내용이거나 Collection Big-O와 관련된 내용이라 대충 검색해보고 그렇구나~하면서 넘길 수 있지만 자바도 다시 시작해볼 겸 직접 코드로 구현하고 확인해보기로 했다.

실험 대상 선정

오늘 비교해보고 싶은 내용은 아래와 같다.

  • Collections.contains() 속도 차이
    1. List 보다 Set이 훨씬 빠름 → 다만 데이터 쌓는 시간은 Set이 더 오래 걸림
  • Linked List와 ArrayList 데이터 추가 삭제 시간 차이
    1. 단순 데이터 검색 시에는 ArrayList가 훨씬 빠름 ArrayList : LinkedList = O(1) : O(N)
    2. 데이터 삽입, 삭제 시에는 LinkedList가 훨씬 빠름 ArrayList : LinkedList = O(N) : O(1)

요약하자면 List, Set Collection 간에 add,remove,contains 성능 테스트다.
여기에 추가로 List의 get까지 테스트해보려고 한다.

자바 컬렉션을 참고해서 List는 ArrayList, LinkedList, Tree는 HashSet,TreeSet 기준으로 테스트 해보도록 하자.

테스트 방법

성능 측정에 자주 사용되는 nanoTime을 활용하여 각 Collection별 method를 100,000번 실행하고 총 소모 시간을 측정한다.

테스트 환경

  • device : M1 Macbook air 16GB RAM (Ventura 13.1)
  • jdk version: openjdk-19

초기 설정

final int MAX_VALUE = 100000;
ArrayList<Integer> arrayList = new ArrayList<>(MAX_VALUE);
LinkedList<Integer> linkedList = new LinkedList<>();
Set<Integer> hashSet = new HashSet<>(MAX_VALUE);
Set<Integer> treeSet = new TreeSet<>();

Instance 생성 시 길이를 정할 수 있는 Collection은 MAX_VALUE로 길이를 미리 지정해두었습니다.

테스트 코드

protected void add(T<Integer> object) {
        long startTime = System.nanoTime();
        for (int i = 0; i < MAX_VALUE; i++) {
            object.add(i);
        }
        long endTime = System.nanoTime();
    }

    protected void remove(T<Integer> object) {
        Iterator<Integer> iterator = object.iterator();
        long startTime = System.nanoTime();
        while (iterator.hasNext()) {
            iterator.next();
            iterator.remove();
        }
        long endTime = System.nanoTime();
    }


    protected void contains(T<Integer> object) {
        long startTime = System.nanoTime();
        for (int i = 0; i < MAX_VALUE; i++) {
            object.contains(i);
        }
        long endTime = System.nanoTime();
    }
    
    protected void get(T<Integer> object) {
        long startTime = System.nanoTime();
        for (int i = 0; i < MAX_VALUE; i++) {
            object.get(i);
        }
        long endTime = System.nanoTime();
    }

전체 코드를 보고 싶다면 여기를 참고해주세요.

Big-O

결과를 보기 전에 Java Collection별 Big-O와 시간복잡도를 보고 결과를 미리 예측해보자.


시간복잡도 이미지를 해석하면 아래와 같다. 오른쪽으로 갈수록 느리다는 뜻
O(1) < O(log g) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)

표를 기준으로 결과를 예측해보면

add : ArrayList(1) = LinkedList(1) = HastSet(1) < TreeSet(log n)
remove: HashSet(1) = LinkedList(1) < TreeSet(log n) < ArrayList(n)
contains: HashSet(1) < TreeSet(log n) < ArrayList(n) = LinkedList(n)
get: ArrayList(1) < LinkedList(n)

왜 이렇게 결과가 나오는지는 Collection이 동작 방식을 확인하면 되는데 이 부분은 다음에 다뤄보려고 한다.

결과


이쁘게 출력해본다고 출력해봤는데 역시 텍스트는 텍스트. 차트로 정리하면 아래와 같다.

예상 결과와 실제 결과를 비교해보자.

예상 결과

add : ArrayList = LinkedList = HastSet < TreeSet
remove: HashSet = LinkedList < TreeSet < ArrayList
contains: HashSet < TreeSet < ArrayList = LinkedList
get: ArrayList < LinkedList

실제 결과

add : LinkedList < ArrayList << HashSet << TreeSet
remove: LinkedList < TreeSet < HashSet <<< ArrayList
contains: HashSet < TreeSet << ArrayList <<< LinkedList
get: ArrayList << LinkedList

get 말고는 일부 혹은 전체 결과가 예상 결과를 벗어난다. 잠시 정신을 차려고 검증하려 했던 원래 내용을 보자.

  • Collections.contains() 속도 차이
    1. List 보다 Set이 훨씬 빠름 → 다만 데이터 쌓는 시간은 Set이 더 오래 걸림
  • Linked List와 ArrayList 데이터 추가 삭제 시간 차이
    1. 단순 데이터 검색 시에는 ArrayList가 훨씬 빠름 ArrayList : LinkedList = O(1) : O(N)
    2. 데이터 삽입, 삭제 시에는 LinkedList가 훨씬 빠름 ArrayList : LinkedList = O(N) : O(1)

세부적으로 결과와 검증해보자.

  • Collection.contains() 속도는 List 보다 Set이 훨씬 빠름
    • HashSet < TreeSet << ArrayList <<< LinkedList → TRUE
  • 다만 데이터 쌓는 시간은 List보다 Set이 더 오래 걸림
    • LinkedList < ArrayList << TreeSet << HashSet → TRUE
  • 단순 데이터 검색 시에는 ArrayList가 훨씬 빠름
    • ArrayList << LinkedList → TRUE
  • 데이터 삽입, 삭제 시에는 LinkedList가 훨씬 빠름
    • LinkedList < ArrayList << TreeSet <<< HashSet → TRUE


검증된 Big-O와 시간복잡도 자료로 예상한 결과보다 노션에 정리한 내용이 실제 결과와 일치했다.
테스트 방법이 잘못되었는지, 변수 통제가 잘안되었는지.. 실제로 어떻게 이런 결과를 얻게 되었는지는 모르겠다.

이유에 대해서 분석해보려고 하겠지만 혹시나 이유를 알고 계신 고수님이 계신다면 댓글 부탁드립니다..!

자료 출처

profile
다양한 경험을 해보고자 하는 Backend-Engineer. [2023년은 내실 다지기의 해]

0개의 댓글