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

這似乎是很慢（我用不同的組調用3M左右時間功能，總是）。蟒蛇對應，在另一方面，是方式要快得多

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

有關如何改善（可能不使用Boost）的C++版本的任何想法？

Answer 1

您實際上並不需要構造聯合集。在Python中，len(s1.union(s2)) == len(s1) + len(s2) - len(s1.intersection(s2));聯合的大小是s1和s2的大小的總和，減去計數兩次的元素的數量，這是交集中元素的數量。因此，你可以做

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

Answer 2

它可以在線性時間內完成，無需新的內存：

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