查找组合对之间共享元素的最佳方式

Question

我有一个A型订购商品的列表，每个商品都包含一个来自商品列表B的子集。对于A中的每一对商品，我想找到数字他们分享的项目B（相交）。

举例来说，如果我有这样的数据：

A1 : B1 
A2 : B1 B2 B3 
A3 : B1 

然后我会得到以下结果：

A1, A2 : 1 
A1, A3 : 1 
A2, A3 : 1 

我遇到的问题是使得算法效率。我的数据集的大小约为8.4K类型的项目。这意味着8.4K选择2 = 35275800组合。我正在使用的算法是简单地通过每个组合对和做一组交集。

我到目前为止的要点在下面。我将计数存储为地图中的一个关键字，并将该值作为A对的向量。我正在使用图形数据结构来存储数据，但我使用的唯一'图形'操作是get_neighbors（），它从A返回项目的B子集。我碰巧知道图形中的元素是从索引0到8.4K排序。

void get_overlap(Graph& g, map<int, vector<A_pair> >& overlap) { 

map<int, vector<A_pair> >::iterator it; 

EdgeList el_i, el_j; 
set<int> intersect; 

size_t i, j; 

VertexList vl = g.vertices(); 

for (i = 0; i < vl.size()-1; i++) { 
    el_i = g.get_neighbors(i); 

    for (j = i+1; j < vl.size(); j++) { 
     el_j = g.get_neighbors(j); 

     set_intersection(el_i.begin(), el_i.end(), el_j.begin(), el_j.end(), inserter(intersect, intersect.begin())); 
     int num_overlap = intersect.size(); 

     it = overlap.find(num_overlap); 
     if (it == overlap.end()) { 
      vector<A_pair> temp; 
      temp.push_back(A_pair(i, j)); 
      overlap.insert(pair<int, vector<A_pair> >(num_overlap, temp)); 
     } 
     else { 
      vector<A_pair> temp = it->second; 
      temp.push_back(A_pair(i, j)); 
      overlap[num_overlap] = temp; 
     } 
    } 
} 

}

我一直在运行这个程序了近24小时，for循环中的第i个元素已经达到迭代250（我打印每个我到一个日志文件）。当然，这距离8.4K还有很长的路要走（尽管我知道随着迭代的进行，从j = i + 1开始，比较次数会缩短）。有没有更优化的方法？

编辑：为了清楚起见，这里的目标是最终找到最重要的k个重叠对。

编辑2：感谢@Beta和其他人指出优化。特别是，直接更新地图（而不是复制其内容并重新设置地图值）大大提高了性能。它现在在几秒钟内运行。

Answer 1

我想你可以通过预先计算一个反向（边到顶）映射来使事情更快。这可以让你避免set_intersection调用，它会执行一堆昂贵的插入操作。我错过了一些声明来完成功能完整的代码，但希望你能明白这一点。我假设EdgeList都为某种INT载体：

void get_overlap(Graph& g, map<int, vector<A_pair> >& overlap) { 

map<int, vector<A_pair> >::iterator it; 



EdgeList el_i, el_j; 
set<int> intersect; 

size_t i, j; 

VertexList vl = g.vertices(); 

// compute reverse map 
map<int, set<int>> reverseMap; 
for (i = 0; i < vl.size()-1; i++) { 
    el_i = g.get_neighbors(i); 
    for (auto e : el_i) { 
     const auto findIt = reverseMap.find(e); 
     if (end(reverseMap) == findIt) { 
      reverseMap.emplace(e, set<int>({i}))); 
     } else { 
      findIt->second.insert(i); 
     } 
    } 
} 

for (i = 0; i < vl.size()-1; i++) { 
    el_i = g.get_neighbors(i); 

    for (j = i+1; j < vl.size(); j++) { 
     el_j = g.get_neighbors(j); 

     int num_overlap = 0; 
     for (auto e: el_i) { 
      auto findIt = reverseMap.find(e); 
      if (end(reverseMap) != findIt) { 
       if (findIt->second.count(j) > 0) { 
        ++num_overlap; 
       } 
      } 
     } 

     it = overlap.find(num_overlap); 
     if (it == overlap.end()) { 
      overlap.emplace(num_overlap, vector<A_pair>({ A_pair(i, j) })); 
     } 
     else { 
      it->second.push_back(A_pair(i,j)); 
     } 
    } 
} 

我没有做精确的性能分析，但双循环内部，替换“在最4N比较” +一些昂贵的一套插入（从，N * log（M）* log（E）比较，其中N是每个顶点的平均边数，M是每边的平均顶点数，E是边的数量，所以它可以是取决于您的数据集。 另外，如果您的边缘索引是紧凑的，那么您可以使用simplae矢量而不是地图来表示反转地图，从而消除了日志（E）性能成本。

但有一个问题。既然你说的是顶点和边，那么你是否还有额外的约束：边总是有2个顶点？这可以简化一些计算。