Scala：列表元素的groupBy（身份）

Question

我开发了一个应用程序，它在（标记化的）文本中构建单词对，并生成每对出现的次数（即使相同的单词对出现多次，也没关系，因为稍后会在算法中平衡）。

当我使用时，

elements groupBy()

我想按元素的内容本身进行分组，所以我写了以下内容：

def self(x: (String, String)) = x

/**
 * Maps a collection of words to a map where key is a pair of words and the 
 *  value is number of
 * times this pair
 * occurs in the passed array
 */
def producePairs(words: Array[String]): Map[(String,String), Double] = {
  var table = List[(String, String)]()
  words.foreach(w1 =>
    words.foreach(w2 =>
      table = table ::: List((w1, w2))))


  val grouppedPairs = table.groupBy(self)
  val size = int2double(grouppedPairs.size)
  return grouppedPairs.mapValues(_.length / size)
}

现在，我完全意识到这个 self() 技巧是一个肮脏的黑客。于是我想了想，得出了一个结论：

grouppedPairs = table groupBy (x => x)

这样就产生了我想要的东西。然而，我仍然觉得我明显错过了一些东西，应该有更简单的方法来做到这一点。亲爱的大家，有什么想法吗？

另外，如果你能帮助我改进对提取部分，它也会有很大帮助——它现在看起来非常必要，C++ 左右。非常感谢！

Answer 1

我建议这样：

def producePairs(words: Array[String]): Map[(String,String), Double] = {
    val table = for(w1 <- words; w2 <- words) yield (w1,w2)
    val grouppedPairs = table.groupBy(identity)
    val size = grouppedPairs.size.toDouble
    grouppedPairs.mapValues(_.length / size)
}

for 理解更容易阅读，并且已经有一个预定义函数 identity，其中是您的 self 的通用版本。

Answer 2

您正在通过迭代单词两次来创建所有单词对的所有单词对的列表，我猜您只需要相邻的对。最简单的方法是使用滑动视图。

def producePairs(words: Array[String]): Map[(String, String), Int] = {
  val pairs   = words.sliding(2, 1).map(arr => arr(0) -> arr(1)).toList
  val grouped = pairs.groupBy(t => t)
  grouped.mapValues(_.size)
}

另一种方法是通过求和来折叠配对列表。不确定这是否更有效：

def producePairs(words: Array[String]): Map[(String, String), Int] = {
  val pairs = words.sliding(2, 1).map(arr => arr(0) -> arr(1))
  pairs.foldLeft(Map.empty[(String, String), Int]) { (m, p) =>
     m + (p -> (m.getOrElse(p, 0) + 1))
  }
}

我看到你返回一个相对数字（双精度）。为简单起见，我刚刚计算了出现次数，因此您需要进行最后的除法。我认为你想除以总对的数量 (words.size - 1) 而不是除以唯一对的数量 (grouped.size)...，因此相对频率总和为 1.0

Answer 3

另一种方法的顺序不是 O(num_words * num_words) ，而是 O(num_unique_words * num_unique_words) （或类似的东西）：

def producePairs[T <% Traversable[String]](words: T): Map[(String,String), Double] = {
  val counts = words.groupBy(identity).map{case (w, ws) => (w -> ws.size)}
  val size = (counts.size * counts.size).toDouble
  for(w1 <- counts; w2 <- counts) yield {
      ((w1._1, w2._1) -> ((w1._2 * w2._2) / size))
  }
}