python - C++ 中的高效集合并集和交集

Question

给定两个集合 set1 和 set2，我需要通过并集计算它们的交集的比率。到目前为止，我有以下代码:

double ratio(const set<string>& set1, const set<string>& set2)
{
    if( set1.size() == 0 || set2.size() == 0 )
        return 0;

    set<string>::const_iterator iter;
    set<string>::const_iterator iter2;
    set<string> unionset;

    // compute intersection and union
    int len = 0;
    for (iter = set1.begin(); iter != set1.end(); iter++) 
    {
        unionset.insert(*iter);
        if( set2.count(*iter) )
            len++;
    }
    for (iter = set2.begin(); iter != set2.end(); iter++) 
        unionset.insert(*iter);

    return (double)len / (double)unionset.size();   
}

它似乎很慢(我调用该函数大约 300 万次，总是使用不同的集合)。另一方面，对应的 Python 方法要快得多

def ratio(set1, set2):
    if not set1 or not set2:
        return 0
    return len(set1.intersection(set2)) / len(set1.union(set2))

关于如何改进 C++ 版本(可能不使用 Boost)有什么想法吗？

Answer 1

可以在线性时间内完成，无需新内存:

double ratio(const std::set<string>& set1, const std::set<string>& set2)
{
    if (set1.empty() || set2.empty()) {
        return 0.;
    }
    std::set<string>::const_iterator iter1 = set1.begin();
    std::set<string>::const_iterator iter2 = set2.begin();
    int union_len = 0;
    int intersection_len = 0;
    while (iter1 != set1.end() && iter2 != set2.end()) 
    {
        ++union_len;
        if (*iter1 < *iter2) {
            ++iter1;
        } else if (*iter2 < *iter1) {
            ++iter2;
        } else { // *iter1 == *iter2
            ++intersection_len;
            ++iter1;
            ++iter2;
        }
    }
    union_len += std::distance(iter1, set1.end());
    union_len += std::distance(iter2, set2.end());
    return static_cast<double>(intersection_len) / union_len;
}