[알고리즘] O(1) 보다 O(logn)이 빠르다? (백준 2776 암기왕 java 해시, 이분탐색)

 

O(1) <<< O(log n)???

 

항해99 수료 후 알고리즘 스터디 중 받았던 어려운 질문..

https://www.acmicpc.net/problem/2776

2776번: 암기왕

 

문제의 핵심 내용은

N(1~1,000,000) 개의 수를 입력받은 후 이를 Array 라고 한다.

M(1~1,000,000) 개의 다음 입력되는 수가 이미 Array에 존재하는지 알아내는 방법에 대한 문제였다.

 

나는 좋은 알고리즘 문제를 골라내기 위해서 알고리즘 분류에 집중해서 문제를 보다 보니

곧바로 이분탐색 문제이겠거니 했었고, 스터디원들이 이분탐색으로 풀길 바라며 문제를 추가했었는데,

해시맵으로 문제를 푼 스터디원이 있었다.

 

생각해보니까 당연히 어떤 값들을 저장하고, 있는지 없는지 체크하는 것 만 한다면 오히려 이분탐색보다 간단하게 풀 수도 있겠다는 생각을 했다.

근데 신기한 점은 해시맵으로 푸는 것 보다 이분 탐색이 0.1 초가량 빠르다는 것.

 

 

1904 ms가 HashMap을 이용한 풀이

1780 ms가 이분탐색을 이용한 풀이이다.

 

 

왜 해시맵이 더 느린가?

 

 

	해시맵	빠름 > 느림	이분탐색
형식	reference type	<	primitive type
연산의 시간복잡도	O(1)	>	O(log n)

 

추가적으로 이분탐색의 경우 탐색 이전에 배열의 정렬 O(n log n)이 필요했기에 당연히 Map이 더 빠른게 아닌가하는 생각이 들었다.

 

시간복잡도만 생각하면 HashMap이 이분탐색보다 빨라야할 것 같은데? 무슨 이유가 있는지 알아보기로 했다.

 

HashMap에서 성능이 “저하”될 수 있는 가능성은 다음과 같음

1. HashMap 의 bucket size가 너무 많이 증가해서
2. 해시 충돌이 자주 일어나는 테스트 케이스

 

사실 1번의 경우 메모리 때문에 OOM이 발생할 우려가 있지 시간과는 크게 문제가 되지 않는 것 같다.

그렇다면 2번 해시 충돌이 자주 일어나는 테스트 케이스때문에 오래 걸리는 걸까?

그렇다고 하기엔 입력받는 N의 범위가 Integer 범위의 정수였다.

Integer 범위에서 같은 해시값을 갖는 정수의 조합이 유의미하게 많을 수는 없다고 생각했고(자바 개발자들은 똑똑하니까),

만약 문자열을 입력 받아 Map에 저장하는 경우라면 해시 충돌을 잘 일으킬 수 있는 테스트 케이스를 만들어 낼 수 있을 것이다.

 

 

실행 시간 비교하기

 

1,000,000개의 요소 Map에 insert vs array 대입 시나리오 테스트

outlier( task 0 , task 2) 빼고 눈대중 평균을 비교하면

array : 350000 map : 14000000 정도로

 

Map과 array 값 대입에 걸리는 시간은 약 40배가량 차이남

추가로, contains 연산도 실행시간을 측정했다.

 

 

outlier(task 0) 빼고 눈대중 평균으로는 8000000 나노초가 걸렸다.

 

즉 array의 특정 요소의 값을 변경하는 연산에 걸리는 시간을 1t라고 한다면,

map.put() 연산은 40t, map.contains() 연산은 20t 쯤 걸린다.

 

이분 탐색의 경우 array index 접근, 대소비교와 같은 가벼운 연산으로 이루어져있으며 배열의 크기가 백만이라는 가정 하에 7번이 최대 탐색 횟수이다. 걸리는 시간을 대충 최대 10t라고하면

map.put, map.contains 연산은 해시 충돌을 고려하지 않더라도 40t, 20t 쯤 걸리게 된다.

 

즉 Map 연산의 시간복잡도 O(1) 과 이분 탐색의 O(log n)은 모든 상수와 계수를 무시한 빅-오 표기법을 사용했기 때문에 이러한 혼란이 발생했고, 실제 연산에 걸리는 시간은 Map의 put, get, contains 등의 연산이 1회의 이분탐색보다 느릴 수 밖에 없다.

 

 

물론 정확하지 않고, 생략된게 많지만… 주저리 주저리

 

언제 Map의 put 연산과 배열의 이분탐색에 걸리는 시간이 비슷해질까? 2의 40승 쯤 되는 크기의 배열에서 이분 탐색을 실행하고 최대의 탐색 횟수만큼 모두 탐색한 경우에 Map의 put 연산과 걸리는 시간이 비슷해진다. (2의 40승은 이미 정수범위를 200배 넘게 초과한 범위이다.)

 

 

사실 그 뒤에 Set이 있었다

 

글을 쓰다보니 Map이 아니라 Set으로 풀면 메모리와 시간을 덜 쓴다는 것을 깨달아버렸다. ㅋ

순서대로 Set, Map, 이분탐색 풀이의 메모리와 시간을 비교한 결과

이런 조회용 이분탐색 유형의 문제를 꼭 이분탐색으로 풀도록 하게 하고싶다면 메모리 제한을 빡세게 걸면 될듯?

 

 

실행시간 측정에 사용된 코드

 

public class TimeComplexity {

	StopWatch stopWatch = new StopWatch();

	@Test
	@DisplayName("map insert n = 1,000,000")
	void mapInsertTime() {
		System.out.println("\\nmap insert operation n = 1,000,000\\n");
		HashMap<Integer, Integer> map = new HashMap<>();
		for (int iter = 0; iter < 11; iter++) {
			map.clear();
			stopWatch.start(String.valueOf(iter));
			for (int i = 0; i < 1000000; i++) {
				map.put(i, i);
			}
			stopWatch.stop();
			StopWatchUtil.printLastTaskInfo(stopWatch, TimeUnit.NANOSECONDS);
		}
	}

	@Test
	@DisplayName("array insert n = 1,000,000")
	void arrayTime() {
		System.out.println("\\narray insert n = 1,000,000\\n");
		int[] array = new int[1000000];
		for (int iter = 0; iter < 11; iter++) {
			stopWatch.start(String.valueOf(iter));
			for (int i = 0; i < 1000000; i++) {
				array[i] = i;
			}
			stopWatch.stop();
			StopWatchUtil.printLastTaskInfo(stopWatch, TimeUnit.NANOSECONDS);
		}
	}

	@Test
	@DisplayName("map contains n = 1,000,000")
	void mapContainsTime() {
		System.out.println("\\nmap contains n = 1,000,000\\n");
		HashMap<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i < 1000000; i++) {
			map.put(i, i);
		}
		for (int iter = 0; iter < 11; iter++) {
			stopWatch.start(String.valueOf(iter));
			for (int i = 0; i < 2000000; i += 2)
				map.containsKey(i);
			stopWatch.stop();
			StopWatchUtil.printLastTaskInfo(stopWatch, TimeUnit.NANOSECONDS);
		}
	}
}

public class StopWatchUtil {

	public static void printLastTaskInfo(StopWatch stopWatch, TimeUnit timeUnit) {
		System.out.printf("task %s : %d %s\\n", stopWatch.lastTaskInfo().getTaskName(),
			(int)stopWatch.lastTaskInfo().getTime(timeUnit), timeUnit.name());
	}
}