读scala的reduce、Flod函数源码笔记

记录一下,怕以后忘记,有些还没有看懂,不懂的先猜以及跑例子,之后再补。

 

目录

准备

reduce

reduceLeft

reduce

reduceRight

Flod

未完待续 


准备

关于类型,在控制台运行可以方便观察到类型

val one = 1    // 输出:one: Int = 1, 类型:Int

val list = List(1, 2) // 输出:list: List[Int] = List(1, 2),类型List[Int],中括号里的是范型

val g = (x: Int) => x *3 // 输出:g: Int => Int = <function1>, 对照上面,则类型: Int => Int ,亦可以稍微补全,val g: Int => Int = (x: Int) => x * 3 

    表示输入Int,输出Int

val product = (x: Int, y: Int) => x * y // 输出:product: (Int, Int) => Int = <function2>,类型:(Int, Int) => Int,稍微补全一下,val product: (Int, Int) => Int = (x: Int, y: Int) => x * y

    表示输入有两个参数,类型分别Int和Int,输出是Int类型

reduce

总结:就想一下数学运算的结合律,我们将序列中所有的元素,看成二元运算的两个操作数,由于是相同的运算,可以不考虑优先级;

那么就剩左右结合,reduce和reduceLeft是左结合,看成()从左往右依次括起来,即从左往右算;

reduceRight是右结合,看成()从右往左依次括起来,即从右往左算。

reduceLeft

reduceLeft,源码如下

def reduceLeft[B >: A](op: (B, A) => B): B = {
    if (isEmpty)
      throw new UnsupportedOperationException("empty.reduceLeft")

    var first = true
    var acc: B = 0.asInstanceOf[B]

    for (x <- self) {
      if (first) {
        acc = x
        first = false
      }
      else acc = op(acc, x)
    }
    acc
  }

函数名:reduceLeft,范型[B >: A]

入参op,op的类型是(B,A) => B,参照前面的类型,可以理解为,op是一个函数,接受两个参数,类型分别为B和A,返回类型是B

reduceLeft的整个函数的返回类型也是B。

依据隐式转换以及网上资料搜索,B >: A,表示类型B是类型A的父类(也可以是A)。

self:暂时不知道是啥,目测是代表这个序列

  1. 若序列为空,抛异常
  2. 定义B类型的acc用来记录结果,默认值是0转换成B类型的值。
  3. 对序列中的每一个元素进行操作
    1. 若是序列的第一个值,将其赋给acc
    2. 序列中的其余的值,都需要将op这个函数作用于(acc, 序列中的元素)并返回acc

举例:

    val list = List(1, 2, 3), list.reduceLeft(_ - _)

    1. acc = 0.asInstanceOf[Int],则acc = 0

    2. 遍历下标为0的1,则acc = 1

    3. 遍历下标为1的2, 则acc = acc - 2 = -1

    4. 遍历下标为2的3, 则acc = acc - 3 = -4

    5. 将acc作为结果返回,即-4

简而言之,结果=(1 - 2) - 3 = -4,从左往右,先有(1-2),再有(1-2)-3

scala> val list = List(1, 2, 3)  // list: List[Int] = List(1, 2, 3)

scala> list.reduce(_ - _)       //res120: Int = -4

scala> l                                 // List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8)

scala> l.reduceLeft(_ - _)     // res150: Int = -34

可以看成:先有1 - 2, 再有(1 - 2) - 3, 再( (1 - 2) - 3) - 4,即(((((( (1 - 2) - 3) - 4) - 5) - 6) -7) - 8) = -34

reduce

reduce,源码如下

def reduce[A1 >: A](op: (A1, A1) => A1): A1 = reduceLeft(op)

直接调用的reduceLeft函数,所以结果同上,

scala> list                           // res127: List[Int] = List(1, 2, 3)

scala> list.reduce(_ - _)      // res126: Int = -4

reduceRight

reduceRight,源码如下

def reduceRight[B >: A](op: (A, B) => B): B = {
    if (isEmpty)
      throw new UnsupportedOperationException("empty.reduceRight")
    // 这边注意一下顺序,(x, y) => op(y, x)
    reversed.reduceLeft[B]((x, y) => op(y, x))
}

override /*TraversableLike*/
def reduceLeft[B >: A](f: (B, A) => B): B =
    if (isEmpty) throw new UnsupportedOperationException("empty.reduceLeft")
    else tail.foldLeft[B](head)(f)

// currying函数
override /*TraversableLike*/
def foldLeft[B](z: B)(@deprecatedName('f) op: (B, A) => B): B = {
    var acc = z
    var these = this
    while (!these.isEmpty) {
      acc = op(acc, these.head)
      these = these.tail
    }
    acc
}

其实就是一句话: reversed.reduceLeft[B]((x, y) => op(y, x)),我们先来看看reversed

reversed,源码如下

protected[this] def reversed = {
    var elems: List[A] = Nil
    self foreach (elems ::= _)
    elems
  }

这个reversed,生成翻转的序列,我们瞄一下

scala> l                                   // List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8)

scala> var nil: List[Int] = Nil    // reversedL: List[Int] = List()

scala> l foreach (nil::= _)        // 

scala> reversedL                    // res136: List[Int] = List(8, 7, 6, 5, 4, 3, 2, 1)

再来看这一句话,reversed.reduceLeft[B]((x, y) => op(y, x))

与reduce也即reduceLeft的区别:1.在反转序列的基础上做的;2.调用的是LinearSeqOptimized类的foldLeft函数。

  1. 反转序列,设反转后的序列为reversedL
  2. acc = reversedL.head, these= reversedL.tail
    1. acc = op(these.head, acc), these=these.tail,循环

举例:

    val list = List(1, 2, 3), list.reduceRight(_ - _)

     A. 生成临时反转序列,reversedL, (3, 2, 1)

    1. acc = 3,these=(2,1)

    2. these不为空, acc= these.head - acc= 2 - 3 = -1, these = (1,)

    3. these不为空, acc= these.head - acc= 1 - (-1) = 2, these = ()

    4. theae为空,退出循环,结果返回,即2

简而言之,结果= 1 - (2 - 3) = 2,这边看成从右往左写,即先有2 - 3的结果,再有1 - (2 - 3)

scala> val list = List(1, 2, 3)  // list: List[Int] = List(1, 2, 3)

scala> list.reduce(_ - _)       //res120: Int = 2

scala> l                                 // List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8)

scala> l.reduceLeft(_ - _)     // res150: Int = -4

可以看成:先有(7 - 8),再有6 - (7 - 8), 再有5 - (6 -( 7- 8)), 即 (1-(2-(3-(4-(5-(6-(7-8))))))) = - 4,

Flod

未完待续 

上一篇:本周最新文献速递20210718


下一篇:Java ASM系列:(044)SerialVersionUIDAdder介绍