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

Теперь я полностью осознаю, что этот трюк с собой () - грязный хак. Поэтому я подумал, что немного вышло с:

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

Для понимания гораздо легче читать, и уже есть предопределенная функция 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))
  }
}

я вижу, вы возвращаете относительное число (Double). для простоты я только что сосчитал вхождения, так что вам нужно сделать последнее деление. Я думаю, что вы хотите разделить на количество общих пар (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))
  }
}