सूचियों को संयोजित करने का एक प्रभावी तरीका क्या है?

Question

जब हमारे पास दो सूचियां a और b हैं, तो एक कुशल सूची में एक नई सूची में उन दोनों को एकसाथ (ऑर्डर प्रासंगिक नहीं) कैसे जोड़ सकता है?

यदि a ::: b और a ++ b कुशल हैं तो मुझे स्कैला एपीआई से पता नहीं लगा सका। शायद मुझे कुछ याद आया।

Answer 1

स्काला 2.9 में, ::: के लिए कोड (सूची आगे जोड़ते) इस प्रकार है:

def :::[B >: A](prefix: List[B]): List[B] = 
    if (isEmpty) prefix 
    else (new ListBuffer[B] ++= prefix).prependToList(this) 

जबकि ++, अधिक सामान्य है, क्योंकि यह एक CanBuildFrom पैरामीटर लेता है, यानी यह एक संग्रह प्रकार से अलग लौट सकते हैं List:

override def ++[B >: A, That](that: GenTraversableOnce[B])(implicit bf: CanBuildFrom[List[A], B, That]): That = { 
    val b = bf(this) 
    if (b.isInstanceOf[ListBuffer[_]]) (this ::: that.seq.toList).asInstanceOf[That] 
    else super.++(that) 
} 

इसलिए यदि आपके वापसी प्रकार List है, दो समान प्रदर्शन करते हैं।

ListBuffer एक चालाक तंत्र है जिसमें इसे एक उत्परिवर्तक निर्माता के रूप में उपयोग किया जा सकता है, लेकिन अंत में toList विधि द्वारा "उपभोग" किया जाता है। तो (new ListBuffer[B] ++= prefix).prependToList(this) करता है, पहले अनुक्रमिक रूप से prefix (उदाहरण a में) में सभी तत्वों को जोड़ते हैं, ओ (| ए |) समय लेते हैं। इसके बाद prependToList पर कॉल किया जाता है, जो स्थिर समय ऑपरेशन (रिसीवर, या b, अलग करने की आवश्यकता नहीं है)। इसलिए, कुल समय ओ (| ए |) है।

Otherhand पर, के रूप में pst ने बताया, हम reverse_::: है:

def reverse_:::[B >: A](prefix: List[B]): List[B] = { 
    var these: List[B] = this 
    var pres = prefix 
    while (!pres.isEmpty) { 
    these = pres.head :: these 
    pres = pres.tail 
    } 
    these 
} 

a reverse_::: b साथ

तो, यह फिर से हे लेता है (| एक |), इसलिए कोई कम या ज्यादा कुशल है कि अन्य दो तरीकों है (हालांकि छोटी सूची आकारों के लिए, आप इंटरमीडिएट ListBuffer निर्माण करने के ऊपरी हिस्से को बचाते हैं)।

---

दूसरे शब्दों में, यदि आप a और b के सापेक्ष आकार के बारे में ज्ञान है, तो आप यह सुनिश्चित करें कि उपसर्ग छोटे दो सूचियों के है बनाना चाहिए। आपको लगता है कि ज्ञान नहीं है, तो, वहाँ कुछ भी नहीं है आप कर सकते हैं, क्योंकि एक List पर size आपरेशन हे लेता है (एन) :)

---

दूसरी ओर, एक भविष्य स्काला संस्करण में आप एक देख सकते हैं Vector संगतता एल्गोरिदम में सुधार हुआ, जैसा कि this ScalaDays talk में दिखाया गया है। यह ओ (लॉग एन) समय में कार्य को हल करने का वादा करता है।