일종의 삽질기.
두 개의 집합 A, B 가 있는데, A가 B의 부분집합이다. A의 크기는 대략 m, B의 크기는 N이고, 이때 앞의 조건에 의해 m ≤ N 이다.
그리고 C++의 표현으로 하자면,
- set<T> A
- map<T, V> B
가 있다. 여기에서 A랑 B에 모두 들어있는 원소만 특정 함수를 호출하려면 무슨 짓을 해야할까;
첫 구현은, A 의 모든 원소에 대해 B에서 찾아서 특정 함수 F를 호출.
for each( const T& t in A )
F( B[t] )
이러면 시간 복잡도는 O( log N ) * θ( m ). ((std::map 구현이 balanced tree — 보통은 red-black tree — 인 관계로 각 검색 연산의 복잡도는 maximal log N에 비례하고, B[t]로 쓰면 아주 조금 느릴 수도 있지만(임시 객체 생성) 전제만 완벽하면 존재 검사는 불필요))
두번째로는 상당히 삽스러운 구현. 그리고 구현 전체를 여기 쓴건 아니다. 데이터베이스 시간이나 자료 구조에서 흔히 말하는 merge-join 을 이용한 것.
A에 대한 iterator i, ie (시작/끝)
B에 대한 iterator j, je (시작/끝)
while( i != ie && j != je)
{
if( *i < *j ) ++i;
else if( *i > *j ) ++j;
else F(*j, ++i, ++j;
}
이런 식인데, 구현하고 생각해보니 이에 대응하는 STL 함수가 있다;
std::set_intersection( A.begin(), A.end(), B.begin(), B.end(), OutputIteratorInstance );
라는 녀석인데, output-iterator 를 쓴다는 거 빼면 아주 간단한 구조다. 구현 스펙의 제한 사항이 비교 회수가 O(m + N)일 것이기 때문에, 위에서 사용한 merge-join이랑 같을 것이다. 근데 이건 메모리를 추가로 안 쓰려면 — 그리고 메모리 풋 프린트를 좀 줄이려면 — output-iterator 를 하나 만들어야 하겠더라고 -_-a
전에 구현한 C++ function closure를 써서 템플릿으로 쓱쓱 짜긴 했는데 시간 낭비가 되버렸다.
m ≤10, N ≤ 1000 정도라서, 윗 쪽의 hash-join 비슷하다만(해쉬 쓰는 정도로 빠른 검사가 아니라서) 녀석이랑 hash-join merge-join이랑 worst-case의 차이가 무의미해졌다 Orz — m이 충분히 작은 경우(지금의 경우) 오히려 hash-join이 빠르게 된다[…]
돌려줘 내 시간 ㅠㅠ
