स्कैला में, कचरा संग्रह के संबंध में अपरिवर्तनीय और परिवर्तनीय सेट और मानचित्र तुलना कैसे करते हैं?

Question

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

क्या यह समझ में आता है कि जब मैं अपरिवर्तनीय डेटा संरचनाओं का उपयोग कर रहा हूं तो स्कैला का कचरा संग्रह महत्वपूर्ण धीमा हो जाएगा? उत्परिवर्तनीय डेटा संरचनाओं का उपयोग करना इसे ठीक करेगा?

Answer 1

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

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

Answer 2

स्कैला उत्परिवर्तनीय डेटा संरचनाएं पूर्व-आवंटित स्मृति द्वारा अपरिवर्तनीय लोगों पर दक्षता प्राप्त करती हैं। वे कई आवेषणों के लिए बेहतर अनुकूल हैं (इसलिए वे उत्परिवर्तनीय क्यों हैं)। समारोह के कार्यान्वयन पर एक नजर डालें + = डिफ़ॉल्ट परिवर्तनशील संग्रह, एक HashMap, जो मानचित्र फैली में:

https://github.com/scala/scala/blob/v2.9.2/src/library/scala/collection/mutable/HashMap.scala#L84

def += (kv: (A, B)): this.type = { 
    val e = findEntry(kv._1) 
    if (e == null) addEntry(new Entry(kv._1, kv._2)) 
    else e.value = kv._2 
    this 
} 

HashMap HashTable का उपयोग कर एक परिवर्तनशील मानचित्र को लागू करता है, जो addEntry

को परिभाषित करता है

https://github.com/scala/scala/blob/v2.9.2/src/library/scala/collection/mutable/HashTable.scala#L117

protected def addEntry(e: Entry) { 
    val h = index(elemHashCode(e.key)) 
    e.next = table(h).asInstanceOf[Entry] 
    table(h) = e 
    tableSize = tableSize + 1 
    nnSizeMapAdd(h) 
    if (tableSize > threshold) 
    resize(2 * table.length) 
} 

संग्रह का आकार हर बार सीमा तक पहुंचने पर दोगुनी हो जाती है। इसलिए यदि आप बार-बार जोड़ रहे हैं तो एक खाली म्यूटेबल डेटा संरचना में एक समय में एक प्रविष्टि दर्ज करता है, तो आपको केवल लॉग (एन) बार का आकार बदलने की आवश्यकता होगी। मैंने गहराई से अपरिवर्तनीय डेटा संरचना कार्यान्वयन को नहीं देखा है, लेकिन मुझे लगता है कि आपको प्रत्येक सम्मिलन पर आकार बदलना होगा। इसलिए आपके प्रदर्शन असमानता।