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

Question

我有一个std::set的集合。我想找到这个集合中所有集合的交集，以最快的方式。集合中的集合数通常很小(~5-10)，每个集合中的元素数通常小于1000个，但偶尔会上升到10000左右。但我需要在成千上万的时间内，尽可能快地完成这些交叉口。我试图对几种方法进行基准测试，如下所示：

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

结果表明，当每个集合中的元素数较少时，使用vector的速度要稍微快一些，对于较大的集合，使用list要稍微快一些。就地使用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只有32k用于L1D，所以我们已经将其溢出到L2中。
• 更复杂的是，设置节点的问题可能分散在内存中，而不是紧密地打包在一起，这意味着缓存行的一部分填充了完全不相关的内容。这可以通过提供一个使节点彼此靠近的分配器来缓解。
• CPU在顺序读取方面要好得多(它们可以在需要内存之前预取内存，所以不必等待它)，而不是随机读取(不幸的是，树结构会导致相当随机的读取)，这进一步加剧了这一点。

这就是为什么速度很重要的地方，vector (或者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;
}

显然，我不能保证对，是这样的速度。