10

我有一个集合std::set。我想以最快的方式找到这个集合中所有集合的交集。集合中的集合数量通常非常少（~5-10），每个集合中的元素数量通常少于 1000，但偶尔会达到 10000 左右。但我需要做这些交集几十数千次，尽可能快。我尝试对以下几种方法进行基准测试：

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

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

4

2 回答 2

10

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

  1. 如果任何迭代器已到达end()其对应集合的 ，那么您就完成了。因此，可以假设所有迭代器都是有效的。
  2. 取第一个迭代器的值作为下一个候选值x。
  3. 在迭代器列表中移动，std::find_if()第一个元素至少与x.
  4. 如果该值大于x使其成为新的候选值并在迭代器序列中再次搜索。
  5. 如果所有迭代器都在值上，则x您找到了交集的一个元素：记录它，递增所有迭代器，重新开始。
于 2012-10-13T19:16:45.527 回答
5

夜晚是一个很好的顾问，我想我可能有一个想法；）

  • 这些天内存比 CPU 慢得多，如果所有数据都适合 L1 缓存没什么大不了的，但它很容易溢出到 L2 或 L3：5 组 1000 个元素已经是 5000 个元素，这意味着 5000 个节点，一个集合节点包含至少 3 个指针 + 对象（即，在 32 位机器上至少有 16 个字节，在 64 位机器上至少有 32 个字节）=> 这至少是 80k 内存，而最近的 CPU 只有 32k 用于 L1D，所以我们已经溢出了进入 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;
}

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

于 2012-10-14T12:12:43.363 回答