string - initialize - scala map of maps

Generando un mapa de frecuencia para una cadena en Scala

Question

Digamos que tengo una cadena, "hola", y quiero generar un mapa de frecuencia de caracteres:

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

Yo podría hacer esto iterativamente

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

Al jugar en el REPL, descubrí que puedo hacer algo un poco más conciso y no usar una colección mutable:

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

Pero no conozco las características de rendimiento de groupBy () ni lo que está pasando en el bloque que se pasa al mapa (como qué es exactamente, p).

¿Cómo hago esto idiomáticamente usando los paradigmas funcionales en Scala?

Para los antecedentes, acabo de llegar a Scala por primera vez desde Ruby. En Ruby, usaría inject pero no estoy seguro de cuál es la forma paralela de hacerlo en Scala:

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

Answer 1

1) ¿Qué significa p ?

groupBy toma una función que mapea elementos a una clave de tipo K Cuando se invoca en alguna colección Coll , devuelve un Map[K, Coll] que contiene las asignaciones de las claves K a todos los elementos que se asignaron a la misma clave.

Entonces, en su caso, str.groupBy(_.toChar) produce una asignación de mapa de una clave k (que es un carácter) a una cadena con todos los elementos (caracteres) c tal que k == c.toChar . Usted obtiene esto:

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

Un Map es un iterable de pares de claves y valores. En este caso, cada par es un carácter y una cadena de elementos. Llamar a la operación de map en un Map implica mapear en estos pares - p es un par donde p._1 es un carácter, y p._2 es la cadena asociada (a la que puede llamar length , como hizo anteriormente).

2) ¿Cómo hacer esto idiomáticamente?

Lo anterior es cómo hacerlo de forma idiomática: usando groupBy y map . Alternativamente, puede usar un mapa inmutable y una recursión en la longitud de la cadena para calcular las frecuencias, o un mapa inmutable y un foldLeft .

3) Característica de rendimiento

Lo mejor es benchmark para ver las diferencias. Aquí hay un par de microbenchmark para una cadena altamente repetitiva (~ 3GHz iMac, JDK7, Scala 2.10.0 todas las noches):

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

Resultados:

• Imperativo: $ 103 57 53 58 53 53 53 53 53 53

• Combinadores: $ 72 51 63 56 53 52 52 54 53 53

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

Tenga en cuenta que al cambiar la versión imperativa para usar con 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
}

Aparentemente es terriblemente lento debido a que reenvía cada llamada de put :

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

Conclusión: el boxeo y el desajuste de los personajes en este caso es lo suficientemente alto como para que las diferencias en el rendimiento entre estos enfoques sean difíciles de observar.

EDITAR:

Actualización: es posible que desee utilizar la evaluación comparativa en línea ScalaMeter en lugar del rasgo de Benchmark .

Answer 2

Al iniciar Scala 2.13 , podemos usar el método groupMapReduce que es (como su nombre lo indica) un equivalente de groupBy seguido de mapValues y un paso de reducción:

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

Esta:

• Caracteres del grupo (parte del grupo MapReduce del grupo )

• map s cada ocurrencia de valor agrupado a 1 (parte del mapa del grupo Mapa Reducir)

• reduce los valores de s dentro de un grupo de valores ( _ + _ ) sumándolos (reduzca parte de groupMap Reduce ).

Esta es una versión equivalente realizada en una sola pasada a través de la secuencia de caracteres de:

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

Answer 3

Extendiendo la respuesta de Axel.

Tu solución groupBy ya es funcional. Solo hay una pequeña corrección que podría hacerla más limpia:

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

La alternativa de Scala para inject es foldLeft , foldRight , reduce , reduceOption dependiendo de cómo lo use. La forma en que usó inject en Ruby no es funcional, ya que su solución se basa en la mutación h y en la mutabilidad del mundo funcional es un "no-no". Así es como haría la solución cerca de su inject pero con un estilo funcional en Scala:

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

Obviamente groupBy ve mucho mejor.

Answer 4

Su ejemplo en ruby ​​se puede traducir casi directamente a Scala usando foldLeft Map foldLeft e inmutable.

Aquí está una de las posibles soluciones:

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

En realidad, si estás de acuerdo con la mutabilidad local, puedes hacer algo como esto:

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

La expresión hash(_) += 1 se desugará a c => hash(c) = hash(c) + 1 y luego a c => hash.update(c, hash.apply(c) + 1)

Esta solución debería ser más eficiente que las funcionales, ya que no crea colecciones intermedias. Además, debido a que el método devuelve una collection.Map[Char, Int] inmutable collection.Map[Char, Int] , el resultado se tratará como inmutable (siempre y cuando nadie realice un downcasting inseguro en él).