传统diff、react优化diff、vue优化diff
前端  /  管理员 发布于 5年前   120
传统diff
计算两颗树形结构差异并进行转换,传统diff算法是这样做的:循环递归每一个节点
比如左侧树a节点依次进行如下对比,左侧树节点b、c、d、e亦是与右侧树每个节点对比
算法复杂度能达到O(n^2),n代表节点的个数
a->e、a->d、a->b、a->c、a->a
查找完差异后还需计算最小转换方式,这其中的原理我没仔细去看,最终达到的算法复杂度是O(n^3)
传统diff算法复杂度达到O(n^3 )这意味着1000个节点就要进行数10亿次的比较,这是非常消耗性能的。react大胆的将diff的复杂度从O(n^3)降到了O(n),他是如何做到的呢
由于web UI中跨级移动操作非常少、可以忽略不计,所以react实现的diff是同层级比较
拥有相同类型的两个组件产生的DOM结构也是相似的,不同类型的两个组件产生的DOM结构则不近相同
对于同一层级的一组子节点,通过分配唯一唯一id进行区分(key值)
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
既然传统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}
patchdiff时调用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) } }}
updateChildrenpatchVnode中有一个重要的概念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会依次移动前三个节点到对应的位置:
123 在
Clash for Windows作者删库跑路了,github已404中评论 按理说只要你在国内,所有的流量进出都在监控范围内,不管你怎么隐藏也没用,想搞你分..原梓番博客 在
在Laravel框架中使用模型Model分表最简单的方法中评论 好久好久都没看友情链接申请了,今天刚看,已经添加。..博主 在
佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 @1111老铁这个不行了,可以看看近期评论的其他文章..1111 在
佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 网站不能打开,博主百忙中能否发个APP下载链接,佛跳墙或极光..路人 在
php中使用hyperf框架调用讯飞星火大模型实现国内版chatgpt功能示例中评论 教程很详细,如果加个前端chatgpt对话页面就完美了..Copyright·© 2019 侯体宗版权所有· 粤ICP备20027696号