c++ - 在 C++ 中执行 vector 交集

Question

我有一个无符号 vector 的 vector 。我需要找到所有这些无符号 vector 的交集，为此我编写了以下代码:

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;
   }               
}

每个单独的 vector 有 9000 个元素，“t”中有很多这样的 vector 。当我分析我的代码时，我发现 set_intersection 占用的时间最多，因此当有许多 func() 调用时会使代码变慢。有人可以建议我如何使代码更高效。

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

编辑: vector “t”中的单个 vector 已排序。

Answer 1

我没有一个框架来描述这些操作，但我肯定会更改代码以重用易于分配的 vector 。此外，我会将初始交叉点提升到循环之外。此外，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 的二进制计数器 来保留中间集。这种方法假定结果很可能是非空的。如果期望结果是空的，那可能不是改进。