我正在编写一些代码,这些代码涉及在其中包含“小”(例如,短字符串或简单案例类)对象的集合和映射,同时通过一个大结构递归,在每个点添加一个小的(通常是 1,有时是少数)对象到集合或地图。似乎使用可变集和映射比不可变集显着加快了速度,但我在定量评估差异时遇到了麻烦。
当我使用不可变数据结构时,Scala 的垃圾收集会导致显着减速是否有意义?使用可变数据结构可以解决这个问题吗?
我正在编写一些代码,这些代码涉及在其中包含“小”(例如,短字符串或简单案例类)对象的集合和映射,同时通过一个大结构递归,在每个点添加一个小的(通常是 1,有时是少数)对象到集合或地图。似乎使用可变集和映射比不可变集显着加快了速度,但我在定量评估差异时遇到了麻烦。
当我使用不可变数据结构时,Scala 的垃圾收集会导致显着减速是否有意义?使用可变数据结构可以解决这个问题吗?
Scala 不可变集合的效率惊人。主要是因为当结构发生变化时,很多结构都会被重用。
但是,如果您进行大量更改,则可变结构可能更合适。实际上,这就是 Scala Collection API 在内部的许多地方所做的:使用可变数据结构来构建新的东西,并且仅作为最后一步,创建一个不可变的并返回它。
Scala 可变数据结构通过预分配内存比不可变数据结构更高效。它们更适合许多插入(因此它们是可变的)。看一下默认可变Collection中函数+=的实现,一个HashMap,Map扩展了:
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 实现了一个可变 Map,它定义了 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)
}
每次达到阈值时,集合的大小都会加倍。因此,如果您一次重复地将 n 个条目添加到一个空的可变数据结构中,您只需要调整 log(n) 次。我没有深入研究不可变数据结构的实现,但我假设您将不得不在每次插入时调整大小。因此,您的性能差异。