c++ - 在组合对之间找到共享元素的最佳方法

Question

我有一个类型 A 的有序项目列表，每个项目包含项目 B 列表的一个子集。对于 A 中的每对项目，我想找到它们共享(相交)的项目 B 的数量.

例如，如果我有这个数据:

A1 : B1  
A2 : B1 B2 B3  
A3 : B1  

然后我会得到以下结果:

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

我遇到的问题是使算法高效。我的数据集的大小约为 8.4K 项类型 A。这意味着 8.4K 选择 2 = 35275800 组合。我使用的算法只是遍历每个组合对并进行集合交集。

到目前为止，我所拥有的要点如下。我将计数作为键存储在映射中，值作为 A 对的 vector 。我正在使用图形数据结构来存储数据，但我使用的唯一“图形”操作是 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(我正在将每个 i 打印到一个日志文件中)。当然，这与 8.4K 相去甚远(尽管我知道随着迭代的进行，比较次数会缩短，因为 j = i +1)。有没有更优化的方法？

编辑:明确地说，这里的目标最终是找到前 k 个重叠对。

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

Answer 1

我认为您可以通过预先计算反向(边到顶点)映射来加快速度。这将允许您避免 set_intersection 调用，它执行一堆昂贵的集合插入。我缺少一些声明来制作功能齐全的代码，但希望你能明白。我假设 EdgeList 是某种 int vector :

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

我没有做精确的性能分析，但在双循环中，你用 N*log(M)*log(E) 比较替换“最多 4N 次比较”+ 一些昂贵的集合插入(来自 set_intersection)，其中 N 是每个顶点的平均边数，M 是每个边的平均顶点数，E 是边数，因此根据您的数据集，它可能是有益的。 此外，如果您的边缘索引很紧凑，那么您可以使用简单 vector 而不是 map 来表示反向 map ，这消除了 log(E) 性能成本。

不过有一个问题。既然你在谈论顶点和边，难道你没有边总是有 2 个顶点的额外约束吗？这可以简化一些计算。