स्ट्रिंग्स

Question

के सेटों की परिवर्तनीय संख्या के चौराहे को कुशलता से ढूंढने के लिए मेरे पास एररेलिस्ट की एक चर संख्या है जिसे मुझे छेड़छाड़ की आवश्यकता है। तारों के सेट की संख्या पर एक यथार्थवादी टोपी शायद 35 के आसपास है लेकिन अधिक हो सकती है। मुझे कोई कोड नहीं चाहिए, केवल विचार क्या हो सकता है कि कुशल हो सकता है। मेरे पास एक कार्यान्वयन है कि मैं कोडिंग शुरू करने वाला हूं लेकिन कुछ अन्य विचार सुनना चाहता हूं।

वर्तमान में, बस मेरे समाधान के बारे में सोचते हुए, ऐसा लगता है कि मुझे Θ (एन) के एसिम्प्टोटिक रन-टाइम होना चाहिए।

किसी भी मदद के लिए धन्यवाद!

tshred

संपादित करें: स्पष्ट करने के लिए, मैं वास्तव में सिर्फ जानना चाहता हूँ वहाँ यह करने के लिए एक तेजी से रास्ता है। Θ से अधिक तेज़ (एन)।

Answer 1

Set.retainAll() यह है कि आप दो सेटों के चौराहे को कैसे पाते हैं। यदि आप HashSet का उपयोग करते हैं, तो अपने ArrayList से Set एस में कनवर्ट करना और उन सभी पर लूप में retainAll() का उपयोग करना वास्तव में ओ (एन) है।

Answer 2

उन्हें क्रमबद्ध करें (एन एलजी एन) और फिर द्विआधारी खोज (एलजी एन) करें।

Answer 3

सबसे अच्छा विकल्प हैशसेट का उपयोग इन सूचियों की सामग्री को ArrayList के बजाय स्टोर करने के लिए करना होगा। यदि आप ऐसा कर सकते हैं, तो आप एक अस्थायी हैशसेट बना सकते हैं जिसमें आप तत्वों को छेड़छाड़ करने के लिए जोड़ते हैं (putAll (..) विधि का उपयोग करें)। TempSet.retainAll (संग्रहितसेट) करें और tempSet में छेड़छाड़ होगी।

Answer 4

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

Answer 5

आप सिंगल हैशसेट का उपयोग कर सकते हैं। जब वस्तु ऑब्जेक्ट सेट में क्षीण होती है तो यह जोड़() विधि झूठी होती है। सूचियों से ऑब्जेक्ट्स जोड़ने और झूठी वापसी मानों की अंकन संख्या आपको हिस्टोग्राम के लिए सेट + डेटा में संघ प्रदान करेगी (और ऑब्जेक्ट्स जो सूची गणना के बराबर + 1 गिनती हैं, आपके चौराहे हैं)। यदि आप ट्रीसेट पर गिनती फेंकते हैं, तो आप जल्दी छेड़छाड़ का पता लगा सकते हैं।

Answer 6

Google Guava में स्थिर विधि Sets.intersection(set1, set2) भी है जो दो सेटों के चौराहे के एक अप्रचलित दृश्य देता है।

Answer 7

स्वीकृत उत्तर ठीक है; एक अद्यतन के रूप में: जावा 8 के बाद से दो Set एस के चौराहे को खोजने के लिए थोड़ा और अधिक प्रभावी तरीका है।

Set<String> intersection = set1.stream() 
    .filter(set2::contains) 
    .collect(Collectors.toSet()); 

कारण यह थोड़ा और अधिक कुशल है, क्योंकि मूल दृष्टिकोण set1 के तत्वों को जोड़ने के लिए किया था यह तो फिर दूर करने के लिए यदि वे set2 में नहीं थे पड़ा है। यह दृष्टिकोण केवल परिणाम सेट में जोड़ता है कि वहां क्या होना चाहिए।

कड़ाई से बोलते हुए आप यह पूर्व जावा 8 भी कर सकते हैं, लेकिन बिना Stream एस कोड काफी अधिक श्रमिक होता।

यदि दोनों सेट आकार में काफी भिन्न हैं, तो आप छोटे से स्ट्रीमिंग करना पसंद करेंगे।