单词count统计这个经典的问题可以算得上是Spark大数据统计的 hello world问题，但是，打蚊子何需动用Spark这门大炮。鉴于Spark是基于Scala的，我们就用Scala本身来实现这个经典的问题，从而达到举一反三的目的。

val str = "hello world,Hello scala"
val split1 = str.split(" ")
var split2 = split1.flatMap(_.split(","))
val res = split2.map(_.toLowerCase()).map((_,1)).groupBy(_._1).map(kv=>(kv._1,kv._2.size))
res.foreach(println)

因为字符串中包含两种分隔符，所以先用空格符进行第一次分割，这时split1是一个string类型的java原生数组，然后再用逗号进行第二次分割，这时需要注意，如果用普通的map去循环分割，最后split2会得到一个二位数组，增加计算的复杂度，所以flatMap上场了，分割后仍然是一个一维数组，相当于在原基础上把数组压平了，后面会对flatMap进行重新实现，以便对其的作用有一个更直观的理解。

这时的split2看起来是这个样子的

List(hello,world,Hello,scala)

因为还涉及到大小写，所以对其进行小写转换，再转换成对偶元祖，经过两次map操作后，这是的临时数据看起来是这样的

List((hello,1),(world,1),(hello,1),(scala,1))

然后使用groupBy进行分组，_._1表示进行归并分组，最后返回得到一个map，键名用每个元祖的第一个元素

Map(‘scala’->List((scala,1)),’world’->List((world,1)),’hello’->List((hello,1),(hello,1))

最后再进行修饰，只取长度值

Map(‘scala’->1,’world’->1,’hello’->2)

得到我们想要的统计结果。下面是flatMap的实现代码

def flatMap(arr:Array[String]): Array[String] ={
  var res = Array[String]()
  val temp = arr.map(_.split(","))
  temp.foreach((v)=>{
    v.foreach(v2=>{res = res :+ v2})
  })
  res
}

这里只给出了一个简单实现，系统的实现比这要复杂很多，读者可自行阅读SDK里的实现源码

附:（请一定要看完）

经过思考发现，groupBy只要传入一个函数参数即可对系列进行分组，那么为什么一定要把List的元素转化为元组再进行groupBy呢？直接groupBy可以不可以，其实是可以的。代码如下

split2.map(_.toLowerCase()).groupBy(v=>v).map(v=>(v._1,v._2.size))

这是精简后的代码，直接使用元素本身来进行分组，值得注意的是，这里的groupBy没法简写成groupBy(_)，但是却可以写成这样

groupBy(_*1)

目测简写为下划线后还需要跟其他操作符（点操作符或者四则运算）,不过具体细节需要阅读源码才能知晓其中的微妙了

网上针对这个例子大多是进行了元组转换操作，其实大可不必，而且也不太好理解，可见独立的深度思考非常重要，不可人云亦云

最后强烈建议新手不要随意使用简写形式，先按常规形式写全函数表达式，在可能的基础上再进行缩写，否则陡峭的Scala学习曲线会让你挫败感顿生。

(完结）

众所周知在很多面向对象的语言中，抽象类都是不可以直接实例化的，必须另写一个类继承实现这个抽象类之后再实例化这个子类，Scala也不例外。

abstract class Car{
  def drive()
  def color
}

val car1 = new Car {}

这段代码是无法编译通过的，因为在Scala中，无论是抽象类和特质，只要存在没有实现的方法或属性，都是无法直接实例化的。注意，这里提到了没有实现的方法和属性，可以看下面的代码

trait Car{
  def drive() = {}

  def color = "red"
}

val car1 = new Car {}

上面这段代码是可以编译通过的，因为虽然它是特质，但是方法和属性都实现了，就可以当作普通类来实例化

如果有时候的确需要直接实例化 “没有实现方法的抽象类或特质”，该怎么办呢？这就引出了今天的主角——匿名子类，用法如下

abstract class Car{
  def drive()
  def color
}

val car1 = new Car {
  override def drive(): Unit = {
    println("drive")
  }
  override var color = "red"
}

在new关键词后面直接跟上方法和属性的实现代码就可以了

匿名子类可以极大提高代码的灵活性，Scala中有广泛应用，如下所示

implicit val ord = new Ordering[String] {
  override def compare(x: String, y: String) : Int = {
    y.compareTo(x)
  }
}

val arr = Array("a", "g", "F", "B", "c")
val sortedArr = arr.sorted
sortedArr.foreach(println)

这段代码对array的元素进行排序，sorted会传入一个隐式参数，而这个隐式参数 ord 就是特质Ordering的一个匿名子类（实现了compare方法），其中compare可由开发者自行实现符合自己排序的逻辑，这也是精髓所在。

package com.datacrafts.digitalevers.test

class binaryFind(in:Array[Int]) {
  val src:Array[Int] = in

  /**
   * 给定一个整数 
   * 使用二分查找它在顺序数列中的位置
   * @param in
   * @return
   */
  def find(in:Int): Int = {
    var start_index = 0
    var end_index = src.length - 1
    var curr_index = (start_index + end_index) / 2
    //需要探测边界 否则无法检索到
    if(src(start_index) == in){
      return start_index
    }
    if(src(end_index) == in){
      return end_index
    }
    //查找中位数 如果没有查找到 继续循环这一过程 当开始节点靠近尾节点则跳出循环
    while(src(curr_index) != in && ((end_index - start_index) > 1)){
      if(src(curr_index) > in){
        end_index = curr_index
      } else {
        start_index = curr_index
      }
      curr_index = (start_index + end_index) / 2
    }
    //循环结束还没找到 说明不存在这一节点 以返回-1标识
    if(src(curr_index) != in){
      return -1
    }
    //查找到则返回该节点index索引
    curr_index
  }
}

object binaryFind{
  def main(args: Array[String]): Unit = {
    val bf = new binaryFind(Array(10,11,12,20))
    println(bf.find(21))
  }
}

上述算法对头尾节点进行了一次特殊的探测处理，因为如果目标值刚好落在头尾节点，最后当头尾节点相互靠近的时候，该算法的中间节点可能无法移动（会一直停留在头节点）从而导致死循环。为了避免死循环，故加上了靠近退出循环机制，但最后可能会无法查找到这个目标节点。

这种为特殊情况而加的代码处理使得整个算法看起来不再是一个“优秀”的算法，后来读到《编程珠玑》的算法，很巧妙地规避了这个问题——该书采取了将中间节点curr_index移动一位的做法，如果目标值比中间节点大，则curr_index往大方向移动一位，如果小，则反之往小的方向移动一位。这很好理解，也是很正确的做法。既然中间节点不是目标值，那为何还要将其作为新的起始节点呢

这种新算法不存在中间节点最后不移动的问题，所以也就不需要再对头尾节点进行探测处理了，并且也不需要再设置头尾节点靠近则退出循环的机制

精简后的代码如下

package com.datacrafts.digitalevers.test

class binaryFind(in:Array[Int]) {
  val src:Array[Int] = in

  /**
   * 给定一个整数
   * 使用二分查找它在顺序数列中的位置
   * @param in
   * @return
   */
  def find(in:Int): Int = {
      var start_index = 0
      var end_index = src.length - 1
      var curr_index = 0

      //查找中位数 如果没有查找到 继续循环这一过程 当开始节点靠近尾节点则跳出循环
      while(start_index <= end_index){
        curr_index = (start_index + end_index) / 2
        if(src(curr_index) > in){
          end_index = curr_index - 1
        } else if(src(curr_index) < in) {
          start_index = curr_index + 1
        } else {
          return curr_index
        }
      }
      //循环结束还没找到 说明不存在这一节点 以返回-1标识
      -1
  }
}

object binaryFind {
  def main(args: Array[String]): Unit = {
    val bf = new binaryFind(Array(10,11,12,20))
    println(bf.find(12))
  }
}

scala实现对象序列化反序列化比较简单，将需要操作的类继承或混入 Serializable 类之后再使用java的输入输出流函数即可完成，实际上 Serializable 类也只是简单继承了 java 的 Serializable 接口

trait Serializable extends Any with java.io.Serializable

先看一个例子，代码在Scala2.12.10下编译通过

package com.datacrafts.digitalevers.test

import java.io.{FileInputStream, FileOutputStream, ObjectInputStream, ObjectOutputStream}

@SerialVersionUID(1L)
class Person(private val name:String,private val age:Int) extends Serializable {

  override def toString: String = {
      name+"-"+age
  }

  def getName1: String = {
    name
  }
}

object test{
  def main(args: Array[String]): Unit = {

    val p = new Person("zhangsan",12)
    val out = new ObjectOutputStream(new FileOutputStream("person.obj"))
    out.writeObject(p)
    out.close()

    val in = new ObjectInputStream(new FileInputStream("person.obj"))
    val person = in.readObject()
    println(person)
    println(person.asInstanceOf[Person].getName1)
    in.close()
  }
}

输出

zhangsan-12

zhangsan

需要注意的点

1.@SerialVersionUID(1L)是固定语句，不能更改，否则编译报错

2.Person类需要继承 Serializable， 如果Person有父类，则使用with混入Serializable

3.需要实现重载 toString 方法，可以直接返回一个空字符串 “”

4.反序列化之后打印输出对象会直接调用重载后的 toString 方法进行输出

5.如果要执行对象的方法，使用asInstanceOf先将类型转为原类型Person，再调用对象方法

所以举一反三，可以看到 Scala SDK底层的很多数据结构都有混入Serializable，说明这些数据结构都是可以序列化反序列化的，以ArrayStack（基于Array的栈结构）为例

@SerialVersionUID(8565219180626620510L)
class ArrayStack[T] private(private var table : Array[AnyRef],
                            private var index : Int)
extends AbstractSeq[T]
   with IndexedSeq[T]
   with IndexedSeqLike[T, ArrayStack[T]]
   with GenericTraversableTemplate[T, ArrayStack]
   with IndexedSeqOptimized[T, ArrayStack[T]]
   with Cloneable[ArrayStack[T]]
   with Builder[T, ArrayStack[T]]
   with Serializable

可以在类定义的继承关系最后看到有混入Serializable，并且在定义开头看到@SerialVersionUID 这个ID值是否为编译器默认固定的值

下面给出一个序列化反序列化 ArrayStack 的实际例程

import scala.collection.mutable

var as = new mutable.ArrayStack[Int]
as.push(1)
as.push(12)
val out = new ObjectOutputStream(new FileOutputStream("stack.obj"))
out.writeObject(as)
out.close()

val in = new ObjectInputStream(new FileInputStream("stack.obj"))
val stack = in.readObject()
println(stack)
in.close()

打印输出 //ArrayStack(12, 1)

和很多面向对象语言一样，有private修饰的属性和方法都只能在类内部访问，实例化后的对象无法直接访问。但是由于Scala增加了伴生对象这样一个概念，所以事情有了一些微妙的变化。实际上，伴生对象对类内资源的访问权限介于类本身和类外部之间，而private[this]就是用来操控这一切的关键

name被IDE标红了，说明无法访问，但是如果把object Animal改成object Person，即Person类的伴生对象，事情就不一样了

标红消失，可以正常访问。

如果这时在name属性上加上 [this]修饰，就相当于拿掉了伴生对象这一特殊权限，仅限类内部使用的权限。如下

更新: 由 private 关键词修饰的成员可以在 伴生类class 和 伴生对象object（两者同名）之间互相访问，但是加上[this]修饰后，便约束了只能在 class 或 object 内部访问了，实际上是缩减了成员的访问范围

接上一篇的QuickUnion算法，篇末曾提及该算法不适合大规模化的运算场景，因为在某些情况下会构造一棵很深的树，比如下面这种情况:

    val qu = new quickUnion
    qu.union(0,1)
    qu.union(1,2)
    qu.union(2,3)
    qu.union(3,4)
    qu.union(4,5)
    qu.union(5,6)
    qu.union(6,7)
    qu.union(7,8)
    for (elem <- qu.arr) {
      print(elem)
    }

如果要比较 0和9两个节点的连通性

qu.connect(0,9)

需要遍历了整棵树，从节点0一直检索到节点8，之所以会造成这种局面，主要是因为我们默认 union 函数的第一个参数的根节点作为子节点，第二个参数的根节点作为父节点，如果左边参数是一颗更深的树，右边参数是一棵小树。这样相当于是将一棵大树挂载到一棵小树上，使得深度不断加大，同时也不断加大算法的时间度。

对此我们的优化建议是，不再强制左右参数谁是父节点，谁作为子节点，而是依据两者树的深度，确保一直是把小树挂载到大树下，从而最大限度限制树深度的递增。于是我们额外维护一个数组 arrTreeLevel ，里面存放每个根节点的树的深度，如果该节点已经作为子节点挂载到其他节点下，则置为0。

如果两棵树的深度一致，则自增1，如果一方大，另一方小，则小的作为子节点，大的作为根节点，深度保持不变。所以只要对 union 函数稍作修改即可，其他程序不需要改动，全部代码如下:

package com.datacrafts.digitalevers.algorithm

class quickUnion {

    val  arrTreeLevel:Array[Int] = new Array[Int](10)

    val arr:Array[Int] = new Array[Int](10)
    for(i <- 0 to 9){
      arr(i) = i
      arrTreeLevel(i) = 1
    }

  /**
   * 查找根节点
   * @param p 待查找的节点索引
   * @return 根节点索引
   */
  def root(p:Int): Int = {
      var root = p
      while (root != arr(root)){
        root = arr(root)
      }
      root
  }

  /**
   * 查看两个节点是否连通
   * 连通 true 否则false
   * @param p 待查询的p节点索引
   * @param q 待查询的q节点索引
   */
  def connect(p:Int,q:Int): Boolean ={
    if(root(p) == root(q)) true else false
  }

  /**
   * 连通两个节点
   * @param p 连接者节点
   * @param q 待连接者节点
   */
  def union(p:Int,q:Int): Unit ={
    val root_p = root(p)
    val root_q = root(q)
    if(root_p != root_q){
      if(arrTreeLevel(root_q) >= arrTreeLevel(root_p)) {
        arr(root_p) = root_q
        if(arrTreeLevel(root_q) == arrTreeLevel(root_p)){
          arrTreeLevel(root_q) += 1
        }
        arrTreeLevel(root_p) = 0
      } else {
        arr(root_q) = root_p
        arrTreeLevel(root_q) = 0
      }
    }
  }
}

object quickUnionDemo{
  def main(args: Array[String]): Unit = {
    val qu = new quickUnion
    qu.union(0,1)
    qu.union(1,2)
    qu.union(2,3)
    qu.union(3,4)
    qu.union(4,5)
    qu.union(5,6)
    qu.union(6,7)
    qu.union(7,8)
    for (elem <- qu.arr) {
      print(elem)
    }                       //0524886789
    println()
    println(qu.connect(0,9))  //false
  }
}

附:《算法》一书中是采取比较树节点数量大小的方式来决定谁是子节点，谁是根节点，然后再“压平”来减少树的深度。笔者认为，直接跟踪树的深度更加直观，读者可自行判断

我们紧接着前一篇的QuickFind继续探讨，因为QuickFind采用连通状态设置值相等的算法，每一次操作都需要遍历整个数据表，并可能有大量的赋值操作，有没有一种稍微优化的算法，这就是这篇需要研究的QuickUnion

QuickUnion 不再将数组的各个节点看作平级，而是构造一种树状结构。其核心思想是

1.将父节点的索引值填充到当前节点中，而不是用节点本身的值去覆盖

2.构造的数组元素在不存在父子关系的时候，索引值等于节点值，比如第0号元素等于0，第2号元素等于2（数组索引从0开始）

当我们进行第一次union操作时，比如要第3号元素和第4号元素进行合并，将3号元素挂载在4号元素下面，我们把4号元素的索引值4写入第3号元素，表示第3号元素的父节点的位置在第4个位置上，整个数组结构变成如下

这样，当我们查看到第3号元素的时候，发现他的值不是3，说明这个节点不再是根节点，而变成了一个子节点，那么他的父节点在哪呢，就是他的值所指向的位置，第4个元素，如果是7，那他的父节点就是第7位置的节点，依此类推。如果他的父节点还不是根节点，继续往上找，直到找到本身的索引值等于其存储的值的那个位置，即为根节点。于是，我们可以写一个函数来查找根结点

/**
   * 查找根节点
   * @param p 待查找的节点索引
   * @return 根节点索引
   */
  def root(p:Int): Int = {
      var root = p
      while (root != arr(root)){
        root = arr(root)
      }
      root
  }

当我们要连通两个节点的时候，不再直接操作这两个节点，而是先查找到这两个节点的根节点，然后在两个根节点之间进行 union 操作。我们合并一些节点得到如下结构

还剩0 2 6 7 8 为独立节点，1 3 4 5 8 已经构成一个树形结构，他们的根节点为8。于是我们判断两个节点是否连通，只要查看他们的根节点是否一致即可，用函数实现如下

/**
   * 查看两个节点是否连通
   * 连通 true 否则 false
   * @param p 待查询的p节点索引
   * @param q 待查询的q节点索引
   */
  def connect(p:Int,q:Int): Boolean ={
    if(root(p) == root(q)) true else false
  }

而union操作的逻辑也很简单，先查找到两个节点的两个根节点，如果两个根节点不一致则我们定义连接者根结点为子节点，待连接者根结点为父节点。只要将父节点的索引值覆写子节点的值即可。如果两个根节点一致，则表示两节点已是连通状态，不进行操作

/**
   * 连通两个节点
   * @param p 连接者节点
   * @param q 待连接者节点
   */
  def union(p:Int,q:Int): Unit ={
    val root_p = root(p)
    val root_q = root(q)
    if(root_p != root_q){
      arr(root_p) = root_q
    }
  }

最后完整代码如下，在scala2.12.10下测试通过

package com.datacrafts.digitalevers.algorithm

class quickUnion {

    val arr:Array[Int] = new Array[Int](10)
    for(i <- 0 to 9){
      arr(i) = i
    }

  /**
   * 查找根节点
   * @param p 待查找的节点索引
   * @return 根节点索引
   */
  def root(p:Int): Int = {
      var root = p
      while (root != arr(root)){
        root = arr(root)
      }
      root
  }

  /**
   * 查看两个节点是否连通
   * 连通 true 否则false
   * @param p 待查询的p节点索引
   * @param q 待查询的q节点索引
   */
  def connect(p:Int,q:Int): Boolean ={
    if(root(p) == root(q)) true else false
  }

  /**
   * 连通两个节点
   * @param p 连接者节点
   * @param q 待连接者节点
   */
  def union(p:Int,q:Int): Unit ={
    val root_p = root(p)
    val root_q = root(q)
    if(root_p != root_q){
      arr(root_p) = root_q
    }
  }
}

object quickUnionDemo{
  def main(args: Array[String]): Unit = {
    val qu = new quickUnion
    qu.union(3,4)
    qu.union(4,8)
    qu.union(1,5)
    qu.union(5,8)
    for (elem <- qu.arr) {
      print(elem)
    }                       //0524886789
    println()
    println(qu.connect(0,3))  //false
    println(qu.connect(1,3))  //true
  }
}

考虑到树的最大深度，无论是union还是connect都会进行两次遍历root节点操作，依旧是一个N^2的时间复杂度的算法，无法进行大规模化运算

需要得知两个物件是否已经被连接起来是现实生活中经常遇到的问题，比如复杂电路板上的两个原件是否是连通的，再引申一下，迷宫的两个出口是否可以形成一条路径，也可以归属此问题。下面将使用一维数组来简化解释该算法

有0-9个数在一维数组的0-9个位置上依次排列，现在要将第2位和第5位进行连接，我们称第2位为连接者，第5位为被连接者，同时我们定义，

当连接者和被连接者都是一个独立节点（即在数组中还没有重复的值存在），使用连接者去覆盖被连接者

可见，第5位也被改写成了数字2，于是第2位和第5位连通了起来。然后继续这一过程，将第5位再和第7位连接起来

继续连通第8位和第9位

再继续连通第7位和第8位

这样，当我们需要判定两点是否连通的时候，只需判断两者的值是否相等就可以了。下面将采用Scala来实现这一算法

package com.datacrafts.digitalevers.algorithm

class connectClass {

  val arr:Array[Int] = new Array[Int](10)
  for(i <- 0 to 9){
    arr(i) = i
  }

  /**
   * 连通两个节点
   * @param p  连接者为止
   * @param q  被连接者位置
   */
  def connect(p:Int,q:Int): Unit ={
     for(i <- 0 until  arr.length){
       if(arr(i) == arr(q)){
         arr(i) = arr(p)
       }
     }
  }

  /**
   * 测试两点是否连通
   * 连通为 true 否则为 false
   * @param p
   * @param q
   */
  def isconnect(p:Int,q:Int): Boolean ={
    if(arr(p) == arr(q)) true else false
  }
}

object connectClass{
  def main(args: Array[String]): Unit = {
    val cc = new connectClass
    cc.connect(1,3)
    cc.connect(3,5)
    println(cc.isconnect(1,5))
    println(cc.isconnect(1,6))
  }
}