एल्गोरिथ्म: सभी सबसेट

Question

समस्या को हटाने के द्वारा सेट के एक समूह विलय करने के लिए एक नक्शा-को कम रास्ता है: मान लीजिए कि हमें समूह के एक समूह है: Set(1,2,3)Set(1,2,3,4)Set(4,5,6)Set(1,2,3,4,6) पर हम पाते हैं सब सबसेट हटा सकते हैं और अंत में करने की जरूरत है परिणाम: Set(4,5,6)Set(1,2,3,4,6)। (Set(1,2,3) और Set(1,2,3,4) दोनों के बाद से Set(1,2,3,4,6) के सबसेट हैं, दोनों निकाल दिए जाते हैं।)

और लगता है कि सेट के तत्वों order है, जो इंट, चार, आदि

हो सकता है यह करने के लिए संभव है यह एक मानचित्र-कम रास्ता में?

मानचित्र में इसे करने का कारण-कम तरीका यह है कि कभी-कभी समूह के समूह का आकार बहुत बड़ा होता है, जिससे एक मशीन की स्मृति में ऐसा करना संभव नहीं होता है। तो हम इसे मानचित्र-कम करने के तरीके में करने की उम्मीद करते हैं, यह बहुत ही कुशल नहीं हो सकता है, बल्कि काम करता है।

मेरे समस्या है:

1. मैं नक्शा-कम करने की प्रक्रिया समूह में कुंजी-मान पेयर के लिए एक महत्वपूर्ण परिभाषित करने के लिए पता नहीं कैसे ठीक से सेट करता है।

2. मुझे नहीं पता कि प्रक्रिया कब समाप्त होनी चाहिए, कि सभी सबसेट हटा दिए गए हैं।

EDIT:

1. डेटा का आकार भविष्य में बड़े बढ़ रही रखेंगे।

2. इनपुट या तो समूह के सेट वाले प्रत्येक पंक्ति के साथ सेट या एकाधिक लाइनों का समूह हो सकता है। वर्तमान में इनपुट val data = RDD[Set] है, मैं सबसे पहले data.collect() करता हूं, जिसके परिणामस्वरूप सेट के कुल समूह में परिणाम होता है। लेकिन मैं RDD[Array[Set]] में इनपुट की पीढ़ी को संशोधित कर सकता हूं, जो मुझे सेट के समूह वाले प्रत्येक पंक्ति के साथ कई लाइनें देगा।

3. प्रत्येक सेट में तत्वों को प्रोग्राम के अन्य हिस्सों को संशोधित करके क्रमबद्ध किया जा सकता है।

Answer 1

मुझे संदेह है कि यह एक पारंपरिक मानचित्र द्वारा किया जा सकता है-तकनीक को कम करें जो अनिवार्य रूप से एक विभाजन और जीत विधि है। ऐसा इसलिए है क्योंकि:

• इस समस्या में प्रत्येक सेट को अनिवार्य रूप से बड़ी कार्डिनालिटी के सभी सेटों की तुलना की जानी चाहिए जिनके न्यूनतम और अधिकतम तत्व न्यूनतम सेट के न्यूनतम और अधिकतम सेट के आसपास हैं।
• सॉर्टिंग और अन्य समस्याओं के विपरीत मानचित्र-कम करने के लिए उपयुक्त, हमारे पास एक पारगमन संबंध नहीं है, यानी A is not-a-subset-of B और B is-not-subset-of C, हम A w.r.t. के बारे में कोई बयान नहीं दे सकते। C।

इस समस्या से ऊपर टिप्पणियों के आधार पर पता लगाने नकल करने समान लगता है और डुप्लिकेट का पता लगाने पर अनुसंधान होता है, उदाहरण के लिए here। इसी तरह की तकनीकें मौजूदा समस्या के लिए अच्छी तरह से काम करेंगी।

Answer 2

चूंकि सबसेट एक ट्रांजिटिव रिलेशनशिप (proof) है, तो आप इसका लाभ उठा सकते हैं और एक पुनरावृत्त एल्गोरिदम तैयार कर सकते हैं जो प्रत्येक पुनरावृत्ति में सबसेट को समाप्त करता है।

मैपर:
स्थानीय सबसेट को खत्म करने और केवल supersets फेंकना

तर्क निम्नलिखित है। कुंजी को प्रत्येक सुपरसेट का पहला तत्व बनने दें।

प्रसारण:
स्थानीय सबसेट को खत्म करने और केवल supersets फेंकना।

आप एक ही तर्क के साथ एक combiner का उपयोग भी कर सकते हैं।

प्रत्येक बार, अंतिम पुनरावृत्ति में, जब तक कि एक बार reducer का उपयोग किया जाता है, reducers की संख्या कम होनी चाहिए। इस तरह, आप शुरुआत से पुनरावृत्तियों की संख्या को परिभाषित कर सकते हैं। जैसे प्रारंभिक रूप से 8 रेड्यूसर सेट करके, और प्रत्येक बार अगली पुनरावृत्ति में उनमें से आधे का उपयोग करके, आपका प्रोग्राम 4 पुनरावृत्तियों (8 reducers, फिर 4, फिर 2 और फिर 1) के बाद समाप्त हो जाएगा। आम तौर पर, यह लॉग इन + 1 पुनरावृत्तियों (लॉग बेस 2) में समाप्त हो जाएगा, जहां n reducers की प्रारंभिक संख्या है, इसलिए n 2 की शक्ति होनी चाहिए और निश्चित रूप से मैपर की संख्या से कम होना चाहिए। यदि यह प्रतिबंधक लगता है, तो आप reducers की संख्या में अधिक कठोर कमी के बारे में सोच सकते हैं (उदा। 1/4, या अधिक से कम)।

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

आप MapReduce v.2 है, तो आप उस तरह ऊपर उल्लिखित तर्क (स्यूडोकोड) को लागू कर सकते हैं:
मैपर:

Set<Set> superSets; 

setup() { 
    superSets = new HashSet<>(); 
}  

map(inputSet){ 
    Set toReplace = null; 
    for (Set superSet : superSets) { 
     if (superSet.contains(inputSet) { 
      return; 
     } 
     if (inputSet.contains(superSet)) { 
      toReplace = superSet; 
      break; 
     }    
    } 
    if (toReplace != null) { 
     superSets.remove(toReplace); 
    } 
    superSets.add(inputSet); 
} 

close() { 
    for (Set superSet : superSets) { 
     context.write(superSet.iterator.next(), superSet); 
    } 
} 

आप एक ही कोड कम करने में और combiner में उपयोग कर सकते हैं ।

अंतिम नोट के रूप में, मुझे संदेह है कि इस तरह की गणना के लिए MapReduce सही वातावरण है। शायद अपाचे स्पार्क, या अपाचे फ्लिंक कुछ बेहतर विकल्प प्रदान करता है।

Answer 3

तो मैं समझता हूँ:

• अपने लक्ष्य का पता लगाने और सेट के एक बड़े सेट

• वहाँ भी सेट कर रहे हैं पूरी तरह से प्रबंधित किया जा करने के लिए सेट के सबसेट को दूर करने के लिए है (स्मृति सीमा)

• रणनीति नक्शा और कम करने (या के कुछ तरह)

है

क्या मैं ध्यान में रखना:

• मुख्य समस्या यह है कि आप कामयाब नहीं कर सकते हैं एक ही समय में सब कुछ है

• सामान्य विधि नक्शा/datas विभाजित करने के लिए supposes कम करने, और प्रत्येक का इलाज अंश। यह पूरी तरह से की तरह नहीं किया जाता है (क्योंकि प्रत्येक सबसेट प्रत्येक सबसेट के साथ छेड़छाड़ कर सकता है)।

अगर मैं कुछ गणना करते हैं:

• मान लीजिए आप एक बड़े सेट है: 1 से 3 से 20 नंबर के 1000 000 100 करने के लिए आप सेट
के 1000 अरबों जोड़ों की तुलना करने होनी चाहिए

100 000 (10 अरब) के साथ भी, इसमें बहुत अधिक समय लगता है (मैंने रोका)।

मैं क्या प्रस्ताव (100 000 सेट के साथ परीक्षण):

1 अधिक छोटे संगत सेटों में विभाजित करने के लिए एक कसौटी परिभाषित करते हैं।संगत सेट सेट के पैकेज हैं, और आप सुनिश्चित हैं कि सेट के सबसेट कम से कम एक समान पैकेज में हैं: तो आप उस विधि से निकालने के लिए सबसेट ढूंढने के लिए निश्चित हैं। अलग-अलग कहें: यदि सेट ए सेट बी का सबसेट है, तो ए और बी इस तरह के एक (या कई) पैकेज में रहेंगे।

मैं बस लेता हूं: प्रत्येक सबसेट जिसमें एक परिभाषित तत्व (1, 2, 3, ...) => होता है, यह लगभग अनुमानों के साथ लगभग 11 500 सेट देता है। तुलना करना उचित हो गया है (120 000 तुलना)। मेरी मशीन पर 180 सेकंड लगते हैं, और इसे हटाने के लिए 900 सबसेट मिलते हैं।

• आपको इसे 100 बार (फिर 18 000 सेकंड) करना है।

• और निश्चित रूप से, आप डुप्लिकेट पा सकते हैं (लेकिन बहुत अधिक नहीं: कुछ%, और गोल को खत्म करना है)।

2 अंत में यह agglomerate के लिए आसान और तेज़ है। डुप्लिकेट काम हल्का है।

3 बड़ा फिल्टर:

2 तत्वों के साथ एक फिल्टर के साथ

, आप 1475 सेट करने के लिए कम कर => आप हटाना लगभग 30 सेट मिलता है, इसे 2-3 सेकंड

लेता है और आप के लिए है करना है कि इस विधि से 10 000

रुचि:

• मानदंड पर सेट का चयन रैखिक और बहुत सरल है। यह भी हार्दिक है: एक तत्व पर, एक दूसरे पर विभाजित, आदि

• यह स्टेटलेस है: आप लाखों सेट फ़िल्टर कर सकते हैं। आपको केवल अच्छा रखना है। आपके पास जितने अधिक डेटा हैं, आपको जितना अधिक फ़िल्टर करना है => समाधान स्केलेबल है।

• अगर आप थोड़ा बादलों का इलाज करना चाहते हैं, आप कर सकते हैं 3, आम में 4 तत्वों, आदि

• ऐसे ही लेता है, आप (यदि आपके पास के रूप में कई के रूप में) एक से अधिक मशीनों के बीच अपने इलाज फैल सकता है।

अंत में, आपको अपने सभी डेटा/हटाना को सुलझाना होगा।

यह समाधान कुल मिलाकर बहुत समय नहीं रखता है (आप गणना कर सकते हैं), लेकिन यह काम को विभाजित करने की आवश्यकता के अनुरूप है।

उम्मीद है कि यह मदद करता है।