std::set이랑
std::set_intersection 이거 너무 느린거같은데..
배열이나 벡터로 어케 못할까
c++ 교집합 만드는거
익명(163.180)
2016-05-16 02:57
추천 0
댓글 22
다른 게시글
-
[경희대]<몸과 문명>느낌과 감각 없이 존재하지 않는 것 [1]에어로홍(aerohong) | 16.05.16추천 0
-
어느 귀차니스트의 문제풀이 [3]익명(182.227) | 16.05.16추천 0
-
답은 "가독성"이다 [1]익명(210.113) | 16.05.16추천 0
-
컴공에서 제일 중요한 과목은 무엇인가익명(203.229) | 16.05.16추천 0
-
자바는 어떻게 압도적 1위를 이루어 낸것일까 [3]익명(203.229) | 16.05.16추천 0
-
1~100 까지 3과 5의 배수 표현 내 스타일. [9]codesafer(codesafer) | 16.05.16추천 0
-
왜 이클립스는 존나게 느린가? [3]dd(203.229) | 16.05.16추천 0
-
헬조선 기업에서 보는 인성이란 [1]ㅋㅋ(124.254) | 16.05.16추천 3
-
저 문제가 왜 Python이면 달라질 게 없냐? [2]밍고스사랑..(mingosudaisuki) | 16.05.16추천 0
-
리눅스에서 c 통합개발환경 뭐쓰냐 [3]익명(210.113) | 16.05.16추천 0
집합의 원소가 어떤 형태인데?
int 라능
표현범위가 int 전체?
표현범위는 0부터 한 백만쯤?
음수는 없음
집합의 갯수가 4000개를 넘는다면 각각 radix sort, 아니면 일반 sort 써서 정렬해 놓고 두개의 인덱스가 각각의 집합을 비교하며 1회 지나가면 되잖아.
각각 iterator 만들어서 하는거? 뭔지 알거같은데
응 근데 그냥 배열 인덱스로 움직이는게 더 쌀껄.
그리고 이진탐색도 쓸수 있지만 크게 차이는 없을것 같음.
만약 표현범위가 아주 작다면 걍 히스토그램 배열에 카운팅만 하면 되지.
ㅇㅋㅇㅋ감사욤
백만이면 히스토그램 배열로 잡기가 좀 애매해서 말야. 원소 갯수가 100만 넘으면 땡큐긴한데
원소 갯수는 천개~만개 이정도 될듯
k-way merge
가령 표현범위가 0~255 고 원소 갯수가 무지 많으면 배열 256개 두개 만들어서 각각 집합의 원소에 해당하는 배열인덱스를 1씩 증가시킨 다음 동일 위치의 카운트의 min 값을 교집합으로 정의할 수 있지. 배열 한 개 비교에 몇 만개의 교집합 원소도 뽑아낼 수 있으니 강력해짐.
만약 양쪽다 unique 한 원소를 갖는다면 배열도 하나만 쓸 수 있고. 카운트가 2인 녀석만 교집합인거지
결과적으로 이런건 직접정의한 해시테이블 같은게 가장 유리할 가능성이 있어. 그럼 정렬 안해도 되니까.
만약 니가 radix sort 를 쓸꺼고 표현범위가 100만이라면 MSB 에 해당하는 바이트는 처리할 필요가 없어.
그러니 약 3000개 이상의 자료에서 최적화된 quick 같은 부류보다 유리해지지.
두개의 radix sort 코드를 뜯어서 아랫자리 버킷에서 위로 가면서 두 집합의 공통 버킷 위치에 해당하는 그룹들만 추릴 수가 있어서 해당되지 않는걸 버리면서 진행하면 사실 radix 가 끝난 시점에서 교집합 자체가 만들어지게 할 수 있지.
버킷이란게 해시와 비슷한 구조잖아.
그니까 최적해는 radix 의 개조 라고 생각됨.