C++中集合集的高效集合交集

Question

我有一个集合std::set.我希望以最快的方式找到此集合中所有集合的交集.集合中的集合数量通常非常小(~5-10),每个集合中的元素数量通常小于1000,但偶尔可以达到10000左右.但我需要做几十个交叉点成千上万的时间,尽可能快.我试着对几个方法进行基准测试,如下所示:

1. std::set最初复制第一组的对象中的就地交叉.然后对于后续集合,它遍历其自身的所有元素和集合的第i组,并根据需要从其自身中移除项目.
2. 使用std::set_intersection临时std::set,将内容交换到当前集,然后再次找到当前集与下一集的交集并插入临时集,依此类推.
3. 手动迭代所有集合中的所有元素,如1),但使用a vector作为目标容器而不是std::set.
4. 与4相同,但使用a std::list而不是a vector,怀疑a list将提供从中间更快的删除.
5. 使用散列集(std::unordered_set)并检查所有集合中的所有项目.

事实证明,vector当每组中的元素数量较少时,使用a 略微更快,而list对于较大的集合,使用a 略微更快.就地使用set比两者都慢得多,其次是set_intersection哈希集.是否有更快的算法/数据结构/技巧来实现这一目标？如果需要,我可以发布代码片段.谢谢!

Answer 1

您可能想要尝试概括std::set_intersection():算法是对所有集使用迭代器:

1. 如果任何迭代器已达到end()其相应的集合,则完成.因此,可以假设所有迭代器都是有效的.
2. 将第一个迭代器的值作为下一个候选值x.
3. 遍历迭代器列表和std::find_if()第一个元素至少一样大x.
4. 如果该值大于x使其成为新的候选值并再次在迭代器序列中搜索.
5. 如果所有迭代器都是值,x则会找到交集的元素:记录它,递增所有迭代器,重新开始.

Answer 2

晚上是个好顾问，我想我可能有个主意;）

• 如今，内存要比CPU慢得多，如果所有数据都适合放在L1缓存中，那么它很容易溢出到L2或L3：5组1000个元素已经是5000个元素，这意味着5000个节点，并且一个集合节点包含至少3个指针+对象（即32位计算机上至少16个字节，而64位计算机上至少32个字节）=>至少有80k的内存，而最近的CPU对于L1D来说只有32k，所以我们已经在溢出进入L2
• 先前的事实因以下问题而变得更加复杂：设置节点可能散布在内存周围，并且没有紧密包装在一起，这意味着高速缓存行的一部分充满了完全不相关的内容。可以通过提供一个使节点相互靠近的分配器来缓解这种情况。
• 而且，事实是，CPU在顺序读取方面要好得多（它们可以在需要之前预取内存，因此您不必等待它）比随机读取要好得多（不幸的是，树结构会导致随机读取）阅读）

这就是为什么速度很重要的原因，a vector（或a deque）是如此之好：它们在内存中发挥得很好。因此，我绝对建议您使用vector我们的中介结构；尽管只需要小心地从四肢插入/删除四肢，以避免重新定位。

所以我想到了一个相当简单的方法：

#include <cassert>

#include <algorithm>
#include <set>
#include <vector>

// Do not call this method if you have a single set...
// And the pointers better not be null either!
std::vector<int> intersect(std::vector< std::set<int> const* > const& sets) {
    for (auto s: sets) { assert(s && "I said no null pointer"); }

    std::vector<int> result; // only return this one, for NRVO to kick in

    // 0. Check obvious cases
    if (sets.empty()) { return result; }

    if (sets.size() == 1) {
        result.assign(sets.front()->begin(), sets.front()->end());
        return result;
    }


    // 1. Merge first two sets in the result
    std::set_intersection(sets[0]->begin(), sets[0]->end(),
                          sets[1]->begin(), sets[1]->end(),
                          std::back_inserter(result));

    if (sets.size() == 2) { return result; }


    // 2. Merge consecutive sets with result into buffer, then swap them around
    //    so that the "result" is always in result at the end of the loop.

    std::vector<int> buffer; // outside the loop so that we reuse its memory

    for (size_t i = 2; i < sets.size(); ++i) {
        buffer.clear();

        std::set_intersection(result.begin(), result.end(),
                              sets[i]->begin(), sets[i]->end(),
                              std::back_inserter(buffer));

        swap(result, buffer);
    }

    return result;
}

看来是正确的，但是显然我不能保证它的速度。