Scala: groupBy (identity) of List Elements

Question

Desarrollo una aplicación que construye pares de palabras en texto (tokenizado) y produce el número de veces que ocurre cada par (incluso cuando pares de mismas palabras aparecen varias veces, está bien porque se igualará más adelante en el algoritmo).

Cuando uso

elements groupBy() 

Quiero grupo por el contenido de los elementos en sí, por lo que escribió lo siguiente:

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

Ahora, Soy plenamente consciente de que este auto() truco es un sucio truco. Así que pensé que un poco salió con un:

grouppedPairs = table groupBy (x => x) 

De esta forma produjo lo que quería. Sin embargo, todavía siento que claramente extraño algo y debería haber una manera más fácil de hacerlo. Alguna idea en absoluto, querido todo?

Además, si me ayudas a mejorar la parte de extracción de pares, también ayudará mucho - se ve muy imperativo, C++ - ish en este momento. ¡Muchas gracias de antemano!

Answer 1

está creando una lista de pares de todas las palabras contra todas las palabras iterando sobre las palabras dos veces, donde supongo que solo quiere los pares vecinos. lo más fácil es utilizar una vista deslizante en su lugar.

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

Otro enfoque sería doblar la lista de pares mediante su suma. aunque no estoy seguro de que esto sea más eficiente:

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

veo que devuelve un número relativo (Doble). por simplicidad acabo de contar las ocurrencias, por lo que necesita hacer la división final. Creo que quiere dividir por el número total de pares (words.size - 1) y no por el número de pares únicos (grouped.size) ..., por lo que las frecuencias relativas se suman a 1.0

Answer 2

I ' d sugerir esto:

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

El para la comprensión es mucho más fácil de leer, y ya hay una función predifined identity, con es una versión generalizada de la self.

Answer 3

enfoque alternativo que no es de orden O(num_words * num_words) pero de orden O(num_unique_words * num_unique_words) (o algo así):

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