检查元素是否在两个向量中的最快方法

Question

所以,认为我们有两个向量,vec1和vec2.什么是仅对元素执行某些操作的最快方法,这两个元素都在两个向量中.到目前为止,我已经做到了这一点.简单地说,我们如何更快地实现这一目标,或者有什么办法:

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

你的方法是O(M*N)因为它std::find在vec2每个元素的元素数量中称为线性vec1.您可以通过以下几种方式改进它:

• 排序vec2可以让你减少时间到O((N + M)*Log M) - 即你可以在范围内使用二进制搜索vec2.begin(), vec2.end()
• 对两个向量进行排序可以让您在O(N Log N + M Log M)中搜索 - 您可以使用类似于合并排序范围的算法来查找线性时间内的匹配对
• 使用vec2元素的哈希集可以让你减少到O(N + M)的时间 - 现在集合的构造时间和搜索都是线性的.