17

我想比较 Scala 中 immutable.Map 和 mutable.Map 的性能特征以进行类似的操作（即将多个映射合并为一个映射。请参阅此问题）。对于可变映射和不可变映射，我似乎都有类似的实现（见下文）。

作为测试，我生成了一个包含 1,000,000 个单项 Map[Int, Int] 的列表，并将此列表传递给我正在测试的函数。有了足够的内存，结果并不令人惊讶：mutable.Map 约为 1200 毫秒，immutable.Map 约为 1800 毫秒，使用 mutable.Map 的命令式实现约为 750 毫秒——不确定是什么导致了巨大的差异，但请随意对此也发表评论。

让我有点吃惊的可能是因为我有点厚，在 IntelliJ 8.1 中的默认运行配置下，两个可变实现都遇到了 OutOfMemoryError，但不可变集合没有。不可变测试确实运行到完成，但运行速度非常慢——大约需要 28 秒。当我增加最大 JVM 内存（大约 200MB，不确定阈值在哪里）时，我得到了上面的结果。

无论如何，这是我真正想知道的：

为什么可变实现会耗尽内存，而不可变实现不会？ 我怀疑不可变版本允许垃圾收集器在可变实现之前运行并释放内存——所有这些垃圾收集都解释了不可变低内存运行的缓慢——但我想要更详细的解释比起那个来说。

下面的实现。（注意：我并不是说这些是最好的实现。请随意提出改进建议。）

  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](func: (B,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) =>
      acc + (if (acc.contains(kv._1)) kv._1 -> func(acc(kv._1), kv._2) else kv)
    }

  def mergeMutableImperative[A,B](func: (B,B) => B)(listOfMaps: List[mutable.Map[A,B]]): mutable.Map[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
  }
4

1 回答 1

25

好吧，这实际上取决于您使用的 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 *了吗？每次用完空间时，resize可变的都会增加一倍，而不可变的在内存使用方面非常保守（尽管现有的键在更新时通常会占用两倍的空间）。HashMap

现在，至于其他性能问题，您正在前两个版本中创建键和值列表。这意味着，在您加入任何地图之前，您已经Tuple2在内存中拥有每个（键/值对）两次！加上 的开销List，虽然很小，但我们谈论的是超过一百万个元素乘以开销。

您可能想要使用投影，这可以避免这种情况。不幸的是，投影是基于 的Stream，这对于我们在 Scala 2.7.x 上的目的来说不是很可靠。不过，试试这个：

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

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

编辑

作为补充，for/yield 推导接受一个或多个集合并返回一个新集合。通常，返回的集合与原始集合的类型相同。因此，例如，在下面的代码中，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用它的/:同义词编写，将在由 for-comprehension 返回的对象上调用。请记住，:运算符末尾的 a 颠倒了对象和参数的顺序。

现在，让我们考虑一下这是什么对象，在哪个对象上foldLeft被调用。用于理解的第一个生成器是m <- listOfMaps. 我们知道这listOfMaps是一个 List[X] 类型的集合，其中 X 在这里并不真正相关。对 a 的理解的结果List总是 another List。其他生成器不相关。

因此，您使用 this List，获取每个内部的所有键/值，Map这是 this 的一个组件List，然后用所有这些创建一个新List的。这就是为什么你要复制你所拥有的一切。

（实际上比这更糟糕，因为每个生成器都会创建一个新的集合；第二个生成器创建的集合只是listOfMaps虽然每个元素的大小，使用后立即丢弃）

下一个问题——实际上是第一个问题，但更容易颠倒答案——是如何使用projection帮助。

当您调用projectionaList时，它会返回类型的新对象Stream（在 Scala 2.7.x 上）。起初您可能认为这只会让事情变得更糟，因为您现在将拥有 的三个副本List，而不是一个。但是 aStream不是预先计算的。它是惰性计算的。

这意味着生成的对象Stream不是 的副本List，而是一个可用于Stream在需要时计算的函数。一旦计算，结果将被保留，因此不需要再次计算。

此外，map, flatMapand filterof a Streamall 返回一个 new ，这意味着您可以将它们全部链接在一起，而无需制作创建它们Stream的 的单个副本。List由于理解与yield使用这些非常功能，使用Stream里面防止不必要的数据副本。

现在，假设你写了这样的东西：

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

在这种情况下，你什么也得不到。分配Streamto后kvs，尚未复制数据。但是，一旦执行了第二行，kvs 将计算其每个元素，因此将保存数据的完整副本。

现在考虑原始形式::

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

在这种情况下，在Stream计算的同时使用 。让我们简单看一下foldLeftfor aStream是如何定义的：

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))，然后将它和函数传递tail给Stream.

但是，一旦f(z, head)执行，将不再有对head. 或者，换句话说，程序中的任何地方都不会指向head的Stream，这意味着垃圾收集器可以收集它，从而释放内存。

最终结果是，由 for-comprehension 生成的每个元素都将短暂存在，而您使用它来计算累加器。这就是您保存整个数据副本的方式。

最后，还有一个问题，为什么第三种算法不能从中受益。好吧，第三种算法不使用yield，因此不会复制任何数据。在这种情况下， usingprojection只添加了一个间接层。

于 2009-08-20T21:31:12.167 回答