해시 테이블 성능 비교 및 소수 찾기 (BOJ 1620)

삼성 B형 전체 링크

 

참고

- 해시 테이블 Hash Table

- 해시 테이블 추가, 삭제, 수정, 검색

- 해시 응용 - 2차원 배열 탐색

- 해시 응용 - Rush Hour Puzzle (2차원 배열 탐색 응용)

- 해시 테이블 성능 비교

 

BOJ 1620의 MAX_TABLE을 바꿔가면서 성능을 비교해보자.

 

BOJ 1620의 N = 100,000이다.

 

순서대로 

MAX_TABLE = 100 (작은 값이고 소수가 아님)

MAX_TABLE = 107 (작은 값이고 소수)

MAX_TABLE = 100,000 (N과 비슷한 값이지만 소수가 아님)

MAX_TABLE = 100,003 (N과 비슷한 값이지만 소수)

MAX_TABLE = 200,000 (N의 2배, 소수가 아님)

MAX_TABLE = 200,009 (N의 2배, 소수)

MAX_TABLE = 400,000 (N의 4배, 소수가 아님)

MAX_TABLE = 400,009 (N의 4배, 소수)

---

먼저 MAX_TABLE을 작게 잡으면 당연히 충돌이 많아지므로 성능이 떨어진다.

그리고 소수 vs 소수가 아닌 경우는 400,000을 제외하고 소수인 경우가 빠르다.

 

소수의 나머지 연산이 충돌을 조금 덜 일으킨다.

hash 함수에서도 5381이 소수이다. 5381은 B형에서 제공한 값이므로 믿고 사용해도 된다.

unsigned long hash(const char *str)
{
	unsigned long hash = 5381;
	int c;

	while (c = *str++)
	{
		hash = (((hash << 5) + hash) + c) % MAX_TABLE;
	}

	return hash % MAX_TABLE;
}

 

그리고 일정 메모리가 넘어가면 성능에 큰 효과가 없는 것을 알 수 있다.

실제로 B형에서는 초기화까지 해줘야 하므로 메모리가 무작정 크면 초기화 비용이 커지기만 한다.

 

따라서 N에 대한 적절한 크기, 소수는 직접 찾아야 한다.

 

보통 1.5 ~ 2배 사이가 성능이 괜찮은 편이지만, 적당한 소수는 문제를 모두 풀고 찾자.

tc를 모두 pass하면, MAX_TABLE을 바꾸면서 실행시간을 체크하면 된다.

 

소수 찾는 코드는 아래를 참고하자.

bool isPrime(int n) 
{
	for (int i = 2; i * i <= n; i++)
		if ((n % i) == 0) return false;

	return true;
}

int main(void)
{
	/* 크기 N에 대해 적절한 소수를 찾아서 break 하자 */
	for (int i = 100000 /* N */; i < 200000 /* N x 2 */;i++)
	{
		if (isPrime(i) == true)
		{
			printf("%d\n", i);
			break;
		}
	}
    
    return 0;
}