요소가 두 벡터에 모두 있는지 확인하는 가장 빠른 방법

Question

그래서 두 개의 벡터 vec1과 vec2가 있다고 가정합니다. 두 벡터에있는 요소에 대해서만 일부 연산을 수행하는 가장 빠른 방법은 무엇입니까? 여기까지, 나는 이것을 만들었습니다. 간단하게, 우리는 어떻게이 빨리 달성하거나 어떤 방법이 있습니다 : 그것은 vec1의 각 요소에 대한 vec2의 요소의 수 std::find 선형을 호출하기 때문에

vector<Test*> vec1; 
vector<Test*> vec2; 

//Fill both of the vectors, with vec1 containing all existing 
//objects of Test, and vec2 containing some of them. 


for (Test* test : vec1){ 

    //Check if test is in vec2 
    if (std::find(vec2.begin(), vec2.end(), test) != vec2.end){ 

     //Do some stuff 

    } 

} 

Answer 1

쉬운 하나의 방법은 n이 vec1의 원소의 개수 std::unordered_set

vector<Test*> vec1; 
vector<Test*> vec2; 

//Fill both of the vectors, with vec1 containing all existing 
//objects of Test, and vec2 containing some of them. 
std::unordered_set<Test*> set2(vec2.begin(),vec2.end()); 

for (Test* t : vec1) { 
    //O(1) lookup in hash set 
    if (set2.find(t)!=set2.end()) { 
    //stuff 
    } 
} 

O (N + m)이고, m은 }

Answer 2

귀하의 접근 방식은 O (M의 *의 N)이다는. 당신은 여러 가지 방법으로 그것을 바탕으로 향상시킬 수 vec2 정렬

• 당신이 O ((N + M) * 로그인 M)에 시간을 단축 할 것이다 - 당신이 범위에 이진 검색을 사용할 수 있습니다 즉 vec2.begin(), vec2.end()
당신이 해시 세트를 사용하여 선형 시간
• 에 일치하는 쌍을 찾기 위해 정렬 된 범위를 병합 유사한 알고리즘을 사용할 수 있습니다 -
• 두 벡터를 정렬하면 O (N 로그 N + M 로그인 M)에서 검색 할 것 vec2 요소는 l이됩니다. 당신은 시간을 O (N + M)으로 줄일 수 있습니다 - 이제는 세트의 생성 시간과 검색 시간이 선형입니다.