code : https://github.com/whco/java-practice/blob/main/java/src/basics/SetVsListBenchmark.java
학습 목표 :
- 자바 ArrayList와 HashSet의 contains() 메소드의 시간복잡도를 이론적으로 생각해 본다.
- 실제 코드를 작성하고 시간을 측정해 이론과 일치하는 지 비교한다.
여러 사이즈 별 HashSet과 ArrayList의 속도차이를 System.nanoTime() 메소드를 이용해 비교해 보았다.
알고리즘 문제를 풀거나 여러 상황에서 특정 문자나 원소가 포함됐는 지 여부를 확인해야 하는 여러 상황이 자주 등장한다.
원소의 개수가 많지 않을 때는 큰 차이가 없다고 보는 사람도 있겠지만 원소의 개수가 n개이면 이론적으로 속도 차이가 n배 난다.
필자의 개발 환경에서 ArrayList와 HashSet의 경우 원소가 겨우 10개인 경우에도 construction과 contains() method를 합친 시간 차이가 2~3배였고, contains() 메소드만 비교할 경우에는 10~20배 가량 차이가 났다.
이후 10배씩 개수를 늘리며 초단위의 결과가 나올 때까지 개수를 늘려서 비교해 보려 하였다.
하지만 10^8개에서 다음과 같은 결과가 나왔다.
HashSet에 add하는 도중 resize해야 하는 상황에서 heap공간의 메모리 한계보다 많은 heap공간을 요구해 중단된 것 같다.
여기까지 돌리는 것만으로도 contains() 메소드에서 ArrayList와 HashSet의 차이가 명확한 걸 볼 수 있었다.
이유는 다음과 같이 ArrayList의 contains() 메소드는 처음부터 끝까지 순서대로 object를 찾아 O(n)이기 때문이고
HashSet의 contains() 메소드는 key의 Hash값을 가진 object가 null이 아닌지만을 판단하여 O(1)이기 때문이다.
정말 원소의 개수에 따라 ArrayList와 HashSet의 contains()의 속도가 linear하게 차이났다면 아름다웠겠지만 메소드의 구체적인 구동방식과 컴퓨터의 작동방식 및 여러 오버헤드 때문에 그렇게까지 나오지는 않은 것 같다. 다음에는 이렇게 조잡하게 내가 System.nanoTime()으로 한 번 한 번씩 구동해서 캡처하는 방식 말고 참고 자료처럼 벤치마킹을 돌려서 깔끔하게 비교하는 것도 해 보고 싶다.
