尋找對集，因此他們的結合具有特定大小

我有一個像後續的變量：尋找對集，因此他們的結合具有特定大小

var L_s = collection.mutable.Set[collection.mutable.Set[Int]]()

，我想找到的套不同尺寸的結合。

請注意：當我們想要找到大小爲k的聯合時，L_s中的所有集合將具有相同的大小，即k-1。

截至目前，我做了以下內容：

for(i <- L_s){ 
for (j <- L_s){ 
    if((i.union(j)).size == k) 
     { 
     res.+=(i.union(j)) 
     } 
    } 
    }

此操作採取了很多的時間，如果L_s擁有多臺套。我想知道做這個操作最有效的方法是什麼。

來源

2017-02-28 user2175104

我們應該瞭解的套件還有其他特徵嗎？是否有關於這些集合的元素的知識，即與「k」有關的總共有多少個不同元素？理論上所有集合都有不同的元素，即它們完全不相交？ – lex82

不，只有我提到的是，當我們想要找到k的聯合時，L_s中的所有集合將具有相同的大小，即k-1。所以如果我可以刪除任何多餘的計算，我發佈的方法會幫助加快我的算法。我目前正在處理的問題會產生很多集合。我正在努力降低這個數字。我認爲套數是緩慢的根本原因。 – user2175104

由於union是可交換（a union b == b union a）需要你做的兩倍多操作，當發現目標大小你又重複union操作，每一個Set得到union自身。這些低效率可以消除。

L_s.toVector.combinations(2).map(x => x(0) union x(1)).filter(_.size == k).toSet

來源

2017-02-28 10:13:27 jwvh

此解決方案正在提取結果。但時間幾乎相同。我可能不得不優化我的代碼的其他部分。我試圖找到頻繁的項目集。我會找到一種方法來減少我的L_s變量中的集合數。這可能有助於加速代碼。 – user2175104

確實。工作量與L_s的大小相關。任何可以做到的事情都會有很大的回報。 – jwvh

基本上有加快你的算法兩個機會：

加快兩套
比較單一，減少所需的比較總數

與之相比，我的意思是檢查兩組的聯合是否大小爲k。

第一個是比較簡單的部分，我在之前的回答中提到過。您不必實際計算聯合並檢查其大小。知道交叉口的大小就足夠了（不是實際的交叉口，只是它的大小）。運行第一組元素並計算第二組中出現的次數（非常高效的查找）。如果十字路口的尺寸爲k - 2，您發現一對符合您的要求。每當發現兩個元素不在第二個集合中時，您應該打破循環，因爲您從此不會達到交集尺寸k - 2。

這是有效的，因爲具有所需屬性的兩個集合除了每個集合中都有一個共同的所有元素。這意味着集合1只有一個元素不在集合2中，反之亦然。

您也可以利用此屬性來限制比較次數。這個想法如下。你的集合包含可以訂購的整數。如果一對集合合格，並且您只考慮每個集合的最低兩個整數，那麼我們稱之爲前綴，前綴至少有一個共同的整數。其他任何東西都會違反你的要求。

您現在可以提前將所有集合的最低和最低整數索引。也就是說，你建立了兩個Map[Int, Set[Set[Int]]類型的地圖，我們稱它們爲setsByLowestMember和setsBySecondLowestMember。當您循環測試所有集合時，不是針對其他集合測試集合，而只是針對具有最低或最低成員等於當前集合的最低或最低值的那些集合進行測試。

示例：正在考慮的當前（有序）集是{ 3, 7, 9, ...}。您檢查所有setsByLowestMember(3),setsByLowestMember(7),setsBySecondLowestMember(3)和setsBySecondLowestMember(7)。

根據您的數據，這可能會顯着加快您的算法。但是，如果您的套件總體上具有非常大的交叉點，則可能沒有多大幫助。如果有幫助，可以進一步改進（使用上述方法，仍然會執行兩次檢查）。

來源

2017-03-01 10:40:31 lex82

尋找對集，因此他們的結合具有特定大小

回答

相關問題