जावा कोड समीक्षा: क्रमबद्ध सूचियों को एक क्रमबद्ध सूची में मर्ज करें

Question

मैं क्रमबद्ध सूचियों को एक सूची में विलय करना चाहता हूं। यह समाधान कैसा है? मेरा मानना ​​है कि यह ओ (एन) समय में चलता है। कोई चमकदार त्रुटियां, अक्षमता, या स्टाइलिस्ट मुद्दों?

मुझे वास्तव में "यह पहला पुनरावृत्ति" के लिए ध्वज स्थापित करने की मुहावरे पसंद नहीं है और यह सुनिश्चित करने के लिए "निम्नतम" का डिफ़ॉल्ट मान है। क्या इसके चारों ओर एक बेहतर तरीका है?

public static <T extends Comparable<? super T>> List<T> merge(Set<List<T>> lists) { 
    List<T> result = new ArrayList<T>(); 

    int totalSize = 0; // every element in the set 
    for (List<T> l : lists) { 
     totalSize += l.size(); 
    } 

    boolean first; //awkward 
    List<T> lowest = lists.iterator().next(); // the list with the lowest item to add 

    while (result.size() < totalSize) { // while we still have something to add 
     first = true; 

     for (List<T> l : lists) { 
      if (! l.isEmpty()) { 
       if (first) { 
        lowest = l; 
        first = false; 
       } 
       else if (l.get(0).compareTo(lowest.get(0)) <= 0) { 
        lowest = l; 
       } 
      } 
     } 
     result.add(lowest.get(0)); 
     lowest.remove(0); 
    } 
    return result; 
} 

नोट: यह होमवर्क नहीं है, लेकिन यह उत्पादन कोड के लिए नहीं है।

Answer 1

आपका समाधान शायद सबसे तेज़ है। सॉर्ट किए गए सूची में लॉग (एन) की एक सम्मिलित लागत होती है, इसलिए आप एम लॉग (एम) (जहां एम सूचियों का कुल आकार है) के साथ समाप्त हो जाएगा।

उन्हें एक सूची और सॉर्टिंग में जोड़ना, पढ़ने के लिए आसान, अभी भी एम लॉग (एम) है।

आपका समाधान सिर्फ एम

आप अपने कोड साफ कर सकते हैं परिणाम सूची आकार से थोड़ा है, और एक बूलियन के बजाय न्यूनतम सूची के लिए एक संदर्भ का उपयोग करना है।

public static <T extends Comparable<? super T>> List<T> merge(Set<List<T>> lists) { 
    int totalSize = 0; // every element in the set 
    for (List<T> l : lists) { 
     totalSize += l.size(); 
    } 

    List<T> result = new ArrayList<T>(totalSize); 

    List<T> lowest; 

    while (result.size() < totalSize) { // while we still have something to add 
     lowest = null; 

     for (List<T> l : lists) { 
      if (! l.isEmpty()) { 
       if (lowest == null) { 
        lowest = l; 
       } else if (l.get(0).compareTo(lowest.get(0)) <= 0) { 
        lowest = l; 
       } 
      } 
     } 

     result.add(lowest.get(0)); 
     lowest.remove(0); 
    } 

    return result; 
} 

तुम सच में विशेष रूप से कर रहे हैं, इनपुट के रूप में एक सूची वस्तु का उपयोग करें, और सबसे कम lists.get जा करने के लिए (0) प्रारंभ किया जा सकता है और आप अशक्त जांच छोड़ सकते हैं।

Answer 2

एंटोन की टिप्पणी पर विस्तार करने के लिए:

, एक संकेतक whch की सूची यह है के साथ एक सूची से नवीनतम परिणाम रखकर एक ढेर में साथ रखकर तो लगातार ऊपर से ढेर लेते हैं, और एक नया डाल आपके द्वारा अभी ली गई वस्तु से संबंधित सूची से ढेर पर आइटम।

जावा की प्राथमिकता क्यूई हीप कार्यान्वयन प्रदान कर सकती है।

Answer 3

क्षमता चूसना जाएगा अगर lists एक ArrayList होता है, के बाद से lowest.remove(0) सूची की लंबाई में रेखीय समय लगेगा, अपने एल्गोरिथ्म हे बनाने (एन^2)।

मुझे क्या करना चाहते हैं:

List<T> result = new ArrayList<T>(); 
for (List<T> list : lists) { 
    result.addAll(list); 
} 
Collections.sort(result); 

जो हे में है (एन एन लॉग इन करें), और परीक्षण, डिबग और बनाए रखने के लिए अब तक कम थकाऊ कोड छोड़ देता है।

Answer 4

चूंकि बलुस और मेरिटॉन ने एल्गोरिदम के बारे में आपके प्रश्न के लिए एक उत्कृष्ट प्रतिक्रिया दी है, इसलिए मैं आपके "पहले" मुहावरे के बारे में बात करूंगा।

निश्चित रूप से अन्य दृष्टिकोण हैं (जैसे 'जादू' मूल्य को सबसे कम सेट करना), लेकिन मुझे लगता है कि "पहला" (जिसके लिए मैं शायद लंबा नाम दूंगा, लेकिन यह पैडेंटिक है) सर्वश्रेष्ठ है , क्योंकि यह बहुत स्पष्ट है। "पहले" जैसे बूलियन की उपस्थिति एक स्पष्ट संकेत है कि आपका लूप पहली बार कुछ खास करेगा। यह पाठक की मदद करता है।

बेशक आपको इसकी आवश्यकता नहीं है यदि आप बलस/मेरिटॉन दृष्टिकोण लेते हैं, लेकिन यह एक ऐसी स्थिति है जो फसलों को उठाती है।

Answer 5

यह वास्तव में एक पुराना सवाल है, लेकिन मुझे सबमिट किए गए उत्तरों में से कोई भी पसंद नहीं है, इसलिए मैं यही कर रहा हूं।

लॉग इन रैखिक जटिलता के कारण उन्हें केवल एक सूची में जोड़ने और सॉर्ट करने का समाधान खराब है।यदि यह आपके लिए महत्वपूर्ण नहीं है, तो यह निश्चित रूप से सबसे सरल और सबसे सरल उत्तर है। आपका प्रारंभिक समाधान खराब नहीं है, लेकिन यह थोड़ा गन्दा है, और @ डाथन ने बताया कि जटिलता ओ (एम एन) एम सूचियों और एन तत्वों के लिए है। आप इसे एक ढेर का उपयोग करके ओ (एन लॉग (एम)) में कम कर सकते हैं ताकि प्रत्येक तत्व के लिए तुलना की संख्या को कम किया जा सके। मैं एक सहायक वर्ग का उपयोग करता हूं जो मुझे पुनरावृत्तियों की तुलना करने की अनुमति देता है। इस तरह से मैं प्रारंभिक सूचियों को नष्ट नहीं करता हूं, और इसे उचित जटिलता के साथ संचालित करना चाहिए इससे कोई फर्क नहीं पड़ता कि किस प्रकार की सूचियां इनपुट हैं। नीचे दिए गए कार्यान्वयन के साथ मैं देखता हूं कि एकमात्र दोष यह है कि यह null तत्वों के साथ सूचियों का समर्थन नहीं करता है, हालांकि वांछित होने पर इसे ठीक किया जा सकता है।

public static <E extends Comparable<? super E>> List<E> merge(Collection<? extends List<? extends E>> lists) { 
    PriorityQueue<CompIterator<E>> queue = new PriorityQueue<CompIterator<E>>(); 
    for (List<? extends E> list : lists) 
     if (!list.isEmpty()) 
      queue.add(new CompIterator<E>(list.iterator())); 

    List<E> merged = new ArrayList<E>(); 
    while (!queue.isEmpty()) { 
     CompIterator<E> next = queue.remove(); 
     merged.add(next.next()); 
     if (next.hasNext()) 
      queue.add(next); 
    } 
    return merged; 
} 

private static class CompIterator<E extends Comparable<? super E>> implements Iterator<E>, Comparable<CompIterator<E>> { 
    E peekElem; 
    Iterator<? extends E> it; 

    public CompIterator(Iterator<? extends E> it) { 
     this.it = it; 
     if (it.hasNext()) peekElem = it.next(); 
     else peekElem = null; 
    } 

    @Override 
    public boolean hasNext() { 
     return peekElem != null; 
    } 

    @Override 
    public E next() { 
     E ret = peekElem; 
     if (it.hasNext()) peekElem = it.next(); 
     else peekElem = null; 
     return ret; 
    } 

    @Override 
    public void remove() { 
     throw new UnsupportedOperationException(); 
    } 

    @Override 
    public int compareTo(CompIterator<E> o) { 
     if (peekElem == null) return 1; 
     else return peekElem.compareTo(o.peekElem); 
    } 

} 

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