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();   
}

它似乎很慢（我调用函数大约3百万次，总是使用不同的设置）。另一方面，python的对应版本要快得多

^{pr2}$ 关于如何改进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;
}

Answer 2

实际上不需要构造联合集。在Python术语中，len(s1.union(s2)) == len(s1) + len(s2) - len(s1.intersection(s2))；并集的大小是s1和{}的大小之和，减去两次计数的元素数，即交集中的元素数。这样，你就能做到

for (const string &s : set1) {
    len += set2.count(s);
}
return ((double) len) / (set1.size() + set2.size() - len)