Ejemplo de la función agregada de Scala

Hola, hallamos la solución a tu búsqueda, deslízate y la obtendrás aquí.

Solución:

Veamos si algo de arte ascii no ayuda. Considere la firma de tipo de aggregate:

def aggregate [B] (z: B)(seqop: (B, A) ⇒ B, combop: (B, B) ⇒ B): B

Además, tenga en cuenta que A se refiere al tipo de colección. Entonces, digamos que tenemos 4 elementos en esta colección, luego aggregate podría funcionar así:

z   A   z   A   z   A   z   A
  /      /seqop /      /    
  B       B       B       B
       /  combop      /
      B _           _ B
          combop  /
              B

Veamos un ejemplo práctico de eso. Di que tengo un GenSeq("This", "is", "an", "example")y quiero saber cuántos personajes hay en él. Puedo escribir lo siguiente:

Tenga en cuenta el uso de par en el siguiente fragmento de código. La segunda función que se pasa a la agregación es la que se llama después de que se calculan las secuencias individuales. Scala solo puede hacer esto para conjuntos que se pueden paralelizar.

import scala.collection.GenSeq
val seq = GenSeq("This", "is", "an", "example")
val chars = seq.par.aggregate(0)(_ + _.length, _ + _)

Entonces, primero calcularía esto:

0 + "This".length     // 4
0 + "is".length       // 2
0 + "an".length       // 2
0 + "example".length  // 7

Lo que hace a continuación no se puede predecir (hay más de una forma de combinar los resultados), pero podría hacer esto (como en el arte ascii anterior):

4 + 2 // 6
2 + 7 // 9

En cuyo punto concluye con

6 + 9 // 15

que da el resultado final. Ahora, esto es un poco similar en estructura a foldLeft, pero tiene una función adicional (B, B) => B, que pliegue no tiene. Esta función, sin embargo, le permite trabajar en paralelo!

Considere, por ejemplo, que cada uno de los cuatro cálculos iniciales son independientes entre sí y pueden realizarse en paralelo. Los dos siguientes (que dan como resultado 6 y 9) pueden iniciarse una vez finalizados los cálculos de los que dependen, pero estos dos pueden además correr en paralelo.

Los 7 cálculos, paralelizados como arriba, podrían tomar tan solo el mismo tiempo 3 cálculos en serie.

En realidad, con una colección tan pequeña, el costo de sincronizar la computación sería lo suficientemente grande como para eliminar cualquier ganancia. Además, si dobla esto, solo tomaría 4 total de cálculos. Sin embargo, una vez que sus colecciones aumentan, comienza a ver algunas ganancias reales.

Considere, por otro lado, foldLeft. Debido a que no tiene la función adicional, no puede paralelizar ningún cálculo:

(((0 + "This".length) + "is".length) + "an".length) + "example".length

Cada uno de los paréntesis internos debe calcularse antes de que pueda continuar el externo.

La función agregada no hace eso (excepto que es una función muy general y podría usarse para hacer eso). Quieres groupBy. Cerca de al menos. Como comienzas con un Seq[(String, String)], y agrupa tomando el primer elemento de la tupla (que es (String, String) => String), devolvería un Map[String, Seq[(String, String)]). Luego debe descartar el primer parámetro en la Seq[String, String)] valores.

Entonces

list.groupBy(_._1).mapValues(_.map(_._2))

Ahí tienes un Map[String, Seq[(String, String)]. Si quieres un Seq en lugar de Map, llama toSeq en el resultado. Sin embargo, no creo que tenga una garantía sobre el pedido en la Seq resultante

---

El agregado es una función más difícil.

Considere primero reducirLeft y reducirRight. Dejar as ser una secuencia no vacía as = Seq(a1, ... an) de elementos de tipo A, y f: (A,A) => A ser una forma de combinar dos elementos de tipo A en uno. Lo notaré como un operador binario @, a1 @ a2 en vez de f(a1, a2). as.reduceLeft(@) calculará (((a1 @ a2) @ a3)... @ an). reduceRight pondrá el paréntesis al revés, (a1 @ (a2 @... @ an)))). Si @ resulta ser asociativo, a uno no le importan los paréntesis. Se podría calcular como (a1 @... @ ap) @ (ap+1 @[email protected]) (también habría paréntesis dentro de los 2 grandes paréntesis, pero eso no nos importa). Entonces uno podría hacer las dos partes en paralelo, mientras que el corchete anidado en reduceLeft o reduceRight fuerza un cálculo completamente secuencial. Pero el cálculo paralelo solo es posible cuando @ se sabe que es asociativo, y el método reduceLeft no puede saberlo.

Aún así, podría haber un método reduce, cuya persona que llama sería responsable de asegurar que la operación sea asociativa. Luego reduce ordenaría las llamadas como crea conveniente, posiblemente haciéndolas en paralelo. De hecho, existe tal método.

Sin embargo, existe una limitación con los diversos métodos de reducción. Los elementos de Seq solo se pueden combinar para obtener un resultado del mismo tipo: @ tiene que ser (A,A) => A. Pero uno podría tener el problema más general de combinarlos en un B. Uno comienza con un valor b de tipo By combinarlo con todos los elementos de la secuencia. El operador @ es (B,A) => By uno calcula (((b @ a1) @ a2) ... @ an). foldLeft hace eso. foldRight hace lo mismo pero comenzando con an. He aquí el @ la operación no tiene posibilidad de ser asociativa. Cuando uno escribe b @ a1 @ a2, debe significar (b @ a1) @ a2, como (a1 @ a2) estaría mal escrito. Así que foldLeft y foldRight tienen que ser secuenciales.

Supongamos, sin embargo, que cada A se puede convertir en un B, escribámoslo con !, a! es de tipo B. Supongamos además que hay un + operación (B,B) => B, y eso @ es tal que b @ a es de hecho b + a!. En lugar de combinar elementos con @, primero se podrían transformar todos en B con !, luego combínalos con +. Eso sería as.map(!).reduceLeft(+). Y si + es asociativo, entonces eso se puede hacer con reducir, y no ser secuencial: as.map (!). reduce (+). Podría haber un método hipotético como.associativeFold (b,!, +).

Agregado está muy cerca de eso. Sin embargo, puede ser que exista una forma más eficiente de implementar [email protected] que b+a! Por ejemplo, si escribe B es List[A], y [email protected] es a :: b, entonces a! estarán a::Nil, y b1 + b2 estarán b2 ::: b1. a :: b es mucho mejor que (a :: Nil) ::: b. Para beneficiarse de la asociatividad, pero seguir utilizando @, uno primero se divide b + a1! + ... + an!, dentro (b + a1! + ap!) + (ap+1! + ..+ an!), luego vuelva a usar @ con (b @ a1 @ an) + (ap+1! @ @ an). ¡Todavía se necesita el! en ap + 1, porque uno debe comenzar con algo b. Y el + sigue siendo necesario también, apareciendo entre los paréntesis. Para hacer eso, as.associativeFold(!, +) podría cambiarse a as.optimizedAssociativeFold(b, !, @, +).

De regreso +. + es asociativo, o equivalentemente, (B, +) es un semigrupo. En la práctica, la mayoría de los semigrupos utilizados en la programación también son monoides, es decir, contienen un elemento neutro. z (por cero) en B, de modo que para cada b, z + b = b + z = b. En ese caso, el ! operación que tiene sentido es probable que sea a! = z @ a. Además, como z es un elemento neutro b @ a1 [email protected] an = (b + z) @ a1 @ an cual es b + (z + a1 @ an). Por lo tanto, siempre es posible comenzar la agregación con z. Si b se quiere en cambio, lo haces b + result al final. Con todas esas hipótesis, podemos hacer uns.aggregate(z, @, +). Eso es lo que aggregate lo hace. @ es el seqop argumento (aplicado en un secuenciaz @ a1 @ a2 @ ap), y + es combop (aplicado a ya parcialmente conjunto resultados, como en (z + [email protected]@ap) + (z + [email protected]@an)).

En resumen, as.aggregate(z)(seqop, combop) calcula lo mismo que as.foldLeft(z)( seqop) siempre que

• (B, combop, z) es un monoide
• seqop(b,a) = combop(b, seqop(z,a))

La implementación agregada puede usar la asociatividad de combop para agrupar los cálculos como desee (sin intercambiar elementos, sin embargo, + no tiene que ser conmutativo, ::: no lo es). Puede ejecutarlos en paralelo.

Finalmente, resolviendo el problema inicial usando aggregate se deja como ejercicio al lector. Una pista: implemente usando foldLeft, entonces busca z y combo que satisfaga las condiciones indicadas anteriormente.

La firma de una colección con elementos de tipo A es:

def aggregate [B] (z: B)(seqop: (B, A) ⇒ B, combop: (B, B) ⇒ B): B 

• z es un objeto de tipo B que actúa como elemento neutro. Si desea contar algo, puede usar 0, si desea construir una lista, comience con una lista vacía, etc.
• segop es análogo a la función a la que le pasas fold métodos. Se necesitan dos argumentos, el primero es del mismo tipo que el elemento neutral que pasó y representa las cosas que ya se agregaron en la iteración anterior, el segundo es el siguiente elemento de su colección. El resultado también debe ser de tipo B.
• combop: es una función que combina dos resultados en uno.

En la mayoría de las colecciones, el agregado se implementa en TraversableOnce como:

  def aggregate[B](z: B)(seqop: (B, A) => B, combop: (B, B) => B): B 
    = foldLeft(z)(seqop)

Por lo tanto combop se ignora. Sin embargo, tiene sentido para colecciones paralelas, porqueseqop primero se aplicará localmente en paralelo, y luego combopse llama para finalizar la agregación.

Entonces, para su ejemplo, puede probar primero con un pliegue:

val seqOp = 
  (map:Map[String,Set[String]],tuple: (String,String)) => 
    map + ( tuple._1 -> ( map.getOrElse( tuple._1, Set[String]() ) + tuple._2 ) )


list.foldLeft( Map[String,Set[String]]() )( seqOp )
// returns: Map(one -> Set(i, 1), two -> Set(2, ii), four -> Set(iv))

Entonces tienes que encontrar una forma de colapsar dos multimaps:

val combOp = (map1: Map[String,Set[String]], map2: Map[String,Set[String]]) =>
       (map1.keySet ++ map2.keySet).foldLeft( Map[String,Set[String]]() )  
         (result,k) => 
           result + ( k -> ( map1.getOrElse(k,Set[String]() ) ++ map2.getOrElse(k,Set[String]() ) ) ) 
        

Ahora, puede usar el agregado en paralelo:

list.par.aggregate( Map[String,Set[String]]() )( seqOp, combOp )
//Returns: Map(one -> Set(i, 1), two -> Set(2, ii), four -> Set(iv))

Aplicar el método “par” a la lista, utilizando así la colección paralela (scala.collection.parallel.immutable.ParSeq) de la lista para aprovechar realmente los procesadores de múltiples núcleos. Sin “par”, no habrá ninguna ganancia de rendimiento ya que el agregado no se realiza en la colección paralela.

Comentarios y valoraciones de la guía

Te invitamos a añadir valor a nuestro contenido contribuyendo tu experiencia en las explicaciones.

---

---

Utiliza Nuestro Buscador