W Scala, w jaki sposób można porównać niezmienne i zmienne zestawy i mapy w odniesieniu do zbierania śmieci?

Question

Piszę kod, który polega na przyjmowaniu zestawów i map z "małymi" (np. Krótkimi łańcuchami lub prostymi klasami przypadków) obiektami, podczas powtarzania przez dużą strukturę, w każdym punkcie dodawania małego (zwykle 1, czasem garść) obiektów do zestawu lub mapy. Wygląda na to, że użycie zestawów zmiennych i map daje znaczące przyspieszenie w stosunku do niezmiennych, ale mam problem z ilościową oceną różnicy.

Czy to ma sens, że odbiór Scaly spowodowałby znaczące spowolnienie, gdy używam niezmiennych struktur danych? Czy za pomocą mutowalnych struktur danych to naprawić?

Answer 1

Niezmienne kolekcje Scala są zaskakująco wydajne. Głównie dlatego, że gdy struktura ulega zmianie, wiele elementów zostaje ponownie wykorzystanych.

Ale jeśli wykonasz wiele zmian, zmienne struktury mogą lepiej pasować. Właściwie to właśnie interfejs API Scala Collection działa w wielu miejscach wewnętrznie: Użyj zmultiplikowanej struktury danych, aby budować nowe rzeczy i tylko jako ostatni krok, stwórz niezmienny i zwróć go.

Answer 2

Scala Struktury danych Mutable uzyskują efektywność nad niezmiennymi poprzez wstępną alokację pamięci. Są lepiej dopasowane do wielu wstawek (stąd dlaczego są zmienne). Spójrz na realizację funkcji + = w domyślnym zmienny Collection, HashMap, który Mapa wysuwa się:

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 implementuje zmienny Mapa stosując HashTable, który określa 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) 
} 

wielkość kolekcji jest podwojona każdym razem, gdy próg zostanie osiągnięty. Jeśli więc wielokrotnie dodajesz jeden wpis naraz do pustej, zmieniającej się struktury danych, musisz tylko zmienić rozmiar log (n) razy. Nie analizowałem do końca niezmiennej implementacji struktury danych, ale zakładam, że będziesz musiał zmienić rozmiar każdej wstawki. Stąd różnica w wydajności.