두 집합에 공통으로 들어있는 원소에 대한 연산

일종의 삽질기.

두 개의 집합 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).¹

두번째로는 상당히 삽스러운 구현. 그리고 구현 전체를 여기 쓴건 아니다. 데이터베이스 시간이나 자료 구조에서 흔히 말하는 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의 차이가 무의미해졌다 — m이 충분히 작은 경우(지금의 경우) 오히려 hash-join이 더 빠르다.