最小依赖图重新计算值算法

大家好呀,好久没有写正式的文章了,有点生疏了。最近完成了一个库的PoC,在最近一期的《Robust》里面也有介绍到,你有听最近一期的《Robust》吗?这个库叫sfcjs,sfc即single file component的缩写,你写过vue的话,肯定知道vue的.vue后缀文件的写法,对的,就是这个家伙。

在这个库中,我基于依赖收集做响应式更新,整个视图被提前建立一个树状结构,并且有一个依赖收集的列表,每次被依赖的响应式数据发生变化,就去遍历每个节点,检查每个节点的依赖是否有这个变化的数据,如果有,就更新当前这个节点。sfcjs里面没有用virtual dom,更新只针对当前节点,所以效率肯定会比react vue都高。

在这个机制里面,有一个场景是,一个响应式数据可能依赖了另外一个响应式数据,例如:

let a = 1
let b = a + 5

其中b依赖了a,也就是说,b在每次a发生变化的时候,都应该更新。这也意味着,在视图中,依赖了b的节点,实际上也会被a的更新所触发重新渲染。

这里就会有一个问题,假如这种依赖关系比较复杂,那么,这个更新的机制应该怎么处理呢?例如,我们有如下这些变量:

let a = 1
let b = a + 5
let c = a + b + 3
let d = c + 9
let e = a * 4
let f = 10
let g = f + a + c + 2
let h = a + d + 6
let i = g + d

它们之间的依赖关系如下:

基于这个图,我们可以看到所有这些变量之间的依赖关系,这个可以被称为“全依赖图”。但是,在我们的代码中,虽然声明了这些变量,但是我们真正在视图中,可能并没有全部用到,我们可能只用到了bcdfg这几个,可以发现,我们实际的依赖图比这个“全依赖图”要小,但是,虽然我们只依赖了bcdfg,但是实际上,a这个变量也被依赖了。所以,最终的“最小依赖图”是这样:

从这个图上,我们其实可以猜测出,真正能够发生变化的,只有af这两个变量,其他变量都是中间过程变量。

现在,我们回到编程的思路中来,假设我们的一个节点依赖了c和g,此时,我们要如何编程,才能在代码层面让我们的这个节点在a发生更新时更新节点内容呢?

我们来看看一些框架是怎么做的吧。

先看看angularjs:

$scope.$watch('a', () => {
  $scope.c = $scope.b + $scope.a + 3
})

$scope.$watch('b', () => {
  $scope.c = $scope.b + $scope.a + 3
})

$scope.$watch('a', () => {
  $scope.b = $scope.a + 5
})

// ... 省略其他依赖关系梳理

可以看到在angualrjs中我们没有办法直接表达依赖关系,只能通过$watch来在某个值发生变化时,做一个计算,从而使另外一个值发生变化。angularjs基于脏检查机制去处理这些属性,关于脏检查机制,我在之前的一篇文章中有解释过,这里就不再赘述。总之,你会发现,这里的所有watch函数,都要执行好多次。

再来看看vue里面:

export default {
  data() {
    return {
      a: 1,
      f: 10,
    }
  },
  computed: {
    b() {
      return this.a + 5
    },
    c() {
      return this.a + this.b + 3
    },
    d() {
      return this.c + 9
    },
    g() {
      return this.a + this.c + this.f + 2
    },
  },
}

哇塞,这样就可以完全表达出一个变量的依赖逻辑,虽然单纯从表达式来看,我们并不知道dg依赖了a,但是基于vue的依赖收集,当this.a发生变化时,这些计算属性都会重新进行计算。

看上去完美对么?但是,如果你深入了解过vue的计算属性的实现原理,你可能会发现,它的依赖计算本质上还是watcher(在vue3中已经重构,不再使用这种方案),通过对a的监听,来重新计算bcdg。但是,你有没有发现,当a发生变化的时候,c要重新计算一次,而此时,b也会重新计算一次,b的重新计算,又会导致c再重新计算一次,也就是说,a的变化,会让c计算两次。

但是,这完全没有必要对吗?

有没有一种方法,可以让这些基于依赖的重新计算只执行一次呢?有的。

我们现在重新去分析angular和vue里面的问题所在,或许也是整个设计上的无奈。就是我们无法在一开始就知道c依赖ab的同时,b也依赖a。也就是说,bc这两个都依赖a的计算属性是割裂的,所以,每次重新计算值的时候,它们只能自己单独计算,而这种割裂就导致c在a变时计算一次,b变时再计算一次。

怎么办呢?

我们建立一种计算的优先级等级机制来完成重新计算。也就是说,这次,我们不是所有的bcdg平等的大家都来计算一次自己,而是有一个基于优先级的等级划分,通盘考虑,统筹规划。

在这种等级划分中,我们确定哪些变量先重新计算,哪些后重新计算,也就是分批计算。而这个分批次的算法,就是本文的重点。先按住不讲。通过这个分批之后,每个变量我只需要计算一次。我们先用我们的眼睛来统筹规划一下,上面的最小依赖图中,我们可以这样划分批次:

af|b|c|dg

第一批是af,第二批是b,第三批是c,第四批是dg。按照这个顺序分批计算,只需要计算一次,我就能让所有的值都更新到正确的值。你可以自己去验证一下,是不是这样。

这是怎么做到的呢?你可以这样思考,比如我们拿c举例,如果a发生变化的时候,马上去重新计算c,紧接着,b也会由于a变而发生变化,c还需要再计算一次才能得到正确结果。既然如此,我们就可以在一开始的时候,不计算c,而是在b变化的时候再计算c。

等一等!!

这里的表述是错误的,在分批的这种思想下,根本不是“b变化”引起的“再计算c”这个过程,而是无论b有没有变化,都会再计算c,分批计算的核心就在于,每一个变量都需要重新计算。比如再计算c的时候,我根本不需要考虑说是a变了还是b变了,我只要确保在b后面再计算c,那么c的值就一定是正确的。

显然,这里还是不够好,因为,假如ab都没有变,为啥要重新计算一次c?所以,我们的算法里面还需要包含这部分优化。那么,怎么优化呢?

不要忘记了,在前面的依赖收集中,我们的c收集到了自己依赖ab,d是最惨的只收集到自己依赖c,但这都不要紧。因为我们是分批计算的,比如说,我们现在f这个变量变了,a没有变,从前面的依赖图我们知道,实际上只需要g重新计算就可以了,但是我们程序不知道啊,我们得用算法去告诉程序。怎么办呢?

在开始分批计算时,我创建一个临时列表,用来保存哪些变量发生变化了,比如上面这个例子,在第一批(也就是发生变化的变量这一批),我记录了f,没有记录a。进入下一批计算时,b依赖了a但是在这个临时列表里面没有a,所以我b不重新计算,再下一批,c依赖ab,但是这两个家伙都不在列表里,所以c也不重新计算,接下来d也是一样,c不在列表里,d也不重新计算,g依赖了acf,其中f在列表里,所以g要重新计算。怎么样,虽然我们仍然是分批来的,但是,最终整个过程我们只重新计算了g。

基于这个算法,我们实际上不需要去提炼最小依赖图,而可以直接用全图,因为即使我上全图,但是最后的计算量也只局限于需要重新计算的哪些变量而已。这样,我们就省去了从全图找出最小依赖图的这个过程,省了一些性能。

好了,接下来是揭秘怎么实现分批的算法。

我们还是用图来说话吧。

首先,我们将最小依赖图进行拆解,变成这样:

把依赖图中的每一条依赖线平铺出来。一共7条线对吧。其中左边是被依赖的变量,右边是依赖了别的变量的变量。现在,我们就是要算出批次对吧。好,如下:

  1. 找出只存在于左边而不存在于右边的变量,作为一批,放入分批列表的第一组中
  2. 将刚才使用过的依赖线划掉

按照上面这个步骤,我们找到了只存在于左边的a和f,有了第一批af然后把这些使用过的依赖线划掉:

接下来,就只剩下了3条线。然后我们继续按照上面的步骤,重新来过:

  1. 找出只存在于左边而不存在于右边的变量,作为一批,放入分批列表的第一组中
  2. 将刚才使用过的依赖线划掉

这次我们只划掉了一条线,并且找到了第二批,和前面的批次连起来得到 af|d。接下来,我们再来一次:

  1. 找出只存在于左边而不存在于右边的变量,作为一批,放入分批列表的第一组中
  2. 将刚才使用过的依赖线划掉

这次我们划掉了两条,并找到了第三批,得到 af|d|c

此时,我们的所有线都被划掉了,但是我们的分批队列里面不对劲呀,还有一些变量不在这里面。没有关系,我们把所有变量做一次filter,把哪些还不在队列里面的全部找出来,作为最后一批加入到队列最后面,得到 af|b|c|dg。为什么可以这样呢?因为那些最后还不在队列里面的变量是依赖上一次被划掉的依赖的,而被划掉之后就代表没有依赖了,所以,这些剩下的家伙一定是最后一批去算的,而且都是在这一个批次。

以上就是建立依赖图分批的算法,从代码实现上看,其实也非常简单,你可以自己实现一下试试。

2021-09-12 58

为价值买单

本文价值0.58RMB
已有2条评论
  1. 1188 2021-09-13 13:42

    很妙的方法. 就是最后的af|d|c|dg错了, d重复了

    • 否子戈 2021-09-13 14:10

      感谢提醒,已改正