在具有大型数据的 Scala 中对可变映射使用更新操作的性能差异

Question

我想知道对可变映射的更新操作在性能上是否比重新分配更好。

假设我有以下地图

val m=Map(1 -> Set("apple", "banana"),
          2 -> Set("banana", "cabbage"),
          3 -> Set("cabbage", "dumplings"))

我想将其反转到这张地图中：

 Map("apple" -> Set(1),
     "banana" -> Set(1, 2),
     "cabbage" -> Set(2, 3),
     "dumplings" -> Set(3))

这样做的代码是：

def reverse(m:Map[Int,Set[String]])={
  var rm = Map[String,Set[Int]]()
  m.keySet foreach { k=>
       m(k) foreach { e =>
         rm = rm + (e -> (rm.getOrElse(e, Set()) + k))
       }
  }
  rm
}

如果地图尺寸很大，在地图上使用更新运算符会更有效吗？

使用地图更新的代码如下：

def reverse(m:Map[Int,Set[String]])={
  var rm = scala.collection.mutable.Map[String,Set[Int]]()
  m.keySet foreach { k=>
      m(k) foreach { e =>
         rm.update(e,(rm.getOrElse(e, Set()) + k))                                                        
      }
  }
  rm
}

Answer 1

可变和不可变集合之间的权衡通常归结为：

不可变集合更安全地共享并允许使用 structural sharing
可变集合具有更好的性能

前段时间我比较了 Scala 中可变和不可变映射的性能，差异大约是可变映射的 2 到 3 倍。

因此，当性能不重要时，为了安全性和可读性，我通常会使用不可变集合。

例如，在您的情况下，执行此转换的功能 "scala way" 将是这样的：

m.view
 .flatMap(x => x._2.map(_ -> x._1))  // flatten map to lazy view of String->Int pairs
 .groupBy(_._1)                      // group pairs by String part
 .mapValues(_.map(_._2).toSet)       // extract all Int parts into Set

虽然我使用惰性视图来避免创建中间集合，groupBy 仍然在内部创建可变映射（您可能需要检查它的来源，逻辑与您所写的非常相似），这反过来被转换为不可变 Map 然后被 mapValues.

丢弃

现在，如果您想充分发挥性能，您可以使用可变集合并尽可能少地更新不可变集合。

对于你的情况意味着有 Map 的可变 Sets 作为你的中间缓冲区：

def transform(m:Map[Int, Set[String]]):Map[String, Set[Int]] = {
  val accum:Map[String, mutable.Set[Int]] = 
    m.valuesIterator.flatten.map(_ -> mutable.Set[Int]()).toMap

  for ((k, vals) <- m; v <- vals) {
    accum(v) += k
  }
  accum.mapValues(_.toSet)
}

请注意，我不会在创建后更新 accum：我正在为每个值执行一次地图查找和一组更新，而在您的两个示例中都有额外的地图更新。

我相信这段代码在性能方面是合理的最佳选择。我自己没有进行任何测试，但我强烈建议您对您的真实数据进行测试，并在此处显示 post 结果。

此外，如果您想走得更远，您可能想尝试可变 BitSet 而不是 Set[Int]。如果您的数据中的整数相当小，它可能会产生一些小的性能提升。

Answer 2

我运行一些测试使用Rex Kerr's Thyme utility。

首先我创建了一些测试数据。

val rndm = new util.Random
val dna = Seq('A','C','G','T')
val m = (1 to 4000).map(_ -> Set(rndm.shuffle(dna).mkString
                                ,rndm.shuffle(dna).mkString)).toMap

然后我用 immutable.Map 和 mutable.Map 版本计时了一些运行。这是一个示例结果：

Time:    2.417 ms   95% CI 2.337 ms - 2.498 ms   (n=19)  // immutable
Time:    1.618 ms   95% CI 1.579 ms - 1.657 ms   (n=19)  // mutable
Time     2.278 ms   95% CI 2.238 ms - 2.319 ms   (n=19)  // functional version

如您所见，使用具有 update() 的可变 Map 具有显着的性能优势。

为了好玩，我还将这些结果与功能更强大的 Map reverse（或我称之为 Map inverter）的版本进行了比较。不涉及 var 或任何可变类型。

m.flatten{case(k, vs) => vs.map((_, k))}
 .groupBy(_._1)
 .mapValues(_.map(_._2).toSet)

此版本始终优于您的不可变版本，但仍未接近可变时间。

Answer 3

仅以功能方式使用@Aivean 方法：

def transform(mp :Map[Int, Set[String]]) = {
   val accum = mp.values.flatten
                 .toSet.map( (_-> scala.collection.mutable.Set[Int]())).toMap
   mp.map {case(k,vals) => vals.map( v => accum(v)+=k)}
   accum.mapValues(_.toSet)
}

在具有大型数据的 Scala 中对可变映射使用更新操作的性能差异

Performance Difference Using Update Operation on a Mutable Map in Scala with a Large Size Data

performance

scala

collections

scala-collections

processing-efficiency