Scala'da, immutable ve mutable setleri ve haritaları çöp toplama açısından nasıl karşılaştırılır?

Question

Büyük bir yapı içinde yineleme yaparken, küçük bir (genellikle 1, bazen bir) ekleyerek, küçük bir (örneğin, kısa dizeleri veya basit vaka sınıfları) nesneler ile setleri ve haritalar alarak içeren bir kod yazıyorum avuç) nesneye ya da haritaya nesneler. Değişken kümeler ve haritalar kullanmak sanki değişmez olanlara göre önemli bir hızlanma sağlıyormuş gibi görünür, fakat farkı nicel olarak değerlendirmede sorun yaşıyorum.

Scala'nın çöp toplama işleminin, değişmez veri yapılarını kullanırken önemli bir yavaşlamaya neden olması mantıklı mı? Değiştirilebilir veri yapılarını kullanarak bunu düzeltmek ister misiniz?

Answer 1

Scala değişmez koleksiyonları şaşırtıcı derecede verimli. Çoğunlukla bir yapı değiştiğinde, yapının çoğu yeniden kullanılır.

Ancak çok fazla değişiklik yaparsanız, değiştirilebilen yapılar daha iyi bir uyum sağlayabilir. Aslında bu, Scala Collection API'sinin birçok yerde dahili olarak yaptığı şeydir: Yeni şeyler oluşturmak için değişebilir bir veri yapısı kullanın ve sadece son adım olarak, bir değişmez oluşturun ve döndürün.

Answer 2

Scala Değişken veri yapıları, belleği önceden tahsis ederek değişmez olanlara göre verimlilik kazanır. Pek çok ekleme için daha uygundurlar (bu nedenle neden değişebilirler). fonksiyonunun uygulanması bir göz atın + = Harita uzanır varsayılan değişken Koleksiyonu, bir HashMap, içinde:

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 kullanarak değişken Harita uygular

addEntry tanımlar

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) 
} 

koleksiyonun boyutu eşiği ulaşıldığında her zaman iki katına çıkarılır. Bu nedenle, sürekli olarak n boş bir değişken veri yapısına bir kerede bir giriş ekliyorsanız, yalnızca günlük (n) zamanlarını yeniden boyutlandırmanız gerekecektir. Değişmez veri yapısı uygulamasına derinlemesine bakmadım, ama her ekleme için yeniden boyutlandırmak zorunda kalacağım. Bu nedenle performans eşitsizliğiniz.