性能差异在Scala大小可变的映射上使用更新操作

我想知道可变映射上的更新操作是否比重新分配的性能更好。性能差异在Scala大小可变的映射上使用更新操作

让我们假设我有以下的地图

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 
}

来源

2017-06-01 user-asterix

此集合[性能DOC]（http://docs.scala-lang.org/overviews/collections/performance-characteristics）可能是利益。 –

谢谢您的重要参考。我以前不知道。我有一个快速查看和我所问的地图集合的情况没有提到。 –

我使用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 reverse（或我称之为Map逆变器）的更多功能版本进行了比较。没有var或涉及任何可变类型。

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

这个版本一贯击败你不可变的版本，但仍然没有接近可变的时机。

来源

2017-06-02 07:13:29 jwvh

感谢您抽出时间做测试。表现大约提高了33％。是否也可以添加功能版本的测试结果 - 仅用于比较所有功能版本。雷克斯克尔的百里香实用程序看起来很有趣，我会检查它的其他测试。 –

@ user-asterix，作为请求：'时间：2.278 ms 95％CI 2.238 ms - 2.319 ms（n = 19）' – jwvh

仅在功能版本结果旁添加了其他结果 –

可变和不可变的集合之间的-的贸易通常范围缩小到这一点：

一成不变的集合是更安全的共享和允许使用structural sharing
可变集合具有更好的性能

前段时间我在Scala中做过可变和不可变Map之间的性能比较，差异大约是2到3次，而不支持可变的。

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

例如，在你的情况下的功能“斯卡拉方式”的执行这种转变会是这样的：

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丢弃。

现在，如果你想挤压每一点性能，你想使用可变集合并尽可能少地更新不可变集合。

对于你的情况是具有可变SetsMap你中间缓冲手段：我做的正是一个地图查询和一组更新：

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对于每个值，在这两个示例中都有额外的地图更新。

我相信这个代码是合理的最佳性能明智。我自己没有进行任何测试，但我强烈建议您在这里对您的真实数据进行处理并发布结果。另外，如果你想更进一步，你可能想尝试可变的BitSet而不是Set[Int]。如果您的数据中的整数相当小，则可能会导致性能稍微提高。

来源

2017-06-02 05:45:39 Aivean

您的代码是一个侧面主题，很有趣，我曾希望有人会给我一些关于如何创建和更新高效地图的线索。据我所知，而不是一个可变的地图，你从值列表创建了一个不可变的地图，然后为每个键创建了一个可变的Set。感谢代码示例。 –

只是使用@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) 
}

来源

2017-06-05 14:10:05

性能差异在Scala大小可变的映射上使用更新操作

回答

相关问题