在Scala中生成字符串的频率映射

Question

假设我有一个字符串,"你好",我想生成一个字符频率图:

Map[Char,Int] = Map(h -> 1, e -> 1, o -> 1, l -> 2)

我可以迭代地做到这一点:

val str = "hello"
var counts = new scala.collection.mutable.HashMap[Char,Int]
for (i <- str) {
    if (counts.contains(i))
        counts.put(i, counts(i) + 1)
    else
        counts.put(i, 1)
}

通过在REPL中乱搞,我发现我可以做一些更简洁的事情而不使用可变集合:

> str.groupBy(_.toChar).map{ p => (p._1, p._2.length)}
scala.collection.immutable.Map[Char,Int] = Map(h -> 1, e -> 1, o -> 1, l -> 2)

但是我不知道groupBy()的性能特征,也不知道传递给map的块中发生了什么(就像p确实是这样).

如何使用Scala中的功能范例以惯用方式执行此操作？

---

作为背景,我是第一次从Ruby来到Scala.在Ruby中,我会使用,inject但我不确定在Scala中执行它的并行方法是:

counts = str.each_byte.inject(Hash.new(0)){ |h, c| h[c] += 1; h}

Answer 1

1)什么p意思？

groupBy采用将元素映射到类型键的函数K.在某些集合上调用时Coll,它返回一个Map[K, Coll]包含从键K映射到映射到同一键的所有元素的映射.

所以,你的情况,str.groupBy(_.toChar)产生从一个关键的地图测绘k(这是一个字符)到一个字符串的所有元素(字符)c这样k == c.toChar.你得到这个:

Map(e -> "e", h -> "h", l -> "ll", o -> "o")

A Map是可重复的键和值对.在这种情况下,每对都是一个字符和一串元素.map在a Map上调用操作涉及映射这些对 - p是一对p._1是一个字符,并且p._2是相关的字符串(您可以在其上调用length,如上所述).

2)如何惯用这个

以上是如何用惯用语 - 使用groupBy和map.或者,您可以在字符串长度上使用不可变映射和递归来计算频率,或者使用不可变映射和a foldLeft.

3)性能特征

最好的基准来看看差异.这里有几个microbenchmark用于高度重复的字符串(~3GHz iMac,JDK7,Scala 2.10.0每晚):

object Imperative extends testing.Benchmark {
  val str = "abc" * 750000

  def run() {
    var counts = new scala.collection.mutable.HashMap[Char,Int]
    var i = 0
    val until = str.length
    while (i < until) {
      var c = str(i)
      if (counts.contains(c))
        counts.put(c, counts(c) + 1)
      else
        counts.put(c, 1)
      i += 1
    }

    //println(f)
  }
}


object Combinators extends testing.Benchmark {
  val str = "abc" * 750000

  def run() {
    val f = str.groupBy(_.toChar).map(p => (p._1, p._2.length))
  }
}


object Fold extends testing.Benchmark {
  val str = "abc" * 750000

  def run() {
    val f = str.foldLeft(Map[Char, Int]() withDefaultValue 0){(h, c) => h.updated(c, h(c)+1)}
  }
}

结果:

• 势在必行: $ 103 57 53 58 53 53 53 53 53 53

• 组合子: $ 72 51 63 56 53 52 52 54 53 53

• 折: $ 163 62 71 62 57 57 57 58 57 57

请注意,更改要使用的命令式版本withDefaultValue:

var counts = new scala.collection.mutable.HashMap[Char,Int].withDefaultValue(0)
var i = 0
val until = str.length
while (i < until) {
  var c = str(i)
  counts.put(c, counts(c) + 1)
  i += 1
}

由于转发每个put电话,显然非常慢:

• withDefaultValue: $ 133 87 109 106 101 100 101 100 101 101

结论:在这种情况下,角色的装箱和拆箱足够高,因此很难观察到这些方法之间的性能差异.

编辑:

更新:您可能希望使用ScalaMeter内联基准测试来代替Benchmark特征.

Answer 2

扩展Axel的答案.

您的groupBy解决方案已经正常运行 它只是微小的修正,可以使它更清洁:

str.groupBy(_.toChar).mapValues(_.size)

斯卡拉的替代方案inject是foldLeft,foldRight,reduce,reduceOption这取决于你如何使用它.您inject在Ruby中使用的方式不起作用,因为您的解决方案基于变异,h而在功能世界中,可变性是"禁忌".以下是您inject在Scala中如何使用接近您的功能样式的解决方案:

str.foldLeft( Map[Char, Int]() ){ (m, c) => m + (c -> (m.getOrElse(c, 0) + 1)) }

显然groupBy看起来好多了.

Answer 3

您在ruby上的示例几乎可以直接转换为使用foldLeft和不可变的Scala Map.

这是一个可能的解决方案:

str.foldLeft(Map[Char, Int]() withDefaultValue 0){(h, c) => h.updated(c, h(c)+1)}

实际上,如果你对局部可变性没问题,你可以做这样的事情:

def charFrequencies(str: String): collection.Map[Char, Int] = {
  val hash = collection.mutable.HashMap.empty[Char, Int] withDefaultValue 0
  str foreach { hash(_) += 1 }
  hash
}

表达hash(_) += 1将被贬低c => hash(c) = hash(c) + 1然后去c => hash.update(c, hash.apply(c) + 1)

此解决方案应该比功能解决方案更有效,因为它不会创建中间集合.另外因为方法返回不可变collection.Map[Char, Int],结果将被视为不可变(只要没有人会对它执行不安全的向下转换).

Answer 4

从 开始Scala 2.13，我们可以使用groupMapReduce（顾名思义）等价于groupBy后跟mapValues和减少步骤的方法：

"hello".groupMapReduce(identity)(_ => 1)(_ + _)
// immutable.Map[Char,Int] = Map(e -> 1, h -> 1, l -> 2, o -> 1)

这个：

• groups 字符（组的一部分 组MapReduce 的）

• maps 每个分组值出现到 1（映射组的一部分Map Reduce 的）

• reduce_ + _通过将一组值 ( ) 中的s 个值相加（减少 groupMap 的一部分 Reduce 的）。

这是一次通过以下字符序列执行的等效版本：

"hello".groupBy(identity).mapValues(_.map(_ => 1).reduce(_+_))