react 虚拟DOM的diff算法

2020/7/13 17:28:13 人评论 次浏览 分类:学习教程

文章目录

      • 浅谈传统 diff和React diff(16之前的diff)
        • 类型比较
        • 针对组件元素的比较
        • 对子节点进行递归
        • key
        • React中应该如何去配合diff算法提高性能?
      • 三大策略
        • tree diff
        • component diff
        • element diff
      • 小结

今天对diff算法(React16之前)进行了一些学习。

浅谈传统 diff和React diff(16之前的diff)

关于树转换成另一颗树的最小操作数这个问题,最前沿的算法(循环递归比较节点是否相同)的时间复杂度是O(n3)。即对两颗树的节点进行时间复杂度为O(n2)的两两比较,比较结束之后,计算节点到节点的编辑距离(类似海明距离的概念,对节点进行增加、删除、修改等等),这一步需要O(n)的时间,所以最后是O(n3)。

传统diff最大的劣势就是太慢了,尽管它能够适应所有形状的树。React基于两种假设,提出了一套O(n)的启发式算法:

假设一:两种不同类型(type)的元素会产生不同的树;

假设二:开发者可以通过 key prop 来暗示哪些子元素在不同的渲染下能保持稳定。

类型比较

React中针对假设一的策略,就是对不同的根节点进行比较,假如类型不同(比如说div变成了span),就进行拆卸,对整颗树进行重建。例如:

<div>
  <Counter />
</div>

<span>
  <Counter />
</span>

Counter或许是同一个Counter,但因为根节点的不同,会被销毁并重新mount一个新的。

那么类型相同又何如?针对两个相同类型的React元素,原先的DOM节点将被保留,仅对比和更新发生了改变的属性:

<div className="before" title="stuff" />

<div className="after" title="stuff" />

style同理,只更新有变化的属性(下面的color):

<div style={{color: 'red', fontWeight: 'bold'}} />

<div style={{color: 'green', fontWeight: 'bold'}} />

处理完当前节点,就继续递归子节点。

针对组件元素的比较

组件更新时,实例将保持不变,进而state数据也会保持一致,会更新的是组件实例的props,触发调用组件元素实例的componentWillReceiveProps()componentWillUpdate() 方法(比如说用redux传递props的时候,组件中仅props发生了更新,这时需要依赖着两个生命周期函数去监听组件发生了什么变化)。

接下来,调用render()方法,diff算法开始比较。

对子节点进行递归

在默认条件下,当递归 DOM 节点的子元素时,React 会同时遍历两个子元素的列表;当产生差异时,生成一个 mutation。比如说下面的例子,列表尾部新增一个元素,只会有一个mutation,更新开销很小:

<ul>
  <li>first</li>
  <li>second</li>
</ul>

<ul>
  <li>first</li>
  <li>second</li>
  <li>third</li> <!-- mutation -->
</ul>

假如是插入到表头,React是不会意识到的,它会认为前两次比较有两个mutation,进而重建前两个元素,这种情况下就会有性能问题了。

<ul>
  <li>first</li>
  <li>second</li>
</ul>

<ul>
  <li>second</li> <!-- mutation -->
  <li>third</li>  <!-- mutation -->
  <li>first</li>  <!-- mutation -->
</ul>

在React和Vue中,都有通过key的策略来解决这种低效的情况,下面来讲讲key属性的作用。

key

React 支持 key 属性。当子元素拥有 key 时,React 使用 key 来匹配原有树上的子元素以及最新树上的子元素。

<ul>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
</ul>

<ul>
  <li key="2014">Connecticut</li>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
</ul>

在上面的例子中,React知道2014这个新增到表头的元素是新元素,而2015和2016是原来的元素,只不过移动了位置,所以只发生一个mutation(增加元素)。

在开发中,vscode经常会进行语法提示,比如说vue中,建议我们在v-for中使用唯一ID作为:key。

需要注意的是,在使用元素在数组中的下标作为key,比较适合元素不发生重新排序的时候。因为进行重新排序的时候,组件state会遇到一些问题:组件实例根据key来决定是否更新/复用,而排序将改变实例当前的key,导致非受控组件的state(比如说输入框)可能互相篡改,导致无法预料的变动。

官方文档给出了以下标为key和以id为key的两个例子:

以下标为key导致的问题(非受控组件)

使用id为key的例子

所以要谨慎使用数组下标作为key。

React中应该如何去配合diff算法提高性能?

基于React diff的假设一,我们知道,应该尽可能在有变化的地方使用同一类型的组件,还有更新props,这应该也是我们推荐高阶组件的原因。

基于假设二,用唯一的key来避免DOM节点发生不必要的销毁和创建,key必须要稳定。

三大策略

上面的是围绕官方文档的分析,同学说周日面试的时候被问及React diff的三大策略,其实三大策略就是官方文档上面提到的两个假设(type不同就重建,使用key进行复用),只不过更有针对性,三大策略分别是:

  • tree diff
  • component diff
  • element diff

tree diff

Web UI 中 DOM 节点跨层级的移动操作特别少,可以忽略不计。

基于这一假设,React对VDOM树进行层级比较,一旦发现节点不存在,就会将它的子树删除掉,这样一来就可以在O(n)时间内遍历完整颗树。

img

所以在使用React开发的时候,官方建议我们不要进行DOM节点跨层级的移动操作,这与React diff的设计思路相悖。在React diff中,移动会被拆分成两个动作,一个是删除原子树,另一个是新增一颗子树,这将会大大影响React应用的性能。

那么平时开发中,跨层级的移动操作如何避免?这要求我们保持稳定的DOM结构,比如说在展示某个元素时,采用css隐藏的方式去控制节点的显示与否,而不对节点进行销毁和创建。

component diff

component diff策略基于的假设,就是前面所说的type比较。

  • 针对同类型的组件,将会向下递归;如果不是同类型的组件,就会将组件认为是 dirty component,从而替换整个组件下的所有子节点。
  • 针对同类型的组件,有可能VDOM没有变化,在确切知道这一点的情况下,可以通过shouldComponentUpdate() 来判断该组件是否需要进行 diff,节省大量的 diff 运算时间。

element diff

当节点处于同一层级时,可以通过唯一id(key)进行区分。

React中,当节点处于同一层级的时候,可以做三件事,分别是INSERT_MARKUP(插入)、MOVE_EXISTING(移动)和 REMOVE_NODE(删除)。

React在没有key的情况下,会对新老两个节点列表进行遍历,一一比对,一旦发生差异,就会选择删除老的/插入新的,这种情况下会造成很多次冗余的操作。

React diff在面对这种情况,是怎么用key去工作的呢?

img

先来讲一个比较有用的属性,它叫做lastIndex,它表示访问过的节点在老集合中最右的位置(即最大的位置),进而判定元素是否有必要移动,是一种顺序优化的手段。

  1. 它在初始化的时候为0,之后会和旧集合中的元素位置index进行比较。
  2. 假如index > lastIndex,就可以认为元素对集合中其他元素的位置没有影响,进而保持其在旧集合中的相对位置,不发生移动,并更新lastIndex为max(index, lastIndex)。
  3. 假如index < lastIndex,则需要对旧元素进行移动操作到lastIndex,并更新lastIndex为max(index, lastIndex)。

diff的运行过程:

  1. 首先,初始化nextIndex为0,表示当前进行到了哪一个元素的位置;除此之外还有lastIndex也初始化为0,它用来减少移动次数;
  2. 对新集合的节点遍历,利用key去判断老集合有没有一样的节点。有的话,拿出老集合中节点下标index,和lastIndex比较,判断是否会发生移动的操作。假如发生了移动,移动到新集合的nextIndex上面;否则不进行移动。没有一样的节点的话,就会在nextIndex的位置创建一个新节点。
  3. 遍历完新集合所有节点后,假如旧集合中还有剩余的节点,将它们删除。

网上有很多相关的分析,就不举例了。需要注意的是列表尾部移到头部这种情况,lastIndex会被提前赋为较大值,导致其他节点都会发生移动。在这种情况下,diff效率就不太行了。所以,官方建议我们尽量减少将尾节点移动到列表首部这种操作。

看下diff过程的源码:

_updateChildren: function(nextNestedChildrenElements, transaction, context) {
    var prevChildren = this._renderedChildren;
    var removedNodes = {};
    var mountImages = [];

    // 获取新的子元素数组
    var nextChildren = this._reconcilerUpdateChildren(
        prevChildren,
        nextNestedChildrenElements,
        mountImages,
        removedNodes,
        transaction,
        context
    );

    // 数组为空就提前退出
    if (!nextChildren && !prevChildren) {
        return;
    }

    var updates = null;
    var name;
    var nextIndex = 0;
    var lastIndex = 0;
    var nextMountIndex = 0;
    var lastPlacedNode = null;

    for (name in nextChildren) {
        if (!nextChildren.hasOwnProperty(name)) {
            continue;
        }
        var prevChild = prevChildren && prevChildren[name];
        var nextChild = nextChildren[name];
        if (prevChild === nextChild) {
            // 同一个引用,说明是使用的同一个component,所以我们需要做移动的操作
            // 移动已有的子节点
            // 这里根据nextIndex, lastIndex决定是否移动
            updates = enqueue(
                updates,
                this.moveChild(prevChild, lastPlacedNode, nextIndex, lastIndex)
            );

            // 更新lastIndex
            lastIndex = Math.max(prevChild._mountIndex, lastIndex);
            // 更新component的mountIndex属性
            prevChild._mountIndex = nextIndex;

        } else {
            if (prevChild) {
                // 更新lastIndex
                lastIndex = Math.max(prevChild._mountIndex, lastIndex);
            }

            // 添加新的子节点在指定的位置上
            updates = enqueue(
                updates,
                this._mountChildAtIndex(
                    nextChild,
                    mountImages[nextMountIndex],
                    lastPlacedNode,
                    nextIndex,
                    transaction,
                    context
                )
            );

            nextMountIndex++;
        }

        // 更新nextIndex
        nextIndex++;
        // 存当前处理完的节点,下次位置移动会使用到
        lastPlacedNode = ReactReconciler.getHostNode(nextChild);
    }

    // 移除掉不存在的旧子节点,和旧子节点与新子节点不同的旧子节点
    for (name in removedNodes) {
        if (removedNodes.hasOwnProperty(name)) {
            updates = enqueue(
                updates,
                this._unmountChild(prevChildren[name], removedNodes[name])
            );
        }
    }
}

小结

本文围绕虚拟DOM的diff算法展开分析,我们知道16以后的React已经使用了Fiber Node的概念,将整体的数据结构从树改为了链表结构。但不得不说,16以前的diff算法是React框架具有突破意义的一点,学习了解也是有意义的,之后会再对React16 的 diff 策略进行学习,有兴趣的同学可以先参考一下2和3两篇文章对React16 的 diff 策略进行学习。

参考文章

  1. https://segmentfault.com/a/1190000018914249?utm_source=tag-newest
  2. https://segmentfault.com/a/1190000016539430
  3. https://blog.csdn.net/VhWfR2u02Q/article/details/100011830

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->