执行矢量c的交集

概述我有200个存储在vecOfVec中的大小为1到4000000的向量.我需要将这些向量与大小为9000个元素的单个向量“vecSearched”相交.我尝试使用以下代码执行相同 *** 作,但是使用perf工具我发现我正在做的交叉点是我的代码中的瓶颈.我是否有某种方式可以执行有效的交叉路口 #include <cstdlib>#include <iostream>#include <vector> 我有200个存储在vecOfVec中的大小为1到4000000的向量.我需要将这些向量与大小为9000个元素的单个向量“vecSearched”相交.我尝试使用以下代码执行相同 *** 作,但是使用perf工具我发现我正在做的交叉点是我的代码中的瓶颈.我是否有某种方式可以执行有效的交叉路口

#include <cstdlib>#include <iostream>#include <vector>using namespace std;int main(int argc,char** argv) {  vector<vector<unsigned> > vecOfVec; //contains 120 vectors of size ranging from 1 to 2000000 elements. All vectors in vecOfVec are sorted  vector<unsigned> vecSearched; //vector searched in contains 9000+ elements. Vectors in vecSearched are sorted  for(unsigned kbt=0; kbt<vecOfVec.size(); kbt++)  {                                       //first find first 9 values spaced at equi-distant places,use these 9 values for performing comparisons     vector<unsigned> equiSpacedVec;                                  if(((vecSearched[0]))>vecOfVec[kbt][(vecOfVec[kbt].size())-1]) //if beginning of searched vector > last value present in indivIDual vectors of vecOfVec then continue     {         continue;                                  }                              unsigned elementIndex=0; //used for iterating over equiSpacedVec                                  unsigned i=0; //used for iterating over indivIDual buckets vecOfVec[kbt].second     //search for value in bucket and store it in bucketValPos     bool firstRun=true;                  for(vector<unsigned>::iterator itValPos=vecSearched.begin();itValPos!=vecSearched.end();++itValPos)     {         //construct a summarized vector out of indivIDual vectors of vecOfVec         if(firstRun)         {             firstRun=false;             unsigned elementIndex1=0; //used for iterating over equiSpacedVec             while(elementIndex1<(vecOfVec[kbt].size())) //create a small vector for skipPing over the remaining vectors             {                  if((elementIndex1+(10000))<(vecOfVec[kbt].size()))                     elementIndex1+=10000;                  else                     break;                 equiSpacedVec.push_back(vecOfVec[kbt][elementIndex1]);             }                   }         //skip indivIDual vectors of vecOfVec using summarized vector constructed above         while((!(equiSpacedVec.empty()))&&(equiSpacedVec.size()>(elementIndex+1))&&((*itValPos)>equiSpacedVec[elementIndex+1])){             elementIndex+=1;             if((i+100)<(vecOfVec[kbt].size()))                 i+=100;         }                     unsigned j=i;         while(((*itValPos)>vecOfVec[kbt][j])&&(j<vecOfVec[kbt].size())){             j++;         }         if(j>(vecOfVec[kbt].size()-1)) //element not found even at last position.         {             break;         }                       if((*itValPos)==vecOfVec[kbt][j])         {                                                  //store intersection result         }     }  }    return 0;}

解决方法 你的问题非常受欢迎.由于没有关联向量的数据,因此可以归结为加速两个向量之间的交集,基本上有两种方法：

1.没有任何预处理

这通常由三件事来解决：

>重复比较次数.例如,对于小向量(大小为1到50),您应该二元搜索每个元素以避免遍历主题向量的所有9000个元素.
>提高代码质量以减少分支错误预测,例如观察结果集通常比输入集更小的大小可以转换这样的代码：

while (Apos < Aend && Bpos < Bend) {    if (A[Apos] == B[Bpos]) {        C[Cpos++] = A[Apos];        Apos++; Bpos++;    }    else if (A[Apos] > B[Bpos]) {        Bpos++;    }     else {      Apos++;    } }

代码“展开”这样的比较创建虽然更容易预测分支(例如块大小= 2)：

while (1) {    Adat0 = A[Apos]; Adat1 = A[Apos + 1];     Bdat0 = B[Bpos]; Bdat1 = B[Bpos + 1];    if (Adat0 == Bdat0) {         C[Cpos++] = Adat0;    }    else if (Adat0 == Bdat1) {        C[Cpos++] = Adat0;        goto advanceB;    }    else if (Adat1 == Bdat0) {        C[Cpos++] = Adat1;        goto advanceA;    }    if (Adat1 == Bdat1) {        C[Cpos++] = Adat1;        goto advanceAB;    }    else if (Adat1 > Bdat1) goto advanceB;    else goto advanceA;advanceA:    Apos+=2;    if (Apos >= Aend) { break; } else { continue; }advanceB:    Bpos+=2;    if (Bpos >= Bend) { break; } else { continue; }advanceAB:    Apos+=2;  Bpos+=2;    if (Apos >= Aend || Bpos >= Bend) { break; }}//  fall back to naive algorithm for remaining elements

>使用SIMD指令执行块 *** 作

这些技术很难在质量保证环境中描述,但您可以阅读它们(以及相关的优化,如if转换)here和here或查找实现元素here

2.进行预处理

这个恕我直言是一个更好的方式,因为你有一个大小为9000元素的主题向量.您可以从中创建一个间隔树,或者只是找到一种索引它的方法,例如,创建一个可以加快搜索速度的结构：

vector<unsigned> subject(9000+); vector<range>    index(9000/M);

范围是一个类似的结构

struct range {    unsigned min,max; };

从而创建一系列范围

[0,100],[101,857],... [33221,33500]

这将允许在进行交集时跳过许多比较(例如,如果另一组的元素大于子范围的最大值,则可以完全跳过该子范围)

3.并行化

是的,在两个列表中总是有第三个元素：P.如果您已经对程序进行了足够的优化(并且只有那时),请将您的工作分解为块并并行运行.这个问题符合一个令人尴尬的模式,所以200个向量对比1应该定义为“50对1并发4次”

测试,测量,重新设计!!

总结

以上是内存溢出为你收集整理的执行矢量c的交集全部内容，希望文章能够帮你解决执行矢量c的交集所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。