std::set은 생각보다 더 느리다

그래프의 노드에 자연수 번호가 붙여져 있다고 가정할 때, 그래프를 인접 행렬로 저장하려면 vector의 vector를 저장하거나 set의 vector를 저장해야 한다. 나는 중복을 제거하고 싶을 경우에만 뒤의 방법을 쓰고, 평소에는 거의 앞의 방법을 사용한다.

 

그런데 오늘 2-SAT - 4를 풀면서 조금 생각이 바뀌었다.

 

메모리 차이는 별로 의미 없다.

위가 vector<vector<int>>, 아래가 vector<set<int>>를 사용한 코드이다. 분명 자료구조만 바꿨는데도 시간 차이가 크게 난다. 이쯤되면 중복 제거할 때도 set을 사용하지 않을 것 같다. vector에서도 $NlogN$ 시간에 중복을 제거할 수 있기 때문이다.

// https://stackoverflow.com/questions/1041620/whats-the-most-efficient-way-to-erase-duplicates-and-sort-a-vector
sort(vec.begin(),vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());

자료의 순서를 되돌리고 싶다면 std::pair<int, int>에 각각 값과 순서를 저장해 놓고, 중복을 제거한 다음 pair.second 기준으로 정렬하면 된다. 근데 애초에 인접 행렬에서는 순서가 크게 중요하지 않아서 이런 걸 자주 쓸 일은 없을 듯 하다.

 

예전에 BOJ 슬랙에서 어떤 분이 std::set은 $logN$ 자료구조 중에서도 독보적으로 느리다고 하시는 걸 봤는데, 오늘 그 말을 이해했다. 아마 Red-Black tree를 사용하기 때문이라고 했던 것 같은데, 나중에 이게 왜 느린지도 공부해 봐야겠다.