如何刪除2組之間不相關的元素？類似於SQL加入

假設我有2臺這樣的：如何刪除2組之間不相關的元素？類似於SQL加入

A = { 1, 4, 7, 10, 11, 12 } 
B = { a, b, x, y, z }

而且我確定如果一個元素在B被與另一功能：

bool isRelated(a, b)

我想刪除來自A和B的元素沒有任何相關元素。我怎樣才能做到這一點？ 1簡單的方法是：

forEach a in A: 
    related = 0 
    forEach b in B: 
     if isRelated(a, b): 
      related++ 
      break 
    if related == 0 
     A.remove(a) 

// then I need to do something similar for B

對我來說看起來效率很低。有沒有更好的辦法？一定會有更好的辦法？

來源

2013-02-22 Jiew Meng

這在時間複雜度上非常類似，但由於linq的懶惰，它可以爲你節省一些。

這是一個C＃示例：

var newA = A.Where(a=> B.Any(b=> IsRelated(a,b)).Select(a); //checks the desired condition 
var newB = B.Where(b=> A.Any(a=> IsRelated(a,b)).Select(b); 
A = newA; 
B = newB'

來源

2013-02-22 08:27:41 Wasafa1

解決了您提及的A＆B類型問題。 – Wasafa1 2013-02-22 08:48:58

沒有一般的更好的方法。 SQL數據庫在它們識別join子句中的特定條件時進行優化，爲此可以使用索引（或者已存在的數據結構或動態構建的數據結構）來查找所有匹配，而不掃描整個集合。並非所有可能的關係都與任何索引有關。

您可以在第一個循環中保留B所有元素的記錄，其中isRelated返回true。然後在尚未編寫的第二個循環中，您可以在循環使用（現在減少的）集合A之前檢查緩存。一旦到位，也許你可能（在第一個循環中）並不總是從一開始就搜索B，以便稍後給出B元素更好的機會進入緩存。

除此之外，我認爲這裏沒有任何大的節省。

來源

2013-02-22 08:27:41

修正了打字錯誤。 – 2013-02-22 08:32:13

如何刪除2組之間不相關的元素？類似於SQL加入

回答

相關問題