자바 리스트와 맵의 성능 비교

자바(Java)는 다양한 데이터 구조를 제공하고 있다. 특히 자바 1.2부터 등장한 Collections 프레임웍에서 유용한 컬렉션 유틸리티 클래스를 많이 보유하고 있다. (컬렉션 프레임웍을 공부하려면 Oracle에서 제공하는 자바 강좌도 유용하다.) 이러한 데이터 구조를 위해 여러 앨거리듬이 사용되는데 대표적으로 해시테이블과 같은 데이터 구조 앨거리듬이나 병합(merge) 정렬 같은 정렬 앨거리듬 같은 것들이 있다.

궁금한 것은 이러한 앨거리듬이 정말로 효과적인가 하는 것이었다.

예를 들어 맵(map)에서 일반적인 데이터 구조인 해시 맵 또는 해시 테이블은 이론상으로 데이터 찾기(search)에 있어 평균 O(1) 시간이 소요된다고 한다. 즉 아무리 데이터 항목 수가 많아도 일정한 실행 시간이 걸린다는 것이다. 따라서 해시테이블은 데이터의 순서는 상관 없으면서 특정 항목을 빠르게 찾고 싶은 경우에 많이 사용된다.

반면에 리스트(list)는 데이터의 순서가 의미 있는 단순 나열이 필요한 경우 많이 사용된다. 그리고 미리 정렬된 리스트가 아닌 경우 특정 데이터 항목을 찾기 위해서는 처음부터 하나씩 비교해서 찾는 수 밖에 없기 때문에 데이터 항목 수가 늘어날수록 그 비용은 증가한다. 찾기 시간은 평균 O(n/2)의 시간이 소요된다고 할 수 있다.

그런데 현실에서도 이게 적용될까? 해시 테이블을 검색하기 위해서는 제일 먼저 찾으려는 키의 해시 값을 구해야 한다. 이게 혹시 시간이 좀 걸리는 작업은 아닐까? 그리고 일반적으로 같은지 다른지만 판단하는 단순 비교는 가장 간단한 작업이고 cpu를 가장 덜 차지하는 연산 중 하나로 알고 있다. 그렇다면 리스트에서 일일이 비교해 찾는 방식이 그렇게 시간이 많이 걸리는 작업은 아니지 않을까?

이런 궁금증을 해결하기 위해 자바 프로그램을 만들어서 실행 시간을 비교해봤다. 결론부터 얘기하자면 다른 성능 비교에서도 많이 보게 되지만 작은 규모에서는 그 차이가 눈에 띌 정도는 아니고 규모가 커지면 그 차이도 커진다는 것이다.

리스트와 맵의 데이터 찾기 성능 1

데이터 항목 수	리스트	맵
10개	20ms	4ms
100개	46ms	13ms
1,000개	1,885ms	19ms

위 표는 임의의 문자열을 10개, 100개, 1000개 넣은 리스트와 맵에 대해 특정 항목을 찾는 작업을 1000회 반복했을 때의 실행 시간을 구한 것이다. 리스트는 ArrayList를, 맵은 HashMap을 사용했다.

리스트나 맵이나 데이터 항목 수 100개까지는 50ms 미만으로 양호한 성적을 보여주지만 1000개가 되자 리스트는 급격히 시간이 늘어난 것을 볼 수 있다. 맵을 사용했을 때는 19ms, 리스트를 사용했을 때는 1885ms이므로 거의 100배의 성능 차이다. 10개와 100개의 차이가 전반적으로 별로 없는 이유는 데이터 찾기 작업 외에 기본적으로 소요되는 시간이 있어서일 거란 추측을 해본다.

일단 이 정도만으로도 데이터 항목 수가 몇 백개 이상인 경우에 대해서는 맵을 사용하면 확실히 이득을 볼 수 있다는 결론을 내릴 수 있다. 하지만 리스트의 특성인 순서가 정해져 있다는 것을 활용하면 어떨까? 미리 정렬했다면 이분 검색(binary search)만으로도 크게 효과를 볼 수 있을 테니 말이다. 그리고 문자열 데이터에 대해 시험했는데 문자열 데이터보다 상대적으로 비교 연산이 단순한 정수형을 사용하면 어떻게 될까? 그래서 다시 시험해봤다.

리스트와 맵의 데이터 찾기 성능 2

데이터 항목 수	문자열 데이터			정수 데이터
	비정렬 리스트	정렬된 리스트	맵	비정렬 리스트	정렬된 리스트	맵
10개	23ms	17ms	6ms	11ms	18ms	6ms
100개	51ms	19ms	11ms	50ms	36ms	26ms
1,000개	1,939ms	119ms	44ms	709ms	107ms	24ms

예상대로 정렬된 리스트의 경우 이분 검색을 활용해 크게 효과를 볼 수 있다(1000개일 때 119ms, 107ms). 이 정도라면 실용적으로는 맵 대신 정렬된 리스트를 사용해도 크게 성능에 문제가 되지는 않을 것이라고 생각된다.

앨거리듬은 어떤 문제를 풀기 위해 사용되는데 프로그램 코딩에 있어서는 대체로 메모리 사용상의 효율성이나 성능상의 효율성의 결과로 나타난다. 위 결과는 앨거리듬이 목적하는 바대로 맵의 성능상의 효과성을 보여주며 적절한 경우 100배까지 성능 차이를 보일 수 있음을 알았다. 하지만 이것은 1000번을 반복 실행했을 때 약 2초 정도 차이므로 일반적인 사용에 있어서는 큰 차이가 나지 않는다고 볼 수 있다. 적절한 앨거리듬을 선택하는 것도 아주 중요하지만 섣부른 최적화(성능 향상)는 독이 될 수 있다는 격언이 있음을 상기해볼 만하다.

PS. 이 성능 비교에 사용된 자바 소스는 이 링크를 눌러 받을 수 있다. 가장 아래 main 메서드부터 먼저 보면 줄거리를 알기 쉬울 것이다.