如何优化C++的std::set_intersection性能？为何Python实现更快？

这是个非常有意思的性能对比问题，咱们先拆解背后的原因，再给你针对性的C++优化方案。

一、Python set更快的核心原因 #

两者底层实现的差异是关键，这直接决定了性能表现：

• 数据结构不同：Python的set是哈希表（开放寻址法实现），而C++的std::set是红黑树（有序平衡二叉树）。哈希表的元素查找平均复杂度是O(1)，而红黑树是O(logn)。虽然std::set_intersection用双指针遍历实现了O(n+m)的时间复杂度，但红黑树的迭代器是双向迭代器，节点分散在堆内存中，缓存命中率极低，实际运行时的常数开销远大于哈希表。
• 内存布局优势：Python的set元素存储在连续的数组桶中（开放寻址法），缓存局部性好，CPU能高效利用缓存加载数据；而std::set的每个节点都是单独的堆分配对象，节点之间靠指针链接，迭代时会频繁触发缓存失效，拖慢整体速度。
• 底层实现的高度优化：Python的set操作是用纯C实现的底层代码，没有C++模板的额外开销，而且哈希表的插入、查找逻辑经过了多年的打磨优化，比如负载因子的调整、哈希函数的选择都非常高效。

二、C++代码的优化方案 #

要追上甚至超过Python的性能，核心是换用和Python set同类型的数据结构，再配合一些细节优化：

1. 替换std::set为std::unordered_set #

std::unordered_set是C++标准库中的哈希集合，和Python set底层逻辑一致。我们需要手动实现交集操作（因为std::set_intersection只支持有序容器）：遍历较小的集合，逐个检查元素是否存在于另一个集合中，存在则插入结果集。

2. 优化内存分配 #

提前用reserve()预留足够的空间，避免哈希表频繁rehash和内存分配的开销，这对填充集合和交集操作都有明显的性能提升。

3. 遍历较小集合减少查找次数 #

交集操作时，遍历元素数量更少的集合，能减少总查找次数，进一步降低时间开销。

优化后的完整代码 #

#include <iostream>
#include <unordered_set>
#include <chrono>
#include <functional>

void elapsed(std::function<void()> f, const std::string& s) {
    auto start = std::chrono::steady_clock::now();
    f();
    std::chrono::duration<double> elapsed = std::chrono::steady_clock::now() - start;
    std::cout << s << " " << elapsed.count() << " seconds" << std::endl;
}

template <typename T>
void fill_set(std::unordered_set<T>& s, T start, T end, T step) {
    // 提前计算需要的空间并预留，避免多次rehash
    const size_t expected_size = (end - start + step - 1) / step;
    s.reserve(expected_size);
    for (T i = start; i < end; i += step) {
        s.insert(i);
    }
}

template <typename T>
void intersect(const std::unordered_set<T>& s1, const std::unordered_set<T>& s2, std::unordered_set<T>& result) {
    // 选择较小的集合遍历，减少查找次数
    const auto& smaller = s1.size() < s2.size() ? s1 : s2;
    const auto& larger = s1.size() < s2.size() ? s2 : s1;
    
    result.reserve(smaller.size()); // 预留结果集空间
    for (const auto& elem : smaller) {
        if (larger.find(elem) != larger.end()) {
            result.insert(elem);
        }
    }
}

int main() {
    std::unordered_set<int64_t> s1;
    std::unordered_set<int64_t> s2;
    std::unordered_set<int64_t> s3;
    
    elapsed(std::bind(fill_set<int64_t>, std::ref(s1), 8, 1000*1000*100, 13), "fill s1 took");
    elapsed(std::bind(fill_set<int64_t>, std::ref(s2), 0, 1000*1000*100, 7), "fill s2 took");
    
    std::cout << "s1 length = " << s1.size() << ", s2 length = " << s2.size() << std::endl;
    elapsed(std::bind(intersect<int64_t>, std::ref(s1), std::ref(s2), std::ref(s3)), "intersect s1 and s2 took");
    std::cout << "s3 length = " << s3.size() << std::endl;
}

4. 编译选项优化 #

确保使用-O3编译，并且尽量使用较新的编译器（比如Clang 14+或GCC 11+），新编译器对哈希表的实现和优化更到位，能进一步提升性能。

三、测试预期 #

用上述优化后的代码，在你的测试环境下，交集操作的时间应该能降到0.2秒以内，甚至比Python的set更快——毕竟C++的哈希表实现没有Python的解释层开销，只要数据结构选对，性能反超是很正常的。

内容的提问来源于stack exchange，提问作者Aleksei Gutikov