Scala 集合(四) 小咪咪 2022-04-15 05:20 110阅读 0赞 # Scala Builder、CanBuildFrom和Like特质 # Scala程序设计 第2版 - 原版.pdf 下载:[https://download.csdn.net/download/u014646662/10805074][https_download.csdn.net_download_u014646662_10805074] 1.Builder 2 CanBuildFrom 3 Like特质 对人工智能感兴趣的同学,可以点击以下链接: [现在人工智能非常火爆,很多朋友都想学,但是一般的教程都是为博硕生准备的,太难看懂了。最近发现了一个非常适合小白入门的教程,不仅通俗易懂而且还很风趣幽默。所以忍不住分享一下给大家。点这里可以跳转到教程。][Link 1] [https://www.cbedai.net/u014646662][Link 1] ## 1.Builder ## 我在前面几篇有关集合的文章中曾提到,如果小心合理地使用,可变集合将是为了提高性能而做出的合理让步。事实上,集合API 在内部使用了可变集合建立新的输出集合,如在map 操作中就是如此。map 操作还使用了collection.mutable.Builder 特征的实现,以构造新实例。 源码: package scala.collection.mutable trait Builder[-Elem, +To] extends scala.AnyRef with scala.collection.generic.Growable[Elem] { def +=(elem : Elem) : Builder.this.type def clear() : scala.Unit def result() : To def sizeHint(size : scala.Int) : scala.Unit = { /* compiled code */ } def sizeHint(coll : scala.collection.TraversableLike[_, _]) : scala.Unit = { /* compiled code */ } def sizeHint(coll : scala.collection.TraversableLike[_, _], delta : scala.Int) : scala.Unit = { /* compiled code */ } def sizeHintBounded(size : scala.Int, boundingColl : scala.collection.TraversableLike[_, _]) : scala.Unit = { /* compiled code */ } def mapResult[NewTo](f : scala.Function1[To, NewTo]) : scala.collection.mutable.Builder[Elem, NewTo] = { /* compiled code */ } } 这种罕见的Builder.this.type 签名是一个单例类型(singleton type)。它确保+= 方法在调用时只返回生Builder 的实例,也就是this。如果尝试返回Builder 的一个新实例,那么就无法通过类型检查。 接下来做一个List 的builder 实现: package cn.com.tengen.test.obj import collection.mutable.Builder class ListBuilder[T] extends Builder[T,List[T]]{ private var storage = Vector.empty[T] override def +=(elem:T) ={ storage = storage :+ elem this } override def clear(): Unit = { storage = Vector.empty[T] } override def result(): List[T] = storage.toList } object ListBuilder extends App{ val lb = new ListBuilder[Int] (1 to 10) foreach (i => lb += i) println(lb.result) } 输出结果: List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) ## 2 CanBuildFrom ## 做一个List调用map的例子: object Test extends App { var l = List(1, 2, 3, 4, 5, 6) l = l map (_ + 1) println(l) } 我们看一下map: 首先map方法来自于:List package scala.collection.immutable sealed abstract class List[+A]() extends scala.collection.AbstractSeq[A] ... { ... final override def map[B, That](f : scala.Function1[A, B])(implicit bf : scala.collection.generic.CanBuildFrom[scala.collection.immutable.List[A], B, That]) : That = { /* compiled code */ } ... } 结果发现map是被重写的,追根溯源 scala.collection.AbstractSeq[A] -> scala.collection.AbstractIterable[A] -> scala.collection.AbstractTraversable[A] -> scala.AnyRef with scala.collection.Traversable[A] -> scala.AnyRef with scala.collection.TraversableLike[A, scala.collection.Traversable[A]] 一层层的继承终于发现map源于TraversableLike package scala.collection trait TraversableLike[+A, +Repr] extends scala.Any with ... { ... def map[B, That](f : scala.Function1[A, B])(implicit bf : scala.collection.generic.CanBuildFrom[Repr, B, That]) : That = { /* compiled code */ } ... } scala.collection.immutable.List对map的重写实质上就是泛型更具体一点,接下来就简单的探讨一下TraversableLike中的map方法: Repr 是内部用来保存元素的集合类型。B 是函数f 创建的元素类型。That 是我们想要创建的目标集合的类型参数,它可能与输入的原始集合相同,也可能不同。 TraversableLike 对其子类(如List)一无所知,但它还是可以构造新的List 并将其返回,因为隐含的CanBuildFrom 实例封装了所需要的细节。 CanBuildFrom 是创建Builder 实例的工厂的trait,由工厂来完成实际构造新集合的工作。使用CanBuildFrom 技术的一个缺点是额外增加了方法签名的复杂度。然而,除了促进类似map 等操作在面向对象中的重用以外,CanBuildFrom 在其他方面使得构造更加模块化、通用化。 例如:CanBuildFrom 实例可以为返回的不同具体集合实例化多个Builder。通常它会返回相同类型的新集合,或者返回对给定元素来说更高效的子类型。 实现一个包含很多元素的映射表最好将键存储在散列表中,同时提供均为O(1) 的存储和查询复杂度。然而,对于一个小映射,可能将元素直接存在数组或列表中会更快,这时n 很小,O(n) 的查询复杂度事实上比散列表的O(1) 复杂度还要快,这取决于散列表的常数开销因子。 输入集合类型不能用来作为输出集合类型的情况还有其他形式。考虑下面的示例: object Test extends App { val set = collection.BitSet(1, 2, 3, 4, 5) println(set.getClass+": "+set) var s = set map (_ + "a") println(s.getClass+": "+s) } 输出: class scala.collection.immutable.BitSet$BitSet1: BitSet(1, 2, 3, 4, 5) class scala.collection.immutable.TreeSet: TreeSet(1a, 2a, 3a, 4a, 5a) 在命令行看一下: ![20181122133942627.png][] 在[https://blog.csdn.net/u014646662/article/details/84302437][https_blog.csdn.net_u014646662_article_details_84302437]已经介绍了BitSet集合,BitSet是非负整数的集合,Int加上String的结果是String,所以,如果将其元素转为字符串,隐含的CanBuildFrom 只能实例化不同于输入的输出集合。 在本例中, 输出集合是SortedSet。 类似地,对于字符串(字符序列),我们也可能遇到以下情形: ![20181122135235180.png][] CanBuildFrom 的另一个好处是传送其他上下文信息的能力,这些上下文信息可能是原集合不知道或不适合由原集合来传递的。例如:使用分布式计算API 时,特定的CanBuildFrom实例可能被用于构建那些适合序列化到远程进程的集合。 ## 3 Like特质 ## Builder 和CanBuildFrom 为输出集合指定了类型参数。为了支持对这些参数的指定,也为了加强代码重用,你知道的大多数集合都混入了相应的 \*Like 特质。该trait 可以添加合适的返回值类型,并为常见方法提供实现。 以下是collection.immutable.Seq 的声明: package scala.collection.immutable trait Seq[+A] extends scala.AnyRef with scala.collection.immutable.Iterable[A] with scala.collection.Seq[A] with scala.collection.generic.GenericTraversableTemplate[A, scala.collection.immutable.Seq] with scala.collection.SeqLike[A, scala.collection.immutable.Seq[A]] with scala.collection.Parallelizable[A, scala.collection.parallel.immutable.ParSeq[A]] { } 需要注意的是,collection.SeqLike 同时用元素类型A 和Seq\[A\] 本身进行参数化。第二个参数用于约束在map 等方法中能够使用的CanBuildFrom 实例。该trait 还实现了Seq 中大部分我们熟悉的方法。 SeqLike 源码: package scala.collection trait SeqLike[+A, +Repr] extends scala.Any with scala.collection.IterableLike[A, Repr] with scala.collection.GenSeqLike[A, Repr] with scala.collection.Parallelizable[A, scala.collection.parallel.ParSeq[A]] { protected[this] override def thisCollection : scala.collection.Seq[A] = { /* compiled code */ } protected[this] override def toCollection(repr : Repr) : scala.collection.Seq[A] = { /* compiled code */ } def length : scala.Int def apply(idx : scala.Int) : A protected[this] override def parCombiner : scala.collection.parallel.Combiner[A, scala.collection.parallel.ParSeq[A]] = { /* compiled code */ } def lengthCompare(len : scala.Int) : scala.Int = { /* compiled code */ } override def isEmpty : scala.Boolean = { /* compiled code */ } override def size : scala.Int = { /* compiled code */ } def segmentLength(p : scala.Function1[A, scala.Boolean], from : scala.Int) : scala.Int = { /* compiled code */ } def indexWhere(p : scala.Function1[A, scala.Boolean], from : scala.Int) : scala.Int = { /* compiled code */ } def lastIndexWhere(p : scala.Function1[A, scala.Boolean], end : scala.Int) : scala.Int = { /* compiled code */ } def permutations : scala.collection.Iterator[Repr] = { /* compiled code */ } def combinations(n : scala.Int) : scala.collection.Iterator[Repr] = { /* compiled code */ } def reverse : Repr = { /* compiled code */ } def reverseMap[B, That](f : scala.Function1[A, B])(implicit bf : scala.collection.generic.CanBuildFrom[Repr, B, That]) : That = { /* compiled code */ } def reverseIterator : scala.collection.Iterator[A] = { /* compiled code */ } def startsWith[B](that : scala.collection.GenSeq[B], offset : scala.Int) : scala.Boolean = { /* compiled code */ } def endsWith[B](that : scala.collection.GenSeq[B]) : scala.Boolean = { /* compiled code */ } def indexOfSlice[B >: A](that : scala.collection.GenSeq[B]) : scala.Int = { /* compiled code */ } def indexOfSlice[B >: A](that : scala.collection.GenSeq[B], from : scala.Int) : scala.Int = { /* compiled code */ } def lastIndexOfSlice[B >: A](that : scala.collection.GenSeq[B]) : scala.Int = { /* compiled code */ } def lastIndexOfSlice[B >: A](that : scala.collection.GenSeq[B], end : scala.Int) : scala.Int = { /* compiled code */ } def containsSlice[B](that : scala.collection.GenSeq[B]) : scala.Boolean = { /* compiled code */ } def contains[A1 >: A](elem : A1) : scala.Boolean = { /* compiled code */ } override def union[B >: A, That](that : scala.collection.GenSeq[B])(implicit bf : scala.collection.generic.CanBuildFrom[Repr, B, That]) : That = { /* compiled code */ } def diff[B >: A](that : scala.collection.GenSeq[B]) : Repr = { /* compiled code */ } def intersect[B >: A](that : scala.collection.GenSeq[B]) : Repr = { /* compiled code */ } def distinct : Repr = { /* compiled code */ } def patch[B >: A, That](from : scala.Int, patch : scala.collection.GenSeq[B], replaced : scala.Int)(implicit bf : scala.collection.generic.CanBuildFrom[Repr, B, That]) : That = { /* compiled code */ } def updated[B >: A, That](index : scala.Int, elem : B)(implicit bf : scala.collection.generic.CanBuildFrom[Repr, B, That]) : That = { /* compiled code */ } def +:[B >: A, That](elem : B)(implicit bf : scala.collection.generic.CanBuildFrom[Repr, B, That]) : That = { /* compiled code */ } def :+[B >: A, That](elem : B)(implicit bf : scala.collection.generic.CanBuildFrom[Repr, B, That]) : That = { /* compiled code */ } def padTo[B >: A, That](len : scala.Int, elem : B)(implicit bf : scala.collection.generic.CanBuildFrom[Repr, B, That]) : That = { /* compiled code */ } def corresponds[B](that : scala.collection.GenSeq[B])(p : scala.Function2[A, B, scala.Boolean]) : scala.Boolean = { /* compiled code */ } def sortWith(lt : scala.Function2[A, A, scala.Boolean]) : Repr = { /* compiled code */ } def sortBy[B](f : scala.Function1[A, B])(implicit ord : scala.math.Ordering[B]) : Repr = { /* compiled code */ } def sorted[B >: A](implicit ord : scala.math.Ordering[B]) : Repr = { /* compiled code */ } override def toSeq : scala.collection.Seq[A] = { /* compiled code */ } def indices : scala.collection.immutable.Range = { /* compiled code */ } override def view : scala.AnyRef with scala.collection.SeqView[A, Repr] = { /* compiled code */ } override def view(from : scala.Int, until : scala.Int) : scala.collection.SeqView[A, Repr] = { /* compiled code */ } override def toString() : _root_.scala.Predef.String = { /* compiled code */ } } object SeqLike extends scala.AnyRef { def indexOf[B](source : scala.collection.Seq[B], sourceOffset : scala.Int, sourceCount : scala.Int, target : scala.collection.Seq[B], targetOffset : scala.Int, targetCount : scala.Int, fromIndex : scala.Int) : scala.Int = { /* compiled code */ } def lastIndexOf[B](source : scala.collection.Seq[B], sourceOffset : scala.Int, sourceCount : scala.Int, target : scala.collection.Seq[B], targetOffset : scala.Int, targetCount : scala.Int, fromIndex : scala.Int) : scala.Int = { /* compiled code */ } } 简单总结一下: (1) 用Builder 抽象了构造。 (2) 用CanBuildFrom 提供隐含的工厂,用于构造适合给定上下文的生成器实例。 (3) Like 特征为Builder 和CanBuildFrom 添加必须的返回值类型参数,并提供大部分的方法实现。 [https_download.csdn.net_download_u014646662_10805074]: https://download.csdn.net/download/u014646662/10805074 [Link 1]: https://www.cbedai.net/u014646662 [20181122133942627.png]: /images/20220415/41c05e4f269a439c8248d826c8482568.png [https_blog.csdn.net_u014646662_article_details_84302437]: https://blog.csdn.net/u014646662/article/details/84302437 [20181122135235180.png]: /images/20220415/881480b8f27f43d8bbe6eec196c1042e.png
还没有评论,来说两句吧...