28

假设我有一个字符串“hello”，我想生成一个字符频率图：

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}
4

4 回答 4

37

1) 是什么p意思？

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

因此，在您的情况下，生成从键（这是一个字符）到包含所有元素（字符）的字符串str.groupBy(_.toChar)的映射映射，例如. 你得到这个：kck == c.toChar

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

AMap是键和值对的可迭代对象。在这种情况下，每一对都是一个字符和一串元素。调用mapa 上的操作Map涉及到这些对上的映射 -p是一对，其中p._1是一个字符，并且p._2是关联的字符串（您可以在其上调用length，就像上面所做的那样）。

2）如何习惯性地做到这一点

以上是如何惯用地做到这一点 - 使用groupByand map。或者，您可以使用不可变映射和字符串长度上的递归来计算频率，或者使用不可变映射和foldLeft.

3) 性能特点

最好进行基准测试以查看差异。这里有几个用于高度重复字符串的微基准测试（~3GHz iMac、JDK7、Scala 2.10.0 nightly）：

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 内联基准测试来代替Benchmarktrait。

于 2012-08-24T08:06:35.833 回答
26

扩展阿克塞尔的答案。

您的groupBy解决方案已经可用。对其进行了微小的修正，可以使其更清洁：

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

Scala 的替代方案inject是foldLeft, foldRight, reduce，reduceOption具体取决于您如何使用它。您inject在 Ruby 中使用的方式不是函数式的，因为您的解决方案是基于变异的h，而在函数式世界中，可变性是“不行的”。以下是您如何在 Scala 中以接近您inject但功能风格的方式执行解决方案：

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

显然groupBy看起来好多了。

于 2012-08-24T08:26:03.923 回答
11

您在 ruby​​ 上的示例几乎可以使用foldLeft和 immutable直接转换为 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)

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

于 2012-08-24T08:26:00.693 回答
6

从 开始Scala 2.13，我们可以使用groupMapReduce（顾名思义）等效于 a和 reduce 步骤的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 的一部分）

  • reduces 值在一组值 ( _ + _) 中，通过对它们求和（减少 groupMap Reduce的一部分）。

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

"hello".groupBy(identity).mapValues(_.map(_ => 1).reduce(_+_))
于 2018-10-06T10:16:37.270 回答