刪除子集

Question

假設給出了兩組整數列表。將它們稱爲A和B.A中的每個集合都可以包含在B中的一個集合中。找到A中所有元素的最有效的算法是什麼，使得一組B中不包含任何元素？

Answer 1

要嘗試修剪搜索空間，我們可以嘗試一些檢查和過濾器作爲搜索的一部分。採取在評論你的榜樣，

A = [{1,2},{1,4},{3,4,7}] 
B = [{2,3,4},{1,2,4},{1,2,5,6}]  

開始與中集作爲指向組的交叉關聯索引鍵的獨特元素的O（n）的枚舉它們屬於：

1: A: {0,1}, B: {1,2} 
2: A: {0} , B: {0,1,2} 
3: A: {2} , B: {0} 
4: A: {1,2}, B: {0,1} 
5: A: {} , B: {2} 
6: A: {} , B: {2} 
7: A: {2} , B: {} 

我們可以立即在A中放置包含B中找不到的元素的集合，比如A的第三集合。

現在，我們將遍歷A中未排除的每個集合，並檢查B中是否存在至少一個集合的相應完整交集。由於您的情況下集合索引的數量爲數百萬，而不是最初遍歷整個B，我們將把B的檢查分成幾部分，每部分爲k集合，比如1024.此外，爲了表示這些1024個集合索引，我們將它們分成16個64位的集合我們可能會按位與（和）（&）相互配合。

在此遍歷期間的任何一點，我們從早期的出口中獲益，如果與操作結果爲零：

set A[0] => elements 1,2 => set-index-intersection in B: b110 & b111 => match 
set A[1] => elements 1,4 => set-index-intersection in B: b110 & b11 => match 

總體而言，工作一段一段的，我們在尋找大約10 * 16操作請檢查k B套的當前部分中的一套是否包含A中的一套。換句話說，我們已經將操作次數從10,000,000減少到了160,000，以便完全檢查A中的一組（B中每百萬組）。這是62的一個因子。