scanRight和动态规划

Posted on Edited on In Disqus:

scanRight

这是 Functional Programming in Scala 一书中，练习5.16的一个问题。问题是，把 tail 泛化为 scanRight，这个 scanRight 需要返回中间结果形式的 stream。例如：

1
2
scala> Stream(3, 2, 1).scanRight(0)(_ + _).toList
res0: List[Int] = List(6, 5, 3, 0)

注：1. 给定一个 stream，tail 会将这个输入的所有后缀作为 stream 返回；2. 中间结果形式的 stream 意味着结果是以 call-by-name 的方式构造的；3. 遍历 scanRight 的时间复杂度应该为 \(O(n)\)。

先不考虑时间复杂度的要求，仅仅实现 scanRight 的功能，那很容易就可以写出下面的代码，

1
2
3
4
5
def scanRight1[B](z: B)(f: (A, => B) => B): Stream[B] =
  foldRight((z, Stream(z)))((e, acc_s) => {
    val acc_e = f(e, acc_s._1)
    (acc_e, Stream.cons(acc_e, acc_s._2))
  })._2

foldRight 保留了累计值 acc_e 和 stream 的中间值 acc_s，在每次迭代（这里实际上是递归）中，使用这两个值来进行 Stream.cons，以得到最后结果。

计算过程分析

在看这题的答案的时候，发现答案并没有直接使用 acc_s，而是用 lazy 缓存了这个值，然后基于这个缓存的值进行计算。

1
2
3
4
5
6
def scanRight2[B](z: B)(f: (A, => B) => B): Stream[B] =
  foldRight((z, Stream(z)))((e, acc_s) => {
    lazy val p = acc_s
    val acc_e = f(e, p._1)
    (acc_e, Stream.cons(acc_e, p._2))
  })._2

这里我不理解的是缓存什么不好，为什么要缓存 acc_s。因为每次迭代都会遇到 stream 中的元素，为什么不 lazy val p = e。

下面以 Stream(3, 2, 1).scanRight(0)(_ + _) 为例，分析 scanRight1 计算过程。

  1. 把求和的 function 叫 sum，

    1
    s.scanRight(0)(sum)

  2. 展开 scanRight，

    1
    2
    3
    4
    s.foldRight((0, Stream(0)))((e, acc_s) => {
      val acc_e = sum(e, acc_s._1)
      (acc_e, Stream.cons(acc_e, acc_s._2))
    })._2

  3. 为了后续分析方便，对比 foldRight 的类型，提取出 foldRight 的 f，

    1
    2
    3
    4
    5
    6
    def foldRight[B](z: => B)(f: (A, => B) => B): B

    f: (Int, (Int, Stream[Int])) => (Int, Stream[Int]) = (e, acc_s) => {
      val acc_e = sum(e, acc_s._1)
      (acc_e, Stream.cons(acc_e, acc_s._2))
    }

  4. 此时可以进行 foldRight 中的 pattern matching 了，

    1
    2
    3
    Cons(h, t) =>
    h: 3
    t: Stream(2, 1).foldRight((0, Stream(0)))(f)

  5. 把参数代入 f 进行计算，

    1
    2
    3
    4
    5
    6
    7
    acc_e: 3
    acc_s: Stream(2, 1).foldRight((0, Stream(0)))(f)

    {
      val acc_e = sum(3, acc_s._1)
      (acc_e, Stream.cons(acc_e, acc_s._2))
    }

    根据 foldRight 的定义，逐层展开 acc_s._1，即：Stream(2, 1).foldRight((0, Stream(0)))(f)._1，省略了展开的详细过程和 foldRight 中对 Empty 的 pattern matching，

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    {
      val acc_e = sum(3,
                        {
                          val acc_e = sum(2,
                                            {
                                              val acc_e = sum(1, 0)

                                              (acc_e, Stream.cons(acc_e, acc_s._2))
                                            }._1
                                          )

                          (acc_e, Stream.cons(acc_e, acc_s._2))
                        }._1
                      )

      (acc_e, Stream.cons(acc_e, acc_s._2))
    }

    等价于，

    1
    2
    3
    4
    {
      val acc_e = 6
      (6, Stream.cons(6, acc_s._2))
    }

  6. 接下来计算 acc_s._2，即：Stream(2, 1).foldRight((0, Stream(0)))(f)._2。

观察上述过程发现，Stream(2, 1).foldRight((0, Stream(0)))(f)，也就是 acc_s 会被计算两次，这就是 lazy val p = acc_s 的缘由。

与动态规划的联系

进一步分析，在第一次迭代中，当前的 acc_s 需要计算两次。在后续的迭代中（计算：(Stream.cons(6, acc_s._2)），每次迭代都重复计算了一部分结果。简单来说就是，

1
2
3
第一次：3 + 2 + 1
第二次：    2 + 1
第三次：        1

例如值 1，在 3 次迭代中，都被重复计算得到了 3 次。使用 lazy val p = acc_s 避免了这些多余的计算。

这时回过头去看 scanRight，可以将这个函数的功能看做是，对所有的后缀 stream 进行了 foldRight 操作。对长后缀 stream 计算 foldRight 时，实际上计算了短后缀 stream 的 foldRight。这实际上就是动态规划，

  • 最优子结构：当前长后缀 stream 的 foldRight可以由短后缀 stream 得到。
  • 无后效性：短后缀 stream 的 foldRight 不受长后缀 stream 的影响。
  • 子问题重叠：短后缀 stream 的 foldRight 会被多次计算。

由于子问题重叠，因此常用，

  • Memoization (Top Down)
  • Tabulation (Bottom Up)

来存储子问题的解，避免重复计算。

scanRight 实际上就是用了 Memoization 来存储子问题的解。