Scala：可变对象不可变对象性能 – OutOfMemoryError

def mergeMaps[A,B](func: (B,B) => B)(listOfMaps: List[Map[A,B]]): Map[A,B] =
    (Map[A,B]() /: (for (m <- listOfMaps; kv <-m) yield kv)) { (acc,kv) =>
      acc + (if (acc.contains(kv._1)) kv._1 -> func(acc(kv._1),kv._2) else kv)
    }

  def mergeMutableMaps[A,B) => B)(listOfMaps: List[mutable.Map[A,B]]): mutable.Map[A,B] =
    (mutable.Map[A,B]() /: (for (m <- listOfMaps; kv <- m) yield kv)) { (acc,kv._2) else kv)
    }

  def mergeMutableImperative[A,B] = {
    val toReturn = mutable.Map[A,B]()
    for (m <- listOfMaps; kv <- m) {
      if (toReturn contains kv._1) {
        toReturn(kv._1) = func(toReturn(kv._1),kv._2)
      } else {
        toReturn(kv._1) = kv._2
      }
    }
    toReturn
  }

那么这真的取决于你正在使用的Map的实际类型.可能是HashMap.现在,像这样的可变结构通过预先分配预期使用的内存来获得性能.你正在加入一百万张地图,所以最终的地图一定会有点大.让我们看看如何添加这些键/值：

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

请参阅调整大小行中的2 *可变的HashMap每次耗尽空间都会增加一倍,而不可变的HashMap在内存使用中相当保守(尽管现有的密钥通常占用更新时的两倍空间).

现在,对于其他性能问题,您将在前两个版本中创建一个键和值列表.这意味着,在您加入任何地图之前,您已经有内存中的每个Tuple2(键/值对)两次！加上List的开销很小,但是我们在讨论超过一百万个元素,而不是开销.

你可能想使用一个投影,这样可以避免这种情况.不幸的是,投影是基于Stream,这对于Scala 2.7.x的目的来说不是很可靠.不过,请尝试这样做：

for (m <- listOfMaps.projection; kv <- m) yield kv

一个流在需要之前不会计算一个值.垃圾收集器也应该收集未使用的元素,只要您不保留对Stream的头部的引用,这在您的算法中似乎就是这种情况.

编辑

补充,产出理解需要一个或多个集合并返回一个新集合.通常情况下,返回的集合与原始集合的类型相同.所以,例如,在下面的代码中,for-comprehension创建一个新的列表,然后将其存储在l2中.它不是val l2 =创建新的列表,而是理解.

val l = List(1,2,3)
val l2 = for (e <- l) yield e*2

现在,我们来看看前两个算法中使用的代码(减去mutable关键字)：

(Map[A,B]() /: (for (m <- listOfMaps; kv <-m) yield kv))

foldLeft操作符(这里用/：synonymous编写)将在for-comprehension返回的对象上被调用.请记住：在操作结束时,会反转对象的顺序和参数.

现在,我们来看看这个对象是什么,在哪个foldLeft被调用.这个理解中的第一个生成器是m 我们知道listofmaps是list>

val kvs = for (m <- listOfMaps.projection; kv <-m) yield kv
(Map[A,B]() /: kvs) { ... }

在这种情况下,你没有获得任何东西.在将流分配给kvs后,数据尚未复制.一旦执行第二行,kvs就会计算出每个元素,因此将保存数据的完整副本.

现在考虑原来的形式::

(Map[A,B]() /: (for (m <- listOfMaps.projection; kv <-m) yield kv))

在这种情况下,流被计算在同一时间使用.我们简单来看一下Stream的折叠方式是如何定义的：

override final def foldLeft[B](z: B)(f: (B,A) => B): B = { 
  if (isEmpty) z 
  else tail.foldLeft(f(z,head))(f) 
}

如果Stream为空,则只返回累加器.否则,计算一个新的累加器(f(z,head)),然后将其传递给该流的尾部.

一旦f(z,头)执行了,那么头就不会有剩余的引用了.换句话说,程序中的任何地方都不会指向Stream的头部,这意味着垃圾收集器可以收集它,从而释放内存.

最终的结果是,通过理解产生的每个元素将只是短暂地存在,同时使用它来计算累加器.这就是保存整个数据的副本.

最后,有一个问题,为什么第三种算法不会从中受益.那么,第三种算法不使用yield,所以没有任何数据的副本.在这种情况下,使用投影只添加一个间接层.