月度归档： 2020 年 8 月

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

package com.datacrafts.digitalevers.link

/**
 * 经典的约瑟夫环问题
 * 本质就是一个单向循环链表的实现
 * @param n 链表中初始节点个数
 */
class Josephus(n:Int) {
    var length = 0
    var head:node = null
    var curr:node = null
    var prev:node = null
    for(index <- 1 to n){
      if(length == 0){
        curr  = new node(index)
        prev = curr
        head = curr
        curr.next = curr
      } else {
        val temp  = new node(index)
        temp.next = head
        curr.next = temp
        prev = curr
        curr = temp
      }
      length += 1
    }
    //初始化完成后复位
    curr = head
    prev = head

  /**
   * 移动到第k个人
   * 1 <= k <= length
   */
  def moveToK(k:Int): Unit ={
      for(index <- 1 until k){
          prev = curr
          curr = curr.next
      }
  }

  /**
   * 开始丢手绢过程
   * 丢到第 m 个人则退出
   * 若curr 与 prev相等 说明循环链表中只剩一个节点 则结束循环
   */
  def circle(m:Int): Unit ={
    while(curr != prev){
      for(index <- 1 until m){
        prev = curr
        curr = curr.next
      }
      //循环结束 删除当前节点
      println(curr.id)
      prev.next = curr.next
      curr = curr.next
      length -= 1
    }
    println(curr.id)
  }

  /**
   * 展示约瑟夫环上所有节点数据
   */
  def show(): Unit = {
    var curr = head
    for(index <- 1 to length){
      println(curr.id)
      curr = curr.next
    }
  }
}

/**
 * 节点类型
 * @param _id
 */
class node(_id:Int){
  var id:Int = _id
  var next:node = null
}

object Josephus{
  def main(args: Array[String]): Unit = {
    var josephus = new Josephus(7)
    //josephus.show()
    josephus.moveToK(4)
    //println(josephus.curr.id)
    //println(josephus.prev.id)
    josephus.circle(3)
    //println(josephus.length)
  }
}

package com.datacrafts.digitalevers.generic

import util.control.Breaks._
import scala.reflect.runtime.universe._


class twoWay[T,U](in:T,v:U) {
  private var size = 0
  var head:node[T,U] = new node[T,U](in,v)

  //比较器
  val cc = new commonCompare

  /**
   * 链表尾部添加节点
   * @param newNode
   */
  def addNode(newNode:node[T,U]): Unit = {
    var temp = head
    while(temp.next != null){
      temp = temp.next
    }
    temp.next = newNode
    newNode.prev = temp
    size += 1
  }

  /**
   * 按顺序插入节点
   */
  def addNodeOrder(newNode:node[T,U])(implicit t:TypeTag[T]): Unit = {
    var curr = head
    var prev = head

    t.tpe match {
      case tpe if tpe == typeOf[Int]=>{
        breakable {
          while (curr != null) {
            prev = curr
            curr = curr.next
            if (curr != null && cc.greater(curr.id.asInstanceOf[Int], newNode.id.asInstanceOf[Int]) == false) {
              //如果找到了这个比新节点数据更小或相等的节点 跳出循环
              break()
            }
          }
        }
      }
      case tpe if tpe == typeOf[Double] =>{
        breakable {
          while (curr != null) {
            prev = curr
            curr = curr.next
            if (curr != null && cc.greater(curr.id.asInstanceOf[Double], newNode.id.asInstanceOf[Double]) == false) {
              //如果找到了这个比新节点数据更小或相等的节点 跳出循环
              break()
            }
          }
        }
      }
    }
    /////match

    if(curr == null){
      //没有找到该节点则在链表尾部插入新节点
      prev.next = newNode
      newNode.prev = prev
    } else {
      //没有则在该节点前置插入新节点
      newNode.next = curr
      prev.next = newNode

      curr.prev = newNode
      newNode.prev = prev
    }
    size += 1
  }

  /**
   * 更新节点数据域
   */
  def updateNode(id:T,data:U){
    var curr = head
    while (curr != null && curr.id != id) {
      curr = curr.next
    }
    if(curr != null){
      curr.data = data
    }
  }

  /**
   * 删除节点（自我删除）
   */
  def delete(id:T): Unit = {
    /*var curr = head
    var prev = head
    while (curr != null && curr.id != id){
      prev = curr
      curr = curr.next
    }
    if(curr != null){
      prev.next = curr.next
      curr.next.prev = prev
      curr.next = null
      curr.prev = null
    }*/
    var curr = head
    while (curr != null && curr.id != id){
      curr = curr.next
    }
    if(curr != null){
      curr.prev.next = curr.next
      if(curr.next != null) {
        curr.next.prev = curr.prev
      }
      //清除待删除节点自身与其他节点的关系
      curr.next = null
      curr.prev = null
    }
  }

  /**
   * 展示链表的所有数据
   */
  def show(): Unit ={
    var temp = head
    while(temp.next != null){
      temp = temp.next
      println(temp)
    }
  }

  def length = {
    size
  }
}

class node[T,U](in:T,v:U){
  var id:T = in
  var data:U = v
  var prev:node[T,U] = null
  var next:node[T,U] = null

  override def toString: String = {
    id + " "+data.toString
  }
}

/**
 * 泛型的通用比较类
 */
class commonCompare{
  def greater[T<% Comparable[T]](t1:T,t2:T) =
    if(t1.compareTo(t2) > 0) true else false
}



object testTwoWay{
  def main(args: Array[String]): Unit = {
    val linkTest = new twoWay(0,"")
    val newNode = new node(13,"hello")
    linkTest.addNodeOrder(newNode)
    val newNode2 = new node(15,"scala")
    linkTest.addNodeOrder(newNode2)
    val newNode3 = new node(20,"java")
    linkTest.addNodeOrder(newNode3)
    //linkTest.updateNode(13,"php")
    linkTest.delete(15)
    linkTest.delete(13)

    linkTest.addNodeOrder(newNode2)
    linkTest.show()
    //print(linkTest.length)
  }
}

package com.datacrafts.digitalevers.generic

import util.control.Breaks._
import scala.reflect.runtime.universe._


/**
 * 比较粗略实现了泛型版本的单向链表的增删改查操作，代码在scala 2.12.10上编译通过，测试运行通过。有几个点需要注意
 * 1.上下边界 <: >:都没有隐式转换 只有视图边界 % 才有隐式转换
 * 2.在按顺序往链表添加节点时 应将比较器的实例化对象提取到 链表类的属性层 而不应放在方法中  此举是为了解决内存使用
 * 3.编译过程中，实例化比较器需要得知泛型参数的具体类型，之前在这个地方纠结了很久，最终无法通过隐式转换实行自动比较，故只能显式将其转换为Int 或者 Double类型
 * 4.但是由于 scala 在运行过程中会擦除泛型类型，故使用了一个小技巧——加入一个隐式参数TypeTag[T]来保存运行时泛型类型，然后通过模式匹配来决定改转换成哪种对象（Int或者Double)，然后会自动通过隐式转换为 Comparable 子类来进行比较操作
 * 5.感觉还有更好的实现方式，以便可以支持更多的数据类型
 * @param in
 * @tparam T
 */
class genericClass[T,U](in:T,v:U) {
  private var size = 0
  var head:node[T,U] = new node[T,U](in,v)

  //比较器
  val cc = new commonCompare
  /**
   * 链表尾部添加节点
   * @param newNode
   */
  def addNode(newNode:node[T,U]): Unit = {
    var temp = head
    while(temp.next != null){
      temp = temp.next
    }
    temp.next = newNode
    size += 1
  }

  /**
   * 按顺序插入节点
   */
  def addNodeOrder(newNode:node[T,U])(implicit t:TypeTag[T]): Unit = {
    var curr = head
    var prev = head

    t.tpe match {
      case tpe if tpe == typeOf[Int]=>{
        breakable {
          while (curr != null) {
            prev = curr
            curr = curr.next
            if (curr != null && cc.greater(curr.id.asInstanceOf[Int], newNode.id.asInstanceOf[Int]) == false) {
              //如果找到了这个比新节点数据更小或相等的节点 跳出循环
              break()
            }
          }
        }
      }
      case tpe if tpe == typeOf[Double] =>{
        breakable {
          while (curr != null) {
            prev = curr
            curr = curr.next
            if (curr != null && cc.greater(curr.id.asInstanceOf[Double], newNode.id.asInstanceOf[Double]) == false) {
              //如果找到了这个比新节点数据更小或相等的节点 跳出循环
              break()
            }
          }
        }
      }
    }
    /////match

    if(curr == null){
      //没有找到该节点则在链表尾部插入新节点
      prev.next = newNode
    } else {
      //没有则在该节点前置插入新节点
      newNode.next = curr
      prev.next = newNode
    }
    size += 1
  }

  /**
   * 更新节点数据域
   */
  def updateNode(id:T,data:U){
    var curr = head
    while (curr != null && curr.id != id) {
      curr = curr.next
    }
    if(curr != null){
      curr.data = data
    }
  }

  /**
   * 删除节点
   */
  def delete(id:T): Unit = {
    var curr = head
    var prev = head
    while (curr != null && curr.id != id){
      prev = curr
      curr = curr.next
    }
    if(curr != null){
      prev.next = curr.next
    }
  }

  /**
   * 展示链表的所有数据
   */
  def show(): Unit ={
    var temp = head
    while(temp.next != null){
      temp = temp.next
      println(temp)
    }
  }

  def length = {
    size
  }
}

class node[T,U](in:T,v:U){
  var id:T = in
  var data:U = v
  var next:node[T,U] = null

  override def toString: String = {
    id + " "+data.toString
  }
}

/**
 * 泛型的通用比较类
 */
class commonCompare{
  def greater[T<% Comparable[T]](t1:T,t2:T) =
    if(t1.compareTo(t2) > 0) true else false
}



object test{
  def main(args: Array[String]): Unit = {
    val linkTest = new genericClass(0,"")
    val newNode = new node(13,"hello")
    linkTest.addNodeOrder(newNode)
    val newNode2 = new node(15,"scala")
    linkTest.addNodeOrder(newNode2)
    linkTest.updateNode(13,"php")
    //linkTest.delete(15)
    linkTest.show()
    //print(linkTest.length)
  }
}

package com.datacrafts.digitalevers.queue


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

  }
}

/**
 *
 */
class oneWayQueue(maxSize:Int) {
  var front = -1
  var tail = -1

  val length = maxSize
  if(maxSize <= 0){
    throw new Exception("参数错误")
  }
  var oneWayQueue = Array[Int](maxSize)

  /**
   * 队列是否为空
   */
  def isEmpty(): Boolean = {
    if(front == tail) true else false
  }

  /**
   * 队列是否满员
   */
  def isFull():Boolean = {
    if(tail >= length - 1) true else false
  }

  /**
   * 队列弹出数据
   */
  def getData() = {
    if(isEmpty()){
      throw new Exception("队列为空")
    }
    front += 1
    oneWayQueue(front)
  }

  /**
   * 队列添加数据
   * TODO 亦可以直接返回 Exception 类型使其参与逻辑运算
   */
  def addData(inData:Int) = {
    if(isFull()){
      //throw new Exception("队列已满")
      false
    } else {
      tail += 1
      oneWayQueue(tail) = inData
      true
    }
  }
  ////////
}