सबसेट्स को हटाएं

Question

मान लीजिए कि आपको पूर्णांक के सेट की दो सूचियां दी गई हैं। उन्हें ए और बी बुलाएं। ए में प्रत्येक सेट बी में सेटों में से एक के भीतर निहित किया जा सकता है। ए में सभी तत्वों को खोजने के लिए सबसे कुशल एल्गोरिदम क्या है कि कोई भी बी के सेट में निहित नहीं है?

Answer 1

खोज स्थान को आजमाएं और ट्रिम करने के लिए, हम खोज के हिस्से के रूप में कुछ चेक और फ़िल्टर आज़मा सकते हैं।

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 = [{1,2},{1,4},{3,4,7}] 
B = [{2,3,4},{1,2,4},{1,2,5,6}]  

शुरू टिप्पणी में अपने उदाहरण लेते हैं, वे संबंध रखते हैं

हम तुरंत ए में सेट को अलग कर सकते हैं जिसमें बी में कोई तत्व नहीं मिला है, जैसे कि ए के तीसरे सेट।

अब, हम ए में प्रत्येक सेट को पार करेंगे, जिसे बाहर नहीं रखा गया है और जांचें कि बी में कम से कम एक सेट का एक पूर्ण पूर्ण चौराहे है क्योंकि आपके मामले में सेट-इंडेक्स की संख्या लाखों में है शुरुआती रूप से बी को पूरी तरह से घुमाने के बजाए, हम बी की हमारी परीक्षा को विभाजित करेंगे, k सेटों में से प्रत्येक, 1024 कहें। इसके अलावा, इन 1024 सेट-इंडेक्स का प्रतिनिधित्व करने के लिए, हम उन्हें 64 बिट्स के 16 बिट्स में विभाजित करेंगे हम bitwise-और() एक दूसरे के साथ हो सकता है।

इस ट्रेवर्सल के दौरान किसी भी बिंदु पर, हम एक प्रारंभिक बाहर निकलने से लाभ करता है, तो शून्य में और आपरेशन के परिणाम:

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 आपरेशन करने के लिए देख रहे हैं जांचें कि 0 में से एक सेट k बी-सेट के वर्तमान खंड में सेट में से एक में शामिल है या नहीं। दूसरे शब्दों में, हमने ए में एक सेट (बी में प्रति मिलियन सेट) की पूरी जांच के लिए 10,000,000 से 160,000 तक संचालन की संख्या कम कर दी है। यह 62 का एक कारक है।