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

前端  /  管理员 发布于 6年前   189

传统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对象中，会有如下几种差异类型：

插入：patches[0]:{type:'INSERT_MARKUP',node: newNode }移动：patches[0]: {type: 'MOVE_EXISTING'}删除：patches[0]: {type: 'REMOVE_NODE'}文本内容改变：patches[0]: {type: 'TEXT_CONTENT',content: 'virtual DOM2'}属性改变：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