查找組合對之間共享元素的最佳方式

Question

我有一個A型訂購商品的列表，每個商品都包含一個來自商品列表B的子集。對於A中的每一對商品，我想找到數字他們分享的項目B（相交）。

舉例來說，如果我有這樣的數據：

A1 : B1 
A2 : B1 B2 B3 
A3 : B1 

然後我會得到以下結果：

A1, A2 : 1 
A1, A3 : 1 
A2, A3 : 1 

我遇到的問題是使得算法效率。我的數據集的大小約爲8.4K類型的項目。這意味着8.4K選擇2 = 35275800組合。我正在使用的算法是簡單地通過每個組合對和做一組交集。

我到目前爲止的要點在下面。我將計數存儲爲地圖中的一個關鍵字，並將該值作爲A對的向量。我正在使用圖形數據結構來存儲數據，但我使用的唯一'圖形'操作是get_neighbors（），它從A返回項目的B子集。我碰巧知道圖形中的元素是從索引0到8.4K排序。

void get_overlap(Graph& g, map<int, vector<A_pair> >& overlap) { 

map<int, vector<A_pair> >::iterator it; 

EdgeList el_i, el_j; 
set<int> intersect; 

size_t i, j; 

VertexList vl = g.vertices(); 

for (i = 0; i < vl.size()-1; i++) { 
    el_i = g.get_neighbors(i); 

    for (j = i+1; j < vl.size(); j++) { 
     el_j = g.get_neighbors(j); 

     set_intersection(el_i.begin(), el_i.end(), el_j.begin(), el_j.end(), inserter(intersect, intersect.begin())); 
     int num_overlap = intersect.size(); 

     it = overlap.find(num_overlap); 
     if (it == overlap.end()) { 
      vector<A_pair> temp; 
      temp.push_back(A_pair(i, j)); 
      overlap.insert(pair<int, vector<A_pair> >(num_overlap, temp)); 
     } 
     else { 
      vector<A_pair> temp = it->second; 
      temp.push_back(A_pair(i, j)); 
      overlap[num_overlap] = temp; 
     } 
    } 
} 

}

我一直在運行這個程序了近24小時，for循環中的第i個元素已經達到迭代250（我打印每個我到一個日誌文件）。當然，這距離8.4K還有很長的路要走（儘管我知道隨着迭代的進行，從j = i + 1開始，比較次數會縮短）。有沒有更優化的方法？

編輯：爲了清楚起見，這裏的目標是最終找到最重要的k個重疊對。

編輯2：感謝@Beta和其他人指出優化。特別是，直接更新地圖（而不是複製其內容並重新設置地圖值）大大提高了性能。它現在在幾秒鐘內運行。

Answer 1

我想你可以通過預先計算一個反向（邊到頂）映射來使事情更快。這可以讓你避免set_intersection調用，它會執行一堆昂貴的插入操作。我錯過了一些聲明來完成功能完整的代碼，但希望你能明白這一點。我假設EdgeList都爲某種INT載體：

void get_overlap(Graph& g, map<int, vector<A_pair> >& overlap) { 

map<int, vector<A_pair> >::iterator it; 



EdgeList el_i, el_j; 
set<int> intersect; 

size_t i, j; 

VertexList vl = g.vertices(); 

// compute reverse map 
map<int, set<int>> reverseMap; 
for (i = 0; i < vl.size()-1; i++) { 
    el_i = g.get_neighbors(i); 
    for (auto e : el_i) { 
     const auto findIt = reverseMap.find(e); 
     if (end(reverseMap) == findIt) { 
      reverseMap.emplace(e, set<int>({i}))); 
     } else { 
      findIt->second.insert(i); 
     } 
    } 
} 

for (i = 0; i < vl.size()-1; i++) { 
    el_i = g.get_neighbors(i); 

    for (j = i+1; j < vl.size(); j++) { 
     el_j = g.get_neighbors(j); 

     int num_overlap = 0; 
     for (auto e: el_i) { 
      auto findIt = reverseMap.find(e); 
      if (end(reverseMap) != findIt) { 
       if (findIt->second.count(j) > 0) { 
        ++num_overlap; 
       } 
      } 
     } 

     it = overlap.find(num_overlap); 
     if (it == overlap.end()) { 
      overlap.emplace(num_overlap, vector<A_pair>({ A_pair(i, j) })); 
     } 
     else { 
      it->second.push_back(A_pair(i,j)); 
     } 
    } 
} 

我沒有做精確的性能分析，但雙循環內部，替換「在最4N比較」 +一些昂貴的一套插入（從，N * log（M）* log（E）比較，其中N是每個頂點的平均邊數，M是每邊的平均頂點數，E是邊的數量，所以它可以是取決於您的數據集。 另外，如果您的邊緣索引是緊湊的，那麼您可以使用simplae矢量而不是地圖來表示反轉地圖，從而消除了日誌（E）性能成本。

但有一個問題。既然你說的是頂點和邊，那麼你是否還有額外的約束：邊總是有2個頂點？這可以簡化一些計算。