传统diff、react优化diff、vue优化diff

更新日期: 2019-07-03阅读: 2.5k标签: diff

传统diff

计算两颗树形结构差异并进行转换,传统diff算法是这样做的:循环递归每一个节点


比如左侧树a节点依次进行如下对比,左侧树节点b、c、d、e亦是与右侧树每个节点对比
算法复杂度能达到O(n^2),n代表节点的个数

a->e、a->d、a->b、a->c、a->a

查找完差异后还需计算最小转换方式,这其中的原理我没仔细去看,最终达到的算法复杂度是O(n^3)


react优化的diff策略

传统diff算法复杂度达到O(n^3 )这意味着1000个节点就要进行数10亿次的比较,这是非常消耗性能的。react大胆的将diff的复杂度从O(n^3)降到了O(n),他是如何做到的呢

由于web UI中跨级移动操作非常少、可以忽略不计,所以react实现的diff是同层级比较


拥有相同类型的两个组件产生的dom结构也是相似的,不同类型的两个组件产生的DOM结构则不近相同

对于同一层级的一组子节点,通过分配唯一唯一id进行区分(key值)


react虚拟节点

dom中没有直接提供api让我们获取一棵树结构,这里我们自己构建一个虚拟的dom结构,遍历这样的数据结构是一件很轻松直观的事情。
对于下面的dom,可以用js构造出一个简单的虚拟dom

<div className="myDiv">
  <p>1</p>
  <div>2</div>
  <span>3</span>
</div>
{
  type: 'div',
  props: {
      className: 'myDiv',
  },
  chidren: [
      {type: 'p',props:{value:'1'}},
      {type: 'div',props:{value:'2'}},
      {type: 'span',props:{value:'3'}}
  ]
}

先序深度优先遍历

首先要遍历新旧两棵树,采用深度优先策略,为树的每个节点标示唯一一个id


在遍历过程中,对比新旧节点,将差异记录下来,记录差异的方式后面会提到

//若新旧树节点只是位置不同,移动
//计算差异
//插入新树中存在但旧树中不存在的节点
//删除新树中没有的节点

// diff 函数,对比两棵树
function diff (oldTree, newTree) {
  // 当前节点的标志,以后每遍历到一个节点,加1
  var index = 0
  var patches = {} // 用来记录每个节点差异的对象
  dfsWalk(oldTree, newTree, index, patches)
  return patches
}

// 对两棵树进行深度优先遍历
function dfsWalk (oldNode, newNode, index, patches) {
  // 对比oldNode和newNode的不同,记录下来
  patches[index] = [...]

  diffChildren(oldNode.children, newNode.children, index, patches)
}

// 遍历子节点
function diffChildren (oldChildren, newChildren, index, patches) {
  var leftNode = null
  var currentNodeIndex = index
  oldChildren.forEach(function (child, i) {
    var newChild = newChildren[i]
    currentNodeIndex = (leftNode && leftNode.count) // 计算节点的标识
      ? currentNodeIndex + leftNode.count + 1
      : currentNodeIndex + 1
    dfsWalk(child, newChild, currentNodeIndex, patches) // 深度遍历子节点
    leftNode = child
  })
}

差异类型

上面代码中,将所有的差异保存在了patches对象中,会有如下几种差异类型:

  1. 插入:patches[0]:{type:'INSERT_MARKUP',node: newNode }
  2. 移动:patches[0]: {type: 'MOVE_EXISTING'}
  3. 删除:patches[0]: {type: 'REMOVE_NODE'}
  4. 文本内容改变:patches[0]: {type: 'TEXT_CONTENT',content: 'virtual DOM2'}
  5. 属性改变:patches[0]: {type: 'SET_MARKUP',props: {className:''}}

列表对比

节点两两进行对比时,我们知道新节点较旧节点有什么不同。如果同一层的多个子节点进行对比,他们只是顺序不同,按照上面的算法,会先删除旧节点,再新增一个相同的节点,这可不是我们想看到的结果
实际上,react在同级节点对比时,提供了更优的算法:


同级比较

首先对新集合的节点(nextChildren)进行in循环遍历,通过唯一的key(这里是变量name)可以取得新老集合中相同的节点,如果不存在,prevChildren即为undefined。如果存在相同节点,也即prevChild === nextChild,则进行移动操作,但在移动前需要将当前节点在老集合中的位置与 lastIndex 进行比较,见moveChild函数,如下图


if (child._mountIndex < lastIndex),则进行节点移动操作,否则不执行该操作。这是一种顺序优化手段,lastIndex一直在更新,表示访问过的节点在老集合中最右的位置(即最大的位置),如果新集合中当前访问的节点比lastIndex大,说明当前访问节点在老集合中就比上一个节点位置靠后,则该节点不会影响其他节点的位置,因此不用添加到差异队列中,即不执行移动操作,只有当访问的节点比lastIndex小时,才需要进行移动操作。

所以下图中只需要移动A、C




vue优化的diff策略

既然传统diff算法性能开销如此之大,Vue做了什么优化呢?

  • 跟react一样,只进行同层级比较,忽略跨级操作

react以及Vue在diff时,都是在对比虚拟dom节点,下文提到的节点都指虚拟节点。Vue是怎样描述一个节点的呢?

Vue虚拟节点

// body下的 <div id="v"><div> 对应的 oldVnode 就是

{
  el:  div  //对真实的节点的引用,本例中就是document.querySelector('#id.classA')
  tagName: 'DIV',   //节点的标签
  sel: 'div#v.classA'  //节点的选择器
  data: null,       // 一个存储节点属性的对象,对应节点的el[prop]属性,例如onclick , style
  children: [], //存储子节点的数组,每个子节点也是vnode结构
  text: null,    //如果是文本节点,对应文本节点的textContent,否则为null
}

patch

diff时调用patch函数,patch接收两个参数vnode,oldVnode,分别代表新旧节点。

function patch (oldVnode, vnode) {
    if (sameVnode(oldVnode, vnode)) {
        patchVnode(oldVnode, vnode)
    } else {
        const oEl = oldVnode.el
        let parentEle = api.parentNode(oEl)
        createEle(vnode)
        if (parentEle !== null) {
            api.insertBefore(parentEle, vnode.el, api.nextSibling(oEl))
            api.removeChild(parentEle, oldVnode.el)
            oldVnode = null
        }
    }
    return vnode
}

patch函数内第一个if判断sameVnode(oldVnode, vnode)就是判断这两个节点是否为同一类型节点,以下是它的实现:

function sameVnode(oldVnode, vnode){
  //两节点key值相同,并且sel属性值相同,即认为两节点属同一类型,可进行下一步比较
    return vnode.key === oldVnode.key && vnode.sel === oldVnode.sel
}

也就是说,即便同一个节点元素比如div,他的className不同,Vue就认为是两个不同类型的节点,执行删除旧节点、插入新节点操作。这与react diff实现是不同的,react对于同一个节点元素认为是同一类型节点,只更新其节点上的属性。

patchVnode

对于同类型节点调用patchVnode(oldVnode, vnode)进一步比较:

patchVnode (oldVnode, vnode) {
    const el = vnode.el = oldVnode.el  //让vnode.el引用到现在的真实dom,当el修改时,vnode.el会同步变化。
    let i, oldCh = oldVnode.children, ch = vnode.children
    if (oldVnode === vnode) return  //新旧节点引用一致,认为没有变化
    //文本节点的比较
    if (oldVnode.text !== null && vnode.text !== null && oldVnode.text !== vnode.text) {
        api.setTextContent(el, vnode.text)
    }else {
        updateEle(el, vnode, oldVnode)
        //对于拥有子节点(两者的子节点不同)的两个节点,调用updateChildren
        if (oldCh && ch && oldCh !== ch) {
            updateChildren(el, oldCh, ch)
        }else if (ch){  //只有新节点有子节点,添加新的子节点
            createEle(vnode) //create el's children dom
        }else if (oldCh){  //只有旧节点内存在子节点,执行删除子节点操作
            api.removeChildren(el)
        }
    }
}

updateChildren

patchVnode中有一个重要的概念updateChildren,这是Vue diff实现的核心

updateChildren (parentElm, oldCh, newCh) {
    let oldStartIdx = 0, newStartIdx = 0
    let oldEndIdx = oldCh.length - 1
    let oldStartVnode = oldCh[0]
    let oldEndVnode = oldCh[oldEndIdx]
    let newEndIdx = newCh.length - 1
    let newStartVnode = newCh[0]
    let newEndVnode = newCh[newEndIdx]
    let oldKeyToIdx
    let idxInOld
    let elmToMove
    let before
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
            if (oldStartVnode == null) {   //对于vnode.key的比较,会把oldVnode = null
                oldStartVnode = oldCh[++oldStartIdx] 
            }else if (oldEndVnode == null) {
                oldEndVnode = oldCh[--oldEndIdx]
            }else if (newStartVnode == null) {
                newStartVnode = newCh[++newStartIdx]
            }else if (newEndVnode == null) {
                newEndVnode = newCh[--newEndIdx]
            }else if (sameVnode(oldStartVnode, newStartVnode)) {
                patchVnode(oldStartVnode, newStartVnode)
                oldStartVnode = oldCh[++oldStartIdx]
                newStartVnode = newCh[++newStartIdx]
            }else if (sameVnode(oldEndVnode, newEndVnode)) {
                patchVnode(oldEndVnode, newEndVnode)
                oldEndVnode = oldCh[--oldEndIdx]
                newEndVnode = newCh[--newEndIdx]
            }else if (sameVnode(oldStartVnode, newEndVnode)) {
                patchVnode(oldStartVnode, newEndVnode)
                api.insertBefore(parentElm, oldStartVnode.el, api.nextSibling(oldEndVnode.el))
                oldStartVnode = oldCh[++oldStartIdx]
                newEndVnode = newCh[--newEndIdx]
            }else if (sameVnode(oldEndVnode, newStartVnode)) {
                patchVnode(oldEndVnode, newStartVnode)
                api.insertBefore(parentElm, oldEndVnode.el, oldStartVnode.el)
                oldEndVnode = oldCh[--oldEndIdx]
                newStartVnode = newCh[++newStartIdx]
            }else {
               // 使用key时的比较
                if (oldKeyToIdx === undefined) {
                    oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) // 有key生成index表
                }
                idxInOld = oldKeyToIdx[newStartVnode.key]
                if (!idxInOld) {
                    api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)
                    newStartVnode = newCh[++newStartIdx]
                }
                else {
                    elmToMove = oldCh[idxInOld]
                    if (elmToMove.sel !== newStartVnode.sel) {
                        api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)
                    }else {
                        patchVnode(elmToMove, newStartVnode)
                        oldCh[idxInOld] = null
                        api.insertBefore(parentElm, elmToMove.el, oldStartVnode.el)
                    }
                    newStartVnode = newCh[++newStartIdx]
                }
            }
        }
        if (oldStartIdx > oldEndIdx) {
            before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].el
            addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx)
        }else if (newStartIdx > newEndIdx) {
            removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
        }
}

代码很长,解读参照文章下面提到的大神文章。原理示意图如下:


过程可以概括为:oldCh和newCh各有两个头尾的变量StartIdx和EndIdx,它们的2个变量相互比较,一共有4种比较方式。如果4种比较都没匹配,如果设置了key,就会用key进行比较,在比较的过程中,变量会往中间靠,一旦StartIdx>EndIdx表明oldCh和newCh至少有一个已经遍历完了,就会结束比较。

这种由两端至中间的对比方法与react的updateChildren实现也是不同,后者是从左至右依次进行对比,各有优点。
比如一个集合,只是把最后一个节点移到了第一个,react实现就出现了短板,react会依次移动前三个节点到对应的位置:



而Vue会在首尾对比时,只移动最后一个节点到第一位即可


作者:娘娘羌
链接:https://www.jianshu.com/p/398e63dc1969

链接: https://www.fly63.com/article/detial/4007

React Diff 算法

React 是 facebook 出的一个前端框架. 设计的关键处就是性能问题。在本文中,我主要是介绍 Diff 算法以及 React 渲染 ,这样你可以更好的优化你的应用程序。

浅析vue2.0的diff算法

如果不了解virtual dom,要理解diff的过程是比较困难的。虚拟dom对应的是真实dom, 使用document.CreateElement 和 document.CreateTextNode创建的就是真实节点。vue2.0才开始使用了virtual dom,有向react靠拢的意思。

简述dom diff原理

关于react的虚拟dom以及每次渲染更新的dom diff,网上文章很多。但是我一直信奉一个原则,即:但凡复杂的知识,理解之后都只需要记忆简单的东西,而想简单、精确描述一个复杂知识,是极困难的事。

React 中 Virtual DOM 与 Diffing 算法的关系

Virtual DOM 是一种编程理念。UI 信息被特定语言描述并保存到内存中,再通过特定的库,例如 ReactDOM 与真实的 DOM 同步信息。这一过程成为 协调 (Reconciliation)。上述只是 协调算法

Vue2.x的diff算法记录

为什么在Vue3.0都已经出来这么久了我还要写这篇文章,因为目前自己还在阅读Vue2.x的源码,感觉有所悟。作为一个刚毕业的新人,对Vue框架的整体设计和架构突然有了一点认知,所以才没头没尾地突然写下了diff算法。

深入理解React Diff算法

fiber上的updateQueue经过React的一番计算之后,这个fiber已经有了新的状态,也就是state,对于类组件来说,state是在render函数里被使用的,既然已经得到了新的state

虚拟 DOM 与 Diff 算法的实现原理

Vue 源码中虚拟 DOM 与 Diff 算法的实现借鉴了 snabbdom 这个库,snabbdom 是一个虚拟 DOM 库,它专注于简单,模块化,强大的功能和性能。要彻底明白虚拟 DOM 与 Diff 算法就得分析 snabbdom 这个库到底做了什么?

手写一个虚拟DOM库,彻底让你理解diff算法

所谓虚拟DOM就是用js对象来描述真实DOM,它相对于原生DOM更加轻量,因为真正的DOM对象附带有非常多的属性,另外配合虚拟DOM的diff算法,能以最少的操作来更新DOM,除此之外

详解虚拟DOM与Diff算法

那么需要真实的操作DOM100w次,触发了回流100w次。每次DOM的更新都会按照流程进行无差别的真实dom的更新。所以造成了很大的性能浪费。如果循环里面是复杂的操作,频繁触发回流与重绘

浅析snabbdom中vnode和diff算法

目前前端使用最多的就是 vue 或 react 了,我们在学习这两个框架的过程中,总有一个绕不开的话题:vnode,也就是虚拟 dom。什么是虚拟 DOM,引用一段 vue 官方的解释就是:

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!