Exemple de la Scala fonction d'agrégation

La fonction d'agrégation ne pas le faire (sauf que c'est une fonction très générale, et il pourrait être utilisé pour le faire). Vous souhaitez groupBy. Près de au moins. Que vous commencez avec un Seq[(String, String)], et vous groupe en prenant le premier élément du tuple (qui est (String, String) => String), il serait de retour d'un Map[String, Seq[(String, String)]). Ensuite, vous avez à jeter le premier paramètre de la Seq[String, String)] valeurs.

Donc

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

Là, vous obtenez un Map[String, Seq[(String, String)]. Si vous voulez un Seq au lieu de Map, appel toSeq sur le résultat. Je ne pense pas que vous avez une garantie sur le bon de commande dans la Seq si

Globale est plus difficile de fonction.

Considérons d'abord reduceLeft et reduceRight.
Laissez as être non vide séquence as = Seq(a1, ... an) d'éléments de type A, et f: (A,A) => A avoir un moyen de combiner les deux éléments de type A en un seul. Je note comme un opérateur binaire @, a1 @ a2 plutôt que f(a1, a2). as.reduceLeft(@) permettra de calculer (((a1 @ a2) @ a3)... @ an). reduceRight va mettre les parenthèses dans l'autre sens, (a1 @ (a2 @... @ an)))). Si @ arrive à être associatif, on ne se soucie pas de parenthèses. On pourrait le calculer comme (a1 @... @ ap) @ (ap+1 @...@an) (il y aurait parenthèse à l'intérieur de la 2 grande parenthèse de trop, mais ne soyons pas de soins à ce sujet). Ensuite, on peut faire les deux parties en parallèle, tandis que le imbriquée bracketing en reduceLeft ou reduceRight force entièrement calcul séquentiel. Mais le calcul parallèle n'est possible que lorsque @ est connu pour être associative, et de la reduceLeft méthode ne peut pas le savoir.

Encore, il pourrait être la méthode reduce, dont l'appelant est responsable de s'assurer que l'opération est associative. Puis reduce l'ordre des appels comme il l'entend, éventuellement de les faire en parallèle. En effet, il y a une telle méthode.

Il y a une limitation au niveau des différents réduire méthodes cependant. Les éléments de la Seq ne peut être combiné à un résultat du même type: @ doit être (A,A) => A. Mais on pourrait avoir le problème plus général de de les combiner en un B. On commence avec une valeur b de type B, et les combiner avec tous les éléments de la séquence. L'opérateur @ est (B,A) => B, et on calcule (((b @ a1) @ a2) ... @ an). foldLeft le fait. foldRight fait la même chose mais en commençant par la an. Là, le @ opération n'a aucune chance d'être associative. Quand on écrit b @ a1 @ a2, il doit signifier (b @ a1) @ a2, comme (a1 @ a2) serait mal tapé. Donc foldLeft et foldRight être séquentielle.

Supposons, cependant, que chaque A peut être transformé en un B, nous allons l'écrire avec !, a! est de type B. Supposons en outre qu'il y a un + opération (B,B) => B, et que @ est telle que b @ a est en fait b + a!. Plutôt que de combiner des éléments avec @, on pourrait tout d'abord transformer tous à B avec !, puis de les combiner avec +. Que serait as.map(!).reduceLeft(+). Et si + est associative, alors cela peut être fait avec les réduire, et de ne pas être séquentielle: comme.la carte(!).réduire(+). Il pourrait y avoir une méthode hypothétique comme.associativeFold(b, !, +).

Globale est très proche de celle. Il se peut cependant qu'il existe un moyen plus efficace de mettre en œuvre b@a que b+a! Par exemple, si le type B est List[A], et b@a est un::b, puis a! sera a::Nil, et b1 + b2 sera b2 ::: b1. a::b est meilleur que celui de (a::Néant:::b. Pour bénéficier de l'associativité, mais toujours utiliser @, on divise b + a1! + ... + an!, en (b + a1! + ap!) + (ap+1! + ..+ an!), puis revenir en arrière à l'aide de @ avec (b @ a1 @ an) + (ap+1! @ @ an). On a besoin encore de la ! sur ap+1, parce que l'on doit commencer avec quelques b. Et le + est encore nécessaire, apparaissant entre la parenthèse. Pour ce faire, as.associativeFold(!, +) pourrait être changé pour as.optimizedAssociativeFold(b, !, @, +).

Retour à +. + est associatif ou, de manière équivalente, (B, +) est un semigroup. Dans la pratique, la plupart des semigroups utilisé dans la programmation arriver à être monoids trop, je.e ils contiennent un élément neutre z (pour zéro) dans B, de sorte que, pour chaque b, z + b = b + z = b. Dans ce cas, le ! opération qui font sens est susceptible d'être a! = z @ a. En outre, comme z est un élément neutre b @ a1 ..@ an = (b + z) @ a1 @ an qui est b + (z + a1 @ an). Donc est est toujours possible de démarrer l'agrégation avec z. Si b est voulu au lieu de cela, vous ne b + result à la fin. Avec toutes ces hypothèses, nous pouvons faire uns.aggregate(z, @, +). C'est ce que aggregate n'. @ est le seqop argument (appliquée dans un séquence z @ a1 @ a2 @ ap), et + est combop (appliqué à déjà partiellement combiné résultats, comme dans (z + a1@...@ap) + (z + ap+1@...@an)).

Pour résumer, as.aggregate(z)(seqop, combop) calcule la même chose que as.foldLeft(z)( seqop) à condition que

• (B, combop, z) est un monoïde
• seqop(b,a) = combop(b, seqop(z,a))

globale de mise en œuvre peuvent utiliser l'associativité de l'combop de groupe les calculs qu'elle aime (pas la permutation des éléments toutefois, + n'a pas à être commutative, ::: n'est pas). Il peut s'exécuter en parallèle.

Enfin, la résolution du problème initial à l'aide de aggregate est laissé comme exercice au lecteur. Une astuce: mettre en œuvre à l'aide de foldLeft, puis de trouver z et combo qui permettront de satisfaire aux conditions énoncées ci-dessus.

La signature d'une collection d'éléments de type A est:

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

• z est un objet de type B agissant d'un élément neutre. Si vous voulez compter quelque chose, vous pouvez utiliser 0, si vous voulez construire une liste, commencer avec une liste vide, etc.
• segop est analoguous à la fonction que vous passez à fold méthodes. Elle prend deux arguments, la première est du même type que l'élément neutre que vous avez passé et de représenter les choses qui était déjà agrégées sur l'itération précédente, le second est le prochain élément de votre collection. Le résultat doit également par type de B.
• combop: est une fonction de la combinaison de deux résultats dans une.

Dans la plupart des collections, le total est de la mise en œuvre dans TraversableOnce comme:

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

Ainsi combop est ignoré. Cependant, il est logique en parallèle des collections, parce queseqop sera d'abord appliqué localement en parallèle, puis combopest appelé à terminer l'agrégation.

Donc, pour votre exemple, vous pouvez essayer avec un pli premier:

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

Alors vous devez trouver un moyen de s'effondrer deux 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]() ) ) ) 
       } 

Maintenant, vous pouvez utiliser l'ensemble en parallèle:

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

Application de la méthode "par" à la liste, donc à l'aide de la collection parallèle(scala.collection.en parallèle.immuable.ParSeq) de la liste pour vraiment profiter de la multi processeurs. Sans "au pair", il n'y aura pas de gain de performance puisque le total n'est pas fait sur la collection parallèle.

Voici le blog sur la façon globale activer les performances sur le multi cœurs de processeur avec banc de la marque.
http://markusjais.com/scalas-parallel-collections-and-the-aggregate-method/

Voici une vidéo sur la "Scala parallèle des collections" parler de "Scala Jours 2011".
http://days2011.scala-lang.org/node/138/272

La description de la vidéo

Scala Parallèle Des Collections

Aleksandar Prokopec

Parallèle de la programmation des abstractions de plus en plus important à mesure que le nombre de cœurs de processeur augmente. Une programmation de haut niveau permet au programmeur de se concentrer davantage sur le programme, et moins sur les détails de bas niveau comme la synchronisation et l'équilibrage de charge. Scala parallèle des collections d'étendre le modèle de programmation de la Scala cadre de collecte, de fournir en parallèle des opérations sur des ensembles de données.
Parler de décrire l'architecture de la collection parallèle cadre, en expliquant leur mise en œuvre et les décisions de conception. Béton collection implémentations en parallèle de hachage cartes et parallèle de hachage essaie seront décrites. Enfin, plusieurs exemples d'applications seront présentés, démontrant le modèle de programmation dans la pratique.

Juste pour clarifier les explications de ceux qui avant moi, en théorie, l'idée est que
total devrait fonctionner comme ça, (j'ai changé les noms des paramètres pour les rendre plus claire):

Seq(1,2,3,4).aggragate(0)(
     addToPrev = (prev,curr) => prev + curr, 
     combineSums = (sumA,sumB) => sumA + sumB)

Devrait logiquement se traduire aux

Seq(1,2,3,4)
    .grouped(2) //split into groups of 2 members each
    .map(prevAndCurrList => prevAndCurrList(0) + prevAndCurrList(1))
    .foldLeft(0)(sumA,sumB => sumA + sumB)

Parce que l'agrégation et la cartographie sont séparés, la liste d'origine pourrait théoriquement être divisés en différents groupes de différentes tailles et exécuter en parallèle, ou même sur une autre machine.
Dans la pratique scala implémentation actuelle ne prend pas en charge cette fonctionnalité par défaut, mais vous pouvez le faire dans votre propre code.