जावा में 2 मर्ज 2 संग्रह (1)

Question

मुझे 2 बड़े संग्रहों को 1 में विलय करने में सक्षम होना चाहिए। मैं किस संग्रह प्रकार का सर्वोत्तम उपयोग कर सकता हूं? मुझे व्यक्तिगत तत्वों के लिए यादृच्छिक पहुंच की आवश्यकता नहीं है। आम तौर पर मैं एक लिंक्डलिस्ट के लिए जाऊंगा, हालांकि मैं ओ (1) के रनटाइम के साथ जावा में 2 लिंक्डलिस्ट को मर्ज नहीं कर सकता, जो कई अन्य भाषाओं में किया जा सकता है, क्योंकि मुझे प्रत्येक तत्व को नई सूची में कॉपी करना होगा ।

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

Answer 1

आप (1) Guava के Iterables.concat तरीकों में से एक का उपयोग कर हे में एक concatenated Iterable दृश्य बना सकते हैं:

Iterable<T> combined = Iterables.concat(list1, list2); 

यह आपको नकल के बिना एक वस्तु के रूप में भर में दोनों सूचियों के तत्वों पुनरावृति करने की अनुमति देगा कोई तत्व

Answer 2

सिद्धांत रूप में, आप ओ (1) में 2 लिंक्ड सूचियों को मर्ज कर सकते हैं, क्योंकि आपको केवल दूसरे के पहले नोड के पहले नोड को इंगित करना है (माना जाता है कि आपके पास ये संदर्भ हैं)।

addAll संग्रह की विधि ओ (एन) के चलने का समय प्रतीत होता है, क्योंकि वे इटरेटर के बारे में बात कर रहे हैं। विवरण JVM विशिष्ट हो सकता है ...

मुझे नहीं लगता कि कोई संग्रह है जो ओ (एन) में गठबंधन होगा। आपको अपना खुद का रोल करना पड़ सकता है।

Answer 3

यहां सबसे सरल समाधान वास्तव में सूची की सूची है। इसका मतलब है कि आपको कुछ सरल रैपर फ़ंक्शंस चाहिए, लेकिन कुछ भी जटिल नहीं है।

Answer 4

मुझे लगता है कि सूची का कार्यान्वयन करना सबसे अच्छा होगा, जो सूची> इसके तर्कों के रूप में, और उसके बाद प्रतिनिधियों को लेता है। दूसरे शब्दों में, सूचियों की एक सूची है, और उन्हें एक सूची के रूप में कार्य करने के लिए तार। जब आप सूची 1 के तत्वों से पहले जाते हैं, तो आप सूची 2 को देखना शुरू करते हैं।

किसी कारण से, मैंने सोचा कि अमरूद की ऐसी सूची थी। लेकिन मैं इसे अपने जावडॉक्स में नहीं ढूंढ सकता।

Answer 5

विलय लिंक्ड सूचियां वास्तव में ओ (1) है, और आप सरणी-आधारित सूचियों को उसी तरह मान सकते हैं, यानी कई ऑब्जेक्ट [] के बीच जुड़े हुए हैं।

ऊपर के कार्यान्वयन हैं, यह मध्य/प्रारंभ से हटाने/डालने पर ArrayList से तेज़ है। और पुनरावृत्ति वस्तुतः वही है। हालांकि यादृच्छिक पहुंच थोड़ी धीमी हो सकती है।

Answer 6

मैं apache.commons से CompositeCollection कक्षा का सुझाव देना चाहता था, लेकिन source code पर यह ओ (एन) में भी चलता है। यदि आपको केवल तत्वों पर पुन: प्रयास करने की आवश्यकता है और कॉलिनडी द्वारा सुझाए गए Google संग्रह का उपयोग नहीं करना चाहते हैं, तो आप आसानी से अपना स्वयं का समग्र इटरेटर बना सकते हैं, उदा।

public class CompositeCollectionIterator<T> implements Iterator<T>{ 

    private Iterator<T>[] iterators; 
    private int currentIteratorIndex = 0; 
    public CompositeCollectionIterator(Collection<T>... aCollections) { 
    iterators = new Iterator[ aCollections.length]; 
    for (int i = 0, aCollectionsLength = aCollections.length; i < aCollectionsLength; i++) { 
     Collection<T> collection = aCollections[ i ]; 
     iterators[i] = collection.iterator(); 
    } 
    } 

    public boolean hasNext() { 
    if (iterators[currentIteratorIndex].hasNext()) return true; 
    else if (currentIteratorIndex < iterators.length - 1){ 
     currentIteratorIndex++; 
     return hasNext(); 
    } 
    return false; 
    } 

    public T next() { 
    return iterators[currentIteratorIndex].next(); 
    } 

    public void remove() { 
    iterators[currentIteratorIndex].remove(); 
    } 
} 

Answer 7

आप सिर्फ वस्तुओं का संग्रह है और (1) समय उन्हें हे में मर्ज करना चाहते हैं, और अपने खुद के डेटा संरचना को लागू करने से परहेज नहीं करते हैं, तो यह करने के लिए तो सबसे आसान तरीका एक का उपयोग करने के लिए है असंतुलित बाइनरी पेड़: प्रत्येक नोड या तो एक पत्ता होता है (एक मूल्य भंडारित करता है) या दो पेड़ों का संयोजन होता है, और आप इन्हें केवल दो वर्गों के रूप में एक अमूर्त सुपरक्लास या इंटरफ़ेस के साथ कार्यान्वित कर सकते हैं। तत्वों को निकालने के लिए एक गहराई-पहला ट्रैवर्सल का उपयोग किया जा सकता है।

यह अनिवार्य रूप से कॉलर डी के इटेटरेटर कॉन्सटेनेशन के सुझाव के समान ही है, लेकिन अधिक नंगे हड्डियों।

पकड़ है कि इस संग्रह से अधिक पुनरावृत्ति हे नहीं जाएगा ( n)! यह ओ ( एन + एम) जहां एम आपके द्वारा किए गए विलयों की संख्या है (क्योंकि प्रत्येक एक ट्रैवर्स होने के लिए एक नोड है)। यह मेरे समाधान और कॉलिनडी दोनों के सच है। मुझे नहीं पता कि यह इस समस्या के सभी संभावित समाधानों के लिए सच है या नहीं।

उपरोक्त को कभी भी ध्यान न दें। इस योजना के तहत, प्रत्येक विलय कम से कम एक तत्व जोड़ता है, इसलिए एम < एन और इसलिए पुनरावृत्ति लागत अभी भी ओ (एन) है। (आप इटरेटर संयोजन का उपयोग करते हैं, तो सुनिश्चित करें कि आप अक्सर कि के रूप में खाली iterators श्रृंखलाबद्ध लागत जोड़ना होगा नहीं कर रहे हैं।)

Answer 8

के पहले और पिछले तत्व की ओर इशारा अपने संग्रह के रूप में दोनों आपस में जुड़े सूचियों का उपयोग कर, और भंडारण तक प्रत्येक सूची (दोनों पॉइंटर्स संभावित रूप से वस्तुओं को जोड़ने/हटाने के दौरान अद्यतन होने की आवश्यकता होगी), आप ओ (1) में दोनों सूचियों को मर्ज कर सकते हैं - दूसरी सूची के पहले तत्व को केवल पहली सूची के अंतिम तत्व को कनेक्ट करें, और समायोजित करें तदनुसार पहले/अंतिम पॉइंटर्स।

मुझे डर है कि आपको जावा में लिंक्ड सूचियों के अपने कार्यान्वयन को रोल करने की आवश्यकता होगी, क्योंकि आपके पास LinkedList के अंतर्निहित नोड्स तक सीधे पहुंच नहीं है, और इसलिए आप अंतिम तत्व को कनेक्ट नहीं कर सकते दूसरी सूची के पहले तत्व के लिए पहली सूची।

सौभाग्य से, जावा में लिंक किए गए सूची कार्यान्वयन को ढूंढना आसान है, क्योंकि यह डेटा संरचना पाठ्यक्रमों में एक बहुत ही आम विषय है। उदाहरण के लिए, here एक है - मुझे पता है, नाम स्पेनिश में हैं, लेकिन ListaEncadenada ("लिंक्डलिस्ट") और NodoLista ("ListNode") में कोड काफी सरल है और स्वयं स्पष्टीकरण होना चाहिए, और सबसे महत्वपूर्ण बात यह है कि कार्यान्वयन में शामिल है सूची के पहले और अंतिम तत्वों के लिए पॉइंटर्स, और आपकी आवश्यकताओं के अनुरूप आसानी से संशोधित किया जा सकता है।