在C++中执行向量交集

Question

我有一个无符号矢量矢量.我需要找到所有这些无符号向量的交集,这样做我写了下面的代码:

int func()
{
   vector<vector<unsigned> > t;
   vector<unsigned> intersectedValues;
   bool firstIntersection=true;
   for(int i=0;i<(t).size();i++)
   {
       if(firstIntersection)
       {
           intersectedValues=t[0];
           firstIntersection=false;
       }else{
           vector<unsigned> tempIntersectedSubjects;                                                              
           set_intersection(t[i].begin(),
                  t[i].end(), intersectedValues.begin(),
                  intersectedValues.end(),
                  std::inserter(tempIntersectedSubjects, tempIntersectedSubjects.begin()));
           intersectedValues=tempIntersectedSubjects;
       }         
       if(intersectedValues.size()==0)
           break;
   }               
}

每个单独的向量具有9000个元素,并且在"t"中存在许多这样的向量.当我分析我的代码时,我发现set_intersection占用了最大的时间,因此当有很多fun​​c()调用时,代码会变慢.有人可以建议我如何使代码更有效.

我正在使用:gcc(GCC)4.8.2 20140120(Red Hat 4.8.2-15)

编辑:对矢量"t"中的各个矢量进行排序.

Answer 1

我没有一个框架来分析操作，但我肯定会更改代码以重用易于分配的向量。此外，我会将初始交叉点提升到循环之外。另外，std::back_inserter()应确保将元素添加到正确的位置而不是开头：

int func()
{
    vector<vector<unsigned> > t = some_initialization();
    if (t.empty()) {
        return;
    }
    vector<unsigned> intersectedValues(t[0]);
    vector<unsigned> tempIntersectedSubjects;
    for (std::vector<std::vector<unsigned>>::size_type i(1u);
         i < t.size() && !intersectedValues.empty(); ++i) {
        std::set_intersection(t[i].begin(), t[i].end(),
                              intersectedValues.begin(), intersectedValues.end(),
                             std::back_inserter(tempIntersectedSubjects);
        std::swap(intersectedValues, tempIntersectedSubjects);
        tempIntersectedSubjects.clear();
    }
}               

我认为这段代码很有可能会更快。将不同的集合相交也可能是合理的：您可以为相邻集合对创建一个新的交集，然后将第一个集合与其相关的相邻集合相交，而不是保留一个集合并与之相交：

std::vector<std::vector<unsigned>> intersections(
    std::vector<std::vector<unsigned>> const& t) {
    std::vector<std::vector<unsigned>> r;
    std::vector<std::vector<unsignned>>::size_type i(0);
    for (; i + 1 < t.size(); i += 2) {
        r.push_back(intersect(t[i], t[i + 1]));
    }
    if (i < t.size()) {
        r.push_back(t[i]);
    }
    return r;
}

std::vector<unsigned> func(std::vector<std::vector<unsigned>> const& t) {
    if (t.empty()) { /* deal with t being empty... */ }
    std::vector<std::vector<unsigned>> r(intersections(t))
    return r.size() == 1? r[0]: func(r);
}

当然，您不会真正像这样实现它：您将使用 Stepanov 的二进制计数器来保存中间集。此方法假设结果很可能非空。如果期望结果是空的，那可能不是一个改进。