5

我正在编写一些代码，这些代码涉及在其中包含“小”（例如，短字符串或简单案例类）对象的集合和映射，同时通过一个大结构递归，在每个点添加一个小的（通常是 1，有时是少数）对象到集合或地图。似乎使用可变集和映射比不可变集显着加快了速度，但我在定量评估差异时遇到了麻烦。

当我使用不可变数据结构时，Scala 的垃圾收集会导致显着减速是否有意义？使用可变数据结构可以解决这个问题吗？

4

2 回答 2

6

Scala 不可变集合的效率惊人。主要是因为当结构发生变化时，很多结构都会被重用。

但是，如果您进行大量更改，则可变结构可能更合适。实际上，这就是 Scala Collection API 在内部的许多地方所做的：使用可变数据结构来构建新的东西，并且仅作为最后一步，创建一个不可变的并返回它。

于 2012-10-16T06:03:10.890 回答
-1

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) 次。我没有深入研究不可变数据结构的实现，但我假设您将不得不在每次插入时调整大小。因此，您的性能差异。

于 2012-10-16T16:53:58.527 回答