글 읽기 - 해쉬테이블로도 시간초과가 납니다

ckdgus2482 6년 전 0

처음에 set을 사용해서 제출했었는데 시간초과가 뜨길래 unordered_set으로 바꿔봤습니다.

그래도 여전히 시간초과가 나네요. 뭐가 문제일까요?

#include<cstdio>
#include<unordered_set>
using namespace std;
int main() {
	int T, N, M, x;
	scanf("%d", &T);
	for (int t = 0; t != T; ++t) {
		scanf("%d", &N);
		unordered_set<int> s;
		for (int i = 0; i != N; ++i) {
			scanf("%d", &x);
			s.insert(x);
		}
		scanf("%d", &M);
		for (int i = 0; i != M; ++i) {
			scanf("%d", &x);
			printf("%d\n", s.find(x) != s.end() ? 1 : 0);
		}
	}
}

wwiiiii 6년 전 0

어차피 정렬은 한번만 하면 되니까 내부 순서를 계속 유지해야 돼서 시간이 좀 걸리는 set보다는 그냥 vector에 한번에 받고 정렬시키고 이진 탐색하면 될거같아요!

ckdgus2482 6년 전 0

그리고 벡터에 받아놓고 정렬하면 시간복잡도가 nlogn인데 set을 쓰면 개수가 더 적은 상태에서부터 정렬하기 때문에 보다 빠르게 동작하는걸로 알고 있습니다.

wwiiiii 6년 전 0

unordered_set의 동작은 정확히는 모르는데 해쉬값을 key로 해서 내부적으로 정렬된 binary search tree라고 알고 있습니다.

이게 맞으면 어차피 정수니까 비교 연산엔 큰 시간이 걸리지 않아 아마 set이나 unordered_set이나 성능 차이는 크지 않을거예요.

그리고 벡터에 받아두고 정렬하는 것도 O(nlogn)이고, set에 n개의 원소를 모두 순서대로 삽입하는 것도 O(sigma i = 1 to n (ilogi)) = O(nlogn)이기 때문에 시간복잡도는 같지만 set 컨테이너 자체가 vector보다 유지해야 하는 성질이 더 많기 때문에 상수가 더 크다고 알고 있어요. 실제로 벡터에 순서없이 받아둔 뒤 한번만 정렬하고 쿼리마다 이진탐색으로 처리하게 하면 아슬아슬하게 시간이 통과됩니다

ckdgus2482 6년 전 0

unordered_set이 해쉬값을 key로 해서 정렬상태를 유지한다는건 아닌것 같습니다. 해쉬값을 통해 랜덤액세스 하는걸로 알고 있는데요. 해쉬값을 정렬해둘 이유가 없지 않습니까?

set에 삽입하는건 O(sigma I=1ton(logi))아닙니까? 이진탐색하는데 왜 ilogi죠? 그리고 수학적으로 계산은 잘 못하겠지만 O(sigma I=1ton(logi)) < O(nlogn) 아닌가요?

wwiiiii 6년 전 0

으 O(sigma I=1ton(logi))가 맞아요 잘못썼네요. 그런데 O(sigma I=1ton(logi)) = O(nlogn)은 성립합니다. 그냥 단순한 증명으로는sigma i = n/2 to n (log i) > sigma i = n/2 to n (log n/2) = (n/2)log(n/2)니까 결국 상수배차이라서 위 식이 성립합니다.

unordered_set에 대해서는 찾아보니까 다음과 같네요.

Internally, the elements in the unordered_set are not sorted in any particular order, but organized into buckets depending on their hash values to allow for fast access to individual elements directly by their values (with a constant average time complexity on average). unordered_set containers are faster than set containers to access individual elements by their key, although they are generally less efficient for range iteration through a subset of their elements.

해석이 맞는지는 모르겠는데 해쉬값에 따라 여러 버켓에 담아 저장한다고 하니 질문자분께서 말씀하신것처럼 거의 랜덤액세스가 맞는것 같습니다. set보다도 효율적이라고 돼 있네요. 그런데 해쉬값이 아무래도 넓은 범위에 퍼져 있을 거니까 일정 범위를 순회하는 연산에 대해서는 비효율적이라고 하네요. vector를 사용한다면 메모리 상으로 연속돼있으니까 아마도 캐시 효율이 더 좋을 것이고, 더 빠르지 않을까 추측해 봅니다. STL의 경우 범용성/안정성등의 이유 때문에 상수가 좀 붙을 수 있으니까 간단한 해쉬 함수를 직접 짜서 돌려보는 것도 좋을것같습니다.

ckdgus2482 6년 전 0

네 답변 감사드립니다.

그런데 코드 보시면 unordered_set을 순회하지는 않고 있습니다.

unordered_set<int> us;

for(auto iter : us) {

. . .
}

이런식으로 순회할때 비효율적이라는 얘기 아닙니까? 제 코드에서는 저런식으로 순회하는건 없고 insert메서드와 find메서드만 사용하고 있습니다. 해쉬충돌이 거의 일어나지 않는다는 가정하에 둘 다 O(1)입니다.

확실한 비교를 위해 아래의 코드를 가지고 실험을 해보았습니다.
랜덤데이터 미리 100만개를 만들고 이 랜덤데이터를 vector, set, unordered_set에 insert하는 시간을 구해보았고, 데이터를 넣은 상태에서 어떠한 랜덤 데이터 한개에 대해서 find하는 시간을 구해보았습니다. 참고로 벡터랑 unordered_set은 insert전에 100만개의 공간을 미리 reserve하고 했습니다. 이 시간도 insertTime에 포함시켰구요. 결과를 정리하면 다음과 같습니다. 시간관계상 한번밖에 못돌렸으나 대략적인 비교는 될것 같습니다.

벡터의 경우
1000000개 insert하는데 1.353354140초
정렬하는데 2.865194194초
탐색 1회에 0.000022238초
탐색 1000000회에 22.238초
1000000개 insert + 정렬 + 탐색1000000회 = 26.456548334초

set의 경우
1000000개 insert하는데 14.954904646초
탐색 1회에 0.000008981초
탐색 1000000회에 8.981초
1000000개 insert + 탐색1000000회 = 23.935904646초

unordered_set의 경우
1000000개 insert하는데 9.369510515초
탐색 1회에 0.000008981초
탐색 1000000회에 8.981초
1000000개 insert + 탐색1000000회 = 18.350510515초

일단 실험환경 얘기드리자면 CPU는 i7-4700MQ (2.4GHz~3.2GHz), Ram DDR3 8GB이고 VisualStudio2015사용했습니다. 디버깅은 32bit 로컬 윈도우디버거 이용했구요.

실험결과 unordered_set, set, vector 순으로 빠르네요. 순서만 보면 제 예상과 일치하는데 문제는 세 경우 모두 이 문제를 풀기엔 시간이 너무 오래 걸린다는겁니다. 해쉬테이블 직접구현하더라도 timeout을 면하긴 힘들어보이는데 그럼 이 문제는 어떻게 풀어야하는거죠...?

#include<iostream>
#include<vector>
#include<set>
#include<unordered_set>
#include<algorithm>
#include<random>
#include<chrono>
using namespace std;

int main() {
	random_device rd;
	vector<int> data;
	data.reserve(1000000);
	vector<int> v;
	unordered_set<int> us;
	set<int> s;
	for (int i = 0; i != 1000000; ++i) data.push_back(rd());

	cout << "vector insertTime : ";
	auto tPoint = chrono::high_resolution_clock::now();
	v.reserve(1000000);
	for (auto iter : data) v.push_back(iter);
	cout << (chrono::high_resolution_clock::now() - tPoint).count() << "nano sec" << endl;

	cout << "set insertTime : ";
	tPoint = chrono::high_resolution_clock::now();
	for (auto iter : data) s.insert(iter);
	cout << (chrono::high_resolution_clock::now() - tPoint).count() << "nano sec" << endl;

	cout << "unordered_set insertTime : ";
	tPoint = chrono::high_resolution_clock::now();
	us.reserve(1000000);
	for (auto iter : data) us.insert(iter);
	cout << (chrono::high_resolution_clock::now() - tPoint).count() << "nano sec" << endl;

	int randNum = rd();

	cout << "vector sortTime : ";
	tPoint = chrono::high_resolution_clock::now();
	sort(v.begin(), v.end());
	cout << (chrono::high_resolution_clock::now() - tPoint).count() << "nano sec" << endl;

	cout << "vector findTime : ";
	tPoint = chrono::high_resolution_clock::now();
	binary_search(v.begin(), v.end(), randNum);
	cout << (chrono::high_resolution_clock::now() - tPoint).count() << "nano sec" << endl;

	cout << "set findTime : ";
	tPoint = chrono::high_resolution_clock::now();
	us.find(randNum);
	cout << (chrono::high_resolution_clock::now() - tPoint).count() << "nano sec" << endl;

	cout << "unordered_set findTime : ";
	tPoint = chrono::high_resolution_clock::now();
	us.find(randNum);
	cout << (chrono::high_resolution_clock::now() - tPoint).count() << "nano sec" << endl;
}

ckdgus2482 6년 전 0

bitset을 이용하면 시간내에 가능하겠지만 그러자니 메모리가 512MB필요하네요

wwiiiii 6년 전 0

음...확실히 unordered_set이 더 빨라야 할 것 같네요;

아래 소스로는 800ms로 통과가 되거든요. 왜 이런 차이가 나는지는 잘 모르겠네요

도움이 못돼서 죄송합니다 ㅠ

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
void task()
{
	int n,k;
	vector<int> note;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&k);
		note.push_back(k);
	}
	sort(note.begin(),note.end());
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&k);
		if(binary_search(note.begin(),note.end(),k)) puts("1");
		else puts("0");
	}
}
int main()
{
	int t;
	scanf("%d",&t);
	while (t--) task();
}

wwiiiii 6년 전 0

생각할 수 있는 유일한 경우는 이제 collision이 매우 많이 일어난다는 가정일까요...혹시 중복 원소가 매우 많을 때 unordered_set에서 어떻게 처리되는 지 찾아보면 나을지도 모르겠네요

wwiiiii 6년 전 0

???? 아래 코드 984ms로 아슬아슬하게 통과됐네요

#include <cstdio>
#include <unordered_set>
using namespace std;
void task()
{
	int n,k;
	unordered_set<int> note1;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&k);
		note1.insert(k);
	}
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&k);
		if(note1.find(k)==note1.end()) puts("0");
		else puts("1");
	}
}
int main()
{
	int t;
	scanf("%d",&t);
	while (t--) task();
}

ckdgus2482 6년 전 0

뭐지...

puts가 printf보다 빠른가요?

ckdgus2482 6년 전 0

다시 제출하니 936ms로 통과됐네요. 처음 제출할때 채점머신 컨디션이 안 좋았다봅니다...

아무튼 이 문제는 시간이 상당히 빡빡하군요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

해쉬테이블로도 시간초과가 납니다

ckdgus2482 6년 전 0

wwiiiii 6년 전 0

ckdgus2482 6년 전 0

ckdgus2482 6년 전 0

wwiiiii 6년 전 0

ckdgus2482 6년 전 0

wwiiiii 6년 전 0

ckdgus2482 6년 전 0

ckdgus2482 6년 전 0

wwiiiii 6년 전 0

wwiiiii 6년 전 0

wwiiiii 6년 전 0

ckdgus2482 6년 전 0

ckdgus2482 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말