STL의 multimap 에서 교집합 구하기..
글쓴이: kleinstein / 작성시간: 화, 2006/11/07 - 12:18오전
STL 의 multimap 콘테이너가 2개 있습니다.
std::multimap<double,int> A;
std::multimap<double,int> B;
..
여기서 A와 B의 키값이 아닌 value값, 그러니까 int 값들중에 서로 공통인 값들이 있으면(교집합) 이 놈들을 찾아서 또다른 multimap 형태로 만들어주고 싶은데요..
set_intersection() 함수를 사용해 보려고 하는데.. 사용법이 도통 이해가 안됩니다.
multimap 콘테이너에서 교집합은 어떻게 구하는건지 힌트라도 좀 주시면 정말 감사드리겠습니다.
Forums:
정확히 어떤 동작을 원하시는지 궁금하네요..
만약에 키 값이 서로 다르지만 value값이 서로 같은 것이 발견되었다면 또 다른 멀티 맵에는 키가 어떤 값이 들어가나요?? 정확히 무엇을 하려고 하시는 것인지 잘 모르겠습니다.
즉, 그러니까... 교집합이라고 하는 것은 집합 A와 집합 B에 서로 같은 원소가 있으면 이것을 C에 넣어주면 되는 것인데... A에는 (3.0, 7)이 들어있고, B에는 (4.0, 7)이 들어있으면 이 두 원소는 서로 같은 것이 아닙니다. 그러나 이것을 같은 것으로 취급하여 교집합을 구한다고 하셨는데, 문제는 그러면 C에는 어떤 키 값이 들어가는 것인지요...
블로그: http://turtleforward.blogspot.com
만약 교집합을
만약 교집합을 구할수만 있으면.. 사실 키값은 더이상 중요하지 않아서 버려도 됩니다..
중요한건 양쪽 모두에 들어있는 value 값들을 뽑아내는게 주 목적이라서요..
그렇다면...
우선 pair를 받아서 그것의 second만 리턴하는 함수를 하나 만듭니다.
transform 함수를 이용하여 모든 multimap의 원소에 대하여 second만 뽑아낸 것을 컨테이너 종류에 다 넣습니다. 이렇게 되면 pair형태에서 값 만을 가진 것들이 컨테이너에 들어가게 됩니다.
이제 set_intersection 함수를 적용해 줍니다.
블로그: http://turtleforward.blogspot.com
대략 이런 코드가 나오지요...
template <typename first_type, typename second_type> second_type GetSecond(const std::pair<first_type, second_type>& p) { return p.second; }위의 함수가 second를 반환하는 함수입니다. 위 함수를 정의해주고 아래와 같은 연산을 하면 원하시는 교집합이 구해집니다. a와 b는 멀티맵이고 va, vb, vc는 std::vector<int>입니다.
std::transform(a.begin(), a.end(), std::back_inserter(va), GetSecond<double, int>); std::transform(b.begin(), b.end(), std::back_inserter(vb), GetSecond<double, int>); std::sort(va.begin(), va.end()); std::sort(vb.begin(), vb.end()); std::set_intersection(va.begin(), va.end(), vb.begin(), vb.end(), std::back_inserter(vc));블로그: http://turtleforward.blogspot.com
sort 는 필요없습니다.
multimap 이 이미 정렬되어 있기때문에 va, vb 에도 정렬되어 들어가지요.
필요합니다.
필요합니다. multimap에는 key값을 기준으로 정렬되어 있으므로 data값에 대해서는 정렬이 되어 있지 않습니다. 그냥 벡터로 하지말고 밑에 쓴 것처럼 set에 넣어버리면 소트 안해도 되겠죠..
블로그: http://turtleforward.blogspot.com
제가 실수했네요
글을 고칠려고 했더니 only2sea 님께서 벌써 답글을 달으셔서 약간 민망 ^_^
그렇다면 multimap 을 집합관련algorithm 에 쓸려면 함수의 마지막 인자로 value_comp() 를 넣어주어야겠군요.
STL 공부할 때는 이게 왜 있나 했었는데 이런 때 쓰는 거였군요.
앗.. 그렇군요...;;
앗... 그렇군요.. 너무 일찍 답글을 달아버려서....
스펙이 약간 헷깔려서... -_- 저도 소팅 할 필요 없을거라고 생각하고 있었습니다. 한 번 더 생각하니 아차~ 해서 저도 포스팅 하기 직전에 소트 두줄 집어넣었거든요...;;;;ㅋㅋ...
블로그: http://turtleforward.blogspot.com
추가로...
만약에 출력하는 값에는 중복된 값이 안 나와야 한다면
std::transform(a.begin(), a.end(), std::inserter(set_a, set_a.begin()), GetSecond<double, int>); std::transform(b.begin(), b.end(), std::inserter(set_b, set_b.begin()), GetSecond<double, int>); std::set_intersection(set_a.begin(), set_a.end(), set_b.begin(), set_b.end(), inserter(set_c, set_c.begin()));이렇게 되어야 하고, 대신에 set_a, set_b, set_c는 std::set<int>이어야 합니다. 위와 같이 벡터로 하면 소팅도 해 주어야 하고 하니까... 이 방법으로 하면 소팅 안 해도 되겠죠...
블로그: http://turtleforward.blogspot.com
해결되고 나니 이제는 속도가 문제가 되네요..
감사합니다..
결국 2개의 multimap 자체에서 교집합을 구하는 방법은 없는것이었군요..
여러분들이 제안해주신 방법처럼 multimap 에서 원하는 값을 뽑아서 1차원 Array 형태로 뽑아낸후에 이걸 이용해서 교집합을 구하는 방법이 정답처럼 보입니다.
그런데 이게 참 속도가 느리네요..
하나의 multimap 안에 보통 2만개~ 10만개 정도의 값들이 들어있구요..
교집합을 구했을때 교집합안에 들어가는 원소들의 갯수가 매번 약 3500~7000개 가량되고 이 모든 과정을 보통 100,000번 가량 반복하니까..
도저히 너무 느려서 사용을 못하겠습니다.
하지만.. 더 빠른 방법은 없겠지요?
최소한 time complexity 상으로는 최적일겁니다.
좀더 빠른 방법이 요구되어진다면 이제는 좀더 machine 에 가까운 방법이어야 하는데...
아예 시작부터 multimap 을 쓰지 않는 방법을 찾으시는 것이 좋을 것 같습니다.
속도를 더 빠르게 하려면...
윗분 말씀대로 멀티맵에 문제가 있습니다. 교집합을 효율적으로 구하려면 자료가 소팅이 되어 있어야 합니다. 정렬이 되어 있으면, 자료 수에 비례하게 시간이 걸립니다.
만약에 멀티 맵의 키 값들의 교집합을 구한다면 훨씬 빠르게 구할 수 있습니다. 하지만 지금 상황에서는 그렇지 않기 때문에 소팅되어 있지 않은 상태에서 교집합을 구하려면 시간이 훨씬 많이 걸립니다. 그래서 소팅을 하고나서 교집합을 구하는 것인데요... 더 빠르게 하는 방법이 없는 것은 아닙니다. 몇만개가 넘는다면, 생각 할 수 있는 방법이 물론 있지요. 수의 범위는 정수의 범위이고 자료의 수는 적당히 많은 몇 만개라면, 적당한 수의 버킷을 만들어서 버킷에 집어 넣는 방법을 사용하면, 좀 더 빠른 결과가 나올 수도 있을 겁니다.... 아니라면 고작 몇 만개 정도로는 오히려 더 나쁜 결과가 나올지도 모르겠군요.
제가 보여 드린 방법이 O(nlg n) 정도라면, 이 방법을 잘 활용하면, 평균적으로는 O(n)만에 할 수 있을 겁니다. 단 문제의 사이즈가 커야 도움이 될 것입니다.
안타깝게도 O(n) 이하로 내리는 것은 불가능할 것 같습니다. 모든 자료를 한번씩은 봐야 하기 때문이지요.
알고리즘적인 시간 복잡도 외에 캐시 히트를 잘 이용하신다거나, 아니면 여러 대의 컴퓨터를 이용하신다면, 더 좋은 결과를 얻으실 수 있겠습니다.
블로그: http://turtleforward.blogspot.com
댓글 달기