当前位置:必发365电子游戏 > 编程 > 借使大家能够动用并行算法的话
借使大家能够动用并行算法的话
2019-12-19

    在上意气风发节我们评论了Monoid的结合性和恒等值的意义以至Monoid怎么着与串类成分折叠算法相相称。但是大家只示范了一下底蕴项目(primitive type)Monoid实例的使用,所以上生龙活虎节的研究指标是理论多于实施。在此生机勃勃节大家将把首要放在一些实用综合项目(composite type)Monoid实例及Monoid的肤浅表达及函数组合工夫。

    Monoid的二元操作函数有所整合性子(associativity),与恒等值(identity)协同利用能够随心所欲选用左折叠或右折叠算法管理串类元素(List element)而拿到相像结果。所以接纳Monoid op大家得以吸收左折叠等于右折叠的定论:

左折叠:op(op(op(a,b),c),d)

右折叠:op(a,op(b,op(c,d)))

可是,假诺能够用并行算法的话就是:

并行算法:op(op(a,b卡塔尔(英语:State of Qatar),op(c,d卡塔尔(英语:State of Qatar))我们能够何况运算 op(a,b卡塔尔(قطر‎, op(c,d卡塔尔

风流罗曼蒂克旦我们得以选择并行算法的话,肯定能提升总结功能。试想假若大家对一个十分的大文件举行理文件字数总计可能寻觅最大值什么的,大家可以把这一个大文件分为若干小文件然后还要总计后再商量将节省数不胜数乘除时间。在现世大数目时代,数据文件不但大况且是布满在超多服务器上的。那么Monoid的特种定律就足以使数据处理相互运算,极其同盟大数量管理情势。

我们看看能还是无法促成像折叠算法似的并行算法:

1   def foldMapV[A,B](iseq: IndexedSeq[A])(m: Monoid[B])(f: A => B): B = {
2       if (iseq.isEmpty) m.zero
3       else if (iseq.length == 1) f(iseq(0))
4       else {
5           val (l, r) = iseq.splitAt(iseq.length / 2)
6           m.op(foldMapV(l)(m)(f), foldMapV(r)(m)(f))
7       }
8   }                                               //> foldMapV: [A, B](iseq: IndexedSeq[A])(m: ch10.ex2.Monoid[B])(f: A => B)B

嘿,那个foldMapV从表面,在类型款式上跟foldMap相似,差异的是中间具体达成方式;foldMapV循环把对象串进行分半。

构成前边对并行运算的座谈,大家用以下格局应该能够兑现互相之间运算吧:

1   def foldMapV[A,B](iseq: IndexedSeq[A])(m: Monoid[B])(f: A => B): B = {
2       if (iseq.isEmpty) m.zero
3       else if (iseq.length == 1) f(iseq(0))
4       else {
5           val (l, r) = iseq.splitAt(iseq.length / 2)
6           m.op(async(foldMapV(l)(m)(f)), async(foldMapV(r)(m)(f)))
7       }
8   }                                               //> foldMapV: [A, B](iseq: IndexedSeq[A])(m: ch10.ex2.Monoid[B])(f: A => B)B

好,大家下边找个例证来演示高阶类型Monoid实例和互相运算应用:用Monoid来落到实处对字串(List[String])的文字数计算。由于我们准备动用并行计算,对字串举办分半时会容许会现身一字分成两半的情况,所以需求自定义复杂一点的数据类型:

 1   trait WC 
 2   case class Stub(chars: String) extends WC  //chars 记录了未完整文字的字符
 3   case class Part(lStub: String, words: Int, rStub: String) extends WC   //lStub=左边文字结尾, words=完整字数,rStub=右边文字开头
 4   
 5   def wcMonoid: Monoid[WC] = new Monoid[WC] {
 6       def op(wc1: WC, wc2: WC): WC = {
 7           (wc1, wc2) match {
 8               case (Stub(l),Stub(r)) => Stub(l + r)
 9               case (Stub(lb),Part(le,w,rb)) => Part(lb+le,w,rb)
10               case (Part(le,w,rb),Stub(re)) => Part(le,w,rb+re)
11               case (Part(le,w,rb),Part(lb,w2,re)) => Part(le, w + (if((rb+lb).isEmpty) 0 else 1) + w2, re)
12           }
13       }
14       val zero = Stub("")
15   }

 Monoid[必发365电子游戏,WC]是个WC类型的Monoid实例,op(wc1,wc2卡塔尔(英语:State of Qatar)=wc3则把八个WC值拼凑起来产生另二个WC值。下边让大家用wcMonoid来兑现这些文字总计函数:

 1   def wordCount(ws: String): Int = {
 2     def wc(c: Char): WC = {
 3         if (c.isWhitespace) Part("",0,"")
 4         else Stub(c.toString)
 5     }
 6     def unstub(s: String) = s.length min 1
 7     
 8     foldMapV(ws.toIndexedSeq)(wcMonoid)(wc) match {
 9         case Stub(c) => 0
10         case Part(l,w,r) => unstub(l) + w + unstub(r)
11     }
12   }                                               //> wordCount: (ws: String)Int

 

用它来数个字数:

1   val words = "the brown fox     is running quickly."  //故意留点空格,标点符号什么的
2                                                   //> words  : String = the brown fox     is running quickly.
3   wordCount(words)                                //> res0: Int = 6 

没错!

再来一个例子:检查豆蔻梢头串数字是不是是有序的:

 1   def seqIsOrdered(iseq: IndexedSeq[Int]): Boolean = {
 2       val stateMonoid = new Monoid[Option[(Int, Int, Boolean)]] {    //状态:Option[(最小值,最大值,是排序)]
 3          def op(s1: Option[(Int,Int,Boolean)], s2: Option[(Int,Int,Boolean)]): Option[(Int,Int,Boolean)] = {
 4            (s1,s2) match {
 5               case (None, b) => b
 6               case (b, None) => b
 7               case (Some((x1,y1,b1)),Some((x2,y2,b2))) => Some(x1 min x2,y1 max y2, b1 && b2 && x2 >= y1)
 8            }
 9          }
10          val zero = None
11       }
12       foldMapV(iseq)(stateMonoid)(i => Some(i,i,true)) map (_._3) getOrElse true
13   }

1   seqIsOrdered(List(1,2,5,9,33).toIndexedSeq)     //> res0: Boolean = true
2   seqIsOrdered(List(1,2,5,0    ,33).toIndexedSeq)    //> res1: Boolean = false

在此个例子里大家用Option[min,max,ordered]作为当前场地并用stateMonoid来管理那么些意况。foldMapV参数(i => Some(i,i,true卡塔尔(قطر‎卡塔尔(英语:State of Qatar)正是行业内部的 A => B。还记得呢,大家扩张foldMap那几个函数是的目标是假设元素A未有Monoid实例,那么大家得以用Monoid[B]下一场用A =>B函数把A转成B技巧运用Monoid[B]。这里我们把 i转成Some(Int,Int,Boolean卡塔尔(قطر‎。

值得注意的是上述四个例证foldMapV历遍无论怎么样是不会中途退出的。那些特点把foldMapV的应用局限在必需消耗整个数据源的思索应用,如求和、最大值等等。对于其它一些渴求,如:A => Boolean这种要求,尽管第一个值就已经获得答案也亟须走完整串数据。

大家在事情发生前的章节里曾经切磋了有的数据结构如List,Stream,Tree等。当大家要求管理那么些布局中封装的成分时平时采纳部分算法如折叠算法。这种算法能保存数据布局。何况它们有共通性:都得以应用折叠算法。既然有共性,肯定就能够有深度抽象的上空,大家得以把它们抽象表完毕四个Foldable[F[_]]:List,Stream,Tree等数据结构类型正是F[_];多个数据构造中封装了某个成分。那几个Foldable类型可以包括种种历遍算法:

 1  def endoComposeMonoid[A] = new Monoid[A => A] {
 2       def op(f: A => A, g: A => A): A => A = f compose g
 3       val zero = (a: A) => a
 4   }
 5   def dual[A](m: Monoid[A]): Monoid[A] = new Monoid[A] {
 6       def op(a1: A, a2: A) = m.op(a2,a1)
 7       val zero = m.zero
 8   }
 9   trait Foldable[F[_]] {
10      def foldRight[A, B](as: F[A])(z: B)(f: (A, B) => B): B = {
11            foldMap(as)(endoComposeMonoid[B])(a => b => f(a,b))(z)
12      }
13      def foldLeft[A, B](as: F[A])(z: B)(f: (B, A) => B): B = {
14            foldMap(as)(dual(endoComposeMonoid[B]))(a => b => f(b,a))(z)
15      }
16      def foldMap[A, B](as: F[A])(mb: Monoid[B])(f: A => B): B = {
17            foldLeft(as)(mb.zero)((b,a) => mb.op(f(a),b))
18      }
19      def concatenate[A](as: F[A])(m: Monoid[A]): A = {
20         foldLeft(as)(m.zero)(m.op)
21      }
22   }

大家今后曾经获取了个Foldable抽象数据构造,它包括了四种折叠历遍算法。大家能够试着创制一些Foldable实例看看:

 1   object listFoldable extends Foldable[List] {
 2      override def foldRight[A, B](as: List[A])(z: B)(f: (A, B) => B): B = {
 3            as.foldRight(z)(f)
 4      }
 5      override def foldLeft[A, B](as: List[A])(z: B)(f: (B, A) => B): B = {
 6            as.foldLeft(z)(f)
 7      }
 8      override def foldMap[A, B](as: List[A])(mb: Monoid[B])(f: A => B): B = {
 9            as.foldLeft(mb.zero)((b,a) => mb.op(f(a),b))
10      }
11      override def concatenate[A](as: List[A])(m: Monoid[A]): A = {
12         as.foldLeft(m.zero)(m.op)
13      }
14   }
15   object indexedSeqFoldable extends Foldable[IndexedSeq] {
16      override def foldRight[A, B](as: IndexedSeq[A])(z: B)(f: (A, B) => B): B = {
17            as.foldRight(z)(f)
18      }
19      override def foldLeft[A, B](as: IndexedSeq[A])(z: B)(f: (B, A) => B): B = {
20            as.foldLeft(z)(f)
21      }
22      override def foldMap[A, B](as: IndexedSeq[A])(mb: Monoid[B])(f: A => B): B = {
23            as.foldLeft(mb.zero)((b,a) => mb.op(f(a),b))
24      }
25      override def concatenate[A](as: IndexedSeq[A])(m: Monoid[A]): A = {
26         as.foldLeft(m.zero)(m.op)
27      }
28   }
29   object StreamFoldable extends Foldable[Stream] {
30      override def foldRight[A, B](as: Stream[A])(z: B)(f: (A, B) => B): B = {
31            as.foldRight(z)(f)
32      }
33      override def foldLeft[A, B](as: Stream[A])(z: B)(f: (B, A) => B): B = {
34            as.foldLeft(z)(f)
35      }
36   }

再看看Tree foldable 实例:

 1  trait Tree[+A] 
 2   case class Leaf[A](value: A) extends Tree[A]
 3   case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]
 4   object TreeFoldable extends Foldable[Tree] {
 5       override def foldMap[A, B](as: Tree[A])(mb: Monoid[B])(f: A => B): B = {
 6           as match {
 7               case Leaf(a) => f(a)
 8               case Branch(l,r) => mb.op(foldMap(l)(mb)(f),foldMap(r)(mb)(f))
 9           }
10       }
11       override def foldRight[A, B](as: Tree[A])(z: B)(f: (A, B) => B): B = {
12           as match {
13               case Leaf(a) => f(a,z)     //恒等值定律 
14               case Branch(l,r) => foldRight(l)(foldRight(r)(z)(f))(f)
15           }
16       }
17       override def foldLeft[A, B](as: Tree[A])(z: B)(f: (B,A) => B): B = {
18           as match {
19               case Leaf(a) => f(z,b)
20               case Branch(l,r) => foldLeft(r)(foldLeft(l)(z)(f))(f)
21           }
22       }
23   }

能够看来TreeFoldable的完毕方式与List,Stream等串类数据类型有所分歧。那是因为Tree类型未有现有的折叠算法。再不怕Tree类型未有空值(唯有Leaf, Branch)。那天本性暗示着有些项目标Monoid是从没有过恒等值的。我们统称这么些项目为semigroup。

 Option的foldable与TreeFoldable很像:

 1   object OptionFoldable extends Foldable[Option] {
 2        override def foldMap[A, B](opt: Option[A])(mb: Monoid[B])(f: A => B): B = {
 3            opt match {
 4                case None => mb.zero
 5                case Some(a) => f(a)
 6            }
 7        }
 8     override def foldRight[A, B](opt: Option[A])(z: B)(f: (A, B) => B): B = {
 9      opt match {
10          case None => z
11          case Some(a) => f(a,z)
12      }
13     }
14     override def foldLeft[A, B](opt: Option[A])(z: B)(f: (B,A) => B): B = {
15         opt match {
16             case None => z
17             case Some(a) => f(z,a)
18         }
19     }
20   }

 

实则任何可折叠的数据类型都能够被调换来List类型,因为大家能够用折叠算法重新整合List:

 1  trait Foldable[F[_]] {
 2      def foldRight[A, B](as: F[A])(z: B)(f: (A, B) => B): B = {
 3            foldMap(as)(endoComposeMonoid[B])(a => b => f(a,b))(z)
 4      }
 5      def foldLeft[A, B](as: F[A])(z: B)(f: (B, A) => B): B = {
 6            foldMap(as)(dual(endoComposeMonoid[B]))(a => b => f(b,a))(z)
 7      }
 8      def foldMap[A, B](as: F[A])(mb: Monoid[B])(f: A => B): B = {
 9            foldLeft(as)(mb.zero)((b,a) => mb.op(f(a),b))
10      }
11      def concatenate[A](as: F[A])(m: Monoid[A]): A = {
12         foldLeft(as)(m.zero)(m.op)
13      }
14      def toList[A](as: F[A]): List[A] = {
15          foldRight(as)(Nil: List[A]){_ :: _}
16      }
17   }

Monoid的函数组合技术也挺有趣:假如大家有Monoid[A], Monoid[B],那我们就足以把它们组合成Monoid[(A,B)]:

1   def productMonoid[A,B](ma: Monoid[A], mb: Monoid[B]): Monoid[(A,B)] = new Monoid[(A,B)] {
2       def op(x: (A,B), y: (A,B)) = (ma.op(x._1, y._1), mb.op(x._2,y._2))
3       val zero = (ma.zero, mb.zero)
4   }                                               //> productMonoid: [A, B](ma: ch10.ex2.Monoid[A], mb: ch10.ex2.Monoid[B])ch10.e
5                                                   //| x2.Monoid[(A, B)]

 大家能够用那些组成的Monoid在历遍一个List时还要总结List长度及和:

1  val pm = productMonoid(intAdditionMonoid,intAdditionMonoid)
2                                                   //> pm  : ch10.ex2.Monoid[(Int, Int)] = ch10.ex2$$anonfun$main$1$$anon$6@614c55
3                                                   //| 15
4   listFoldable.foldMap(List(1,2,3,4))(pm)(a => (1, a))
5                                                   //> res0: (Int, Int) = (4,10)

在历遍进度中我们把List各个节点成分值转成风流倜傥对值 a => (1, a卡塔尔,然后分别对每一种成员推行intAdditionMonoid的op操作。

下边剩下的日子大家再谈谈一些较复杂的Monoid:

只要二个函数的结果是Monoid,大家能够完成这些函数的Monoid实例:

1   def functionMonoid[A,B](mb: Monoid[B]): Monoid[A => B] = new Monoid[A => B] {
2       def op(f: A => B, g: A => B): A => B = a => mb.op(f(a),g(a))
3       val zero: A => B = a => mb.zero 
4   }

贯彻这些Monoid实例的应该尽量从品种相配入手:函数A => B的结果是B;大家有Monoid[B],Monoid[B].op(b,b)=>b。

借使大家能够动用并行算法的话。再来一个归并key-value Map的Monoid实例:就算我们有value类型的Monoid实例就足以实现:

1   def mapMergeMonoid[K,V](mv: Monoid[V]): Monoid[Map[K,V]] = new Monoid[Map[K,V]] {
2        val zero = Map()
3       def op(ma: Map[K,V], mb: Map[K,V]): Map[K,V] = {
4           ma.map {
5               case (k,v) => (k, mv.op(v, mb get(k) getOrElse mv.zero ))
6           }
7       }
8   }

有了这么些Monoid实例,大家就足以管理Map的嵌入表明式了:

 1   val M: Monoid[Map[String, Map[String, Int]]] = mapMergeMonoid(mapMergeMonoid(intAdditionMonoid))
 2   M: Monoid[Map[String, Map[String, Int]]] = $anon$1@21dfac82
 3   
 4  val m1 = Map("o1" -> Map("i1" -> 1, "i2" -> 2))
 5  m1: Map[String,Map[String,Int]] = Map(o1 -> Map(i1 -> 1, i2 -> 2))
 6  
 7  val m2 = Map("o1" -> Map("i2" -> 3))
 8  m2: Map[String,Map[String,Int]] = Map(o1 -> Map(i2 -> 3))
 9  
10  val m3 = M.op(m1, m2)
11  m3: Map[String,Map[String,Int]] = Map(o1 -> Map(i1 -> 1, i2 -> 5))

最后,大家试着用mapMergeMonoid实例来落到实处frequencyMap:总括输入List里的文字开掘次数。假设用叁个例证来申明的话,看看上面那几个风度翩翩串文字转成key-value Map:

Vector("a rose", "is a", "rose is", "a rose") >>> Map(a -> 3, rose -> 3, is -> 2)

那不正是搜索引擎中的索引比重算法吗?我们用foldMapV和mapMergeMonoid能够并行运算收拾索引,那算是Monoid的骨子里运用之黄金年代。

我们看看现实落实:

1 def frequencyMap[A](as: IndexedSeq[A]): Map[A, Int] =
2   foldMapV(as, mapMergeMonoid[A, Int](intAddition))((a: A) => Map(a -> 1))

1 frequencyMap(Vector("a rose", "is a", "rose is", "a rose"))
2 res0: Map[String,Int] = Map(a -> 3, rose -> 3, is -> 2)

 

 

 

 

 

 

 

 

 

 

上一篇:没有了
下一篇:没有了