diff算法：react与vuediff算法对比，snabbdom.js
Author：zhoulujun Date：
diff算法
传统diff算法循环新旧dom树的所有节点去比较，更新修改的dom
将两颗树中所有的节点一一对比需要O(n²)的复杂度，在对比过程中发现旧节点在新的树中未找到，那么就需要把旧节点删除，删除或者删除一棵树的一个节点(找到一个合适的节点放到被删除的位置)的时间复杂度为O(n)），合起来diff两个树的复杂度就是O(n³)
最开始经典的深度优先遍历DFS算法，其复杂度为O(n^3)，存在高昂的diff成本，然后是cito.js的横空出世，它对今后所有虚拟DOM的算法都有重大影响。它采用两端同时进行比较的算法，将diff速度拉高到几个层次。紧随其后的是kivi.js，在cito.js的基出提出两项优化方案，使用key实现移动追踪及基于key的编辑长度距离算法应用（算法复杂度 为O(n^2)）。但这样的diff算法太过复杂了，于是后来者snabbdom将kivi.js进行简化，去掉编辑长度距离算法，调整两端比较算法。速度略有损失，但可读性大大提高。再之后，就是著名的vue2.0 把snabbdom整个库整合掉了。
因此目前VirtualDOM的主流diff算法趋向一致，在主要diff思路上，snabbdom与react的reconilation方式基本相同。
vue和react使用虚拟dom（virtual DOM），只会在同一层级去比较，如果有变化直接删除当前虚拟dom节点，插入新的节点
vue和react的虚拟DOM的diff算法大致相同，其核心是基于两个简单的假设:
两个相同的组件产生类似的DOM结构，不同的组件产生不同的DOM结构
同一层级的一组节点，他们可以通过唯一的id进行区分
(优化的)diff三点策略:
web UI中DOM节点跨层级的移动操作特别少，可以忽略不计。
拥有相同类型的两个组件将会生成相似的树形结构，拥有不同类型的两个组件将会生成不同树形结构。
对于同一层级的一组自节点，他们可以通过唯一id进行区分。
所以，比较只会在同层级进行, 不会跨层级比较
react：
分三个策略：
component diff(组件间的比较/同级比较)： 拥有相同类的两个组件 生成相似的树形结构，拥有不同类的两个组件 生成不同的树形结构。
tree diff (虚拟DOM树分层比较/子节点比较)： Web UI中DOM节点跨层级的移动操作特别少，可以忽略不计
element diff(元素间比较/key比较)： 对于同一层级的一组子节点，通过唯一id区分。
策略的优先级是：1. 同级比较，2. Key 的使用，3. 子节点更新。
tree diff
DOM节点出现了跨层级操作：只有创建节点和删除节点的操作
tree diff 总结：
React通过updateDepth对Virtual DOM树进行层级控制。
对树分层比较，两棵树 只对同一层次节点 进行比较。如果该节点不存在时，则该节点及其子节点会被完全删除，不会再进一步比较。
只需遍历一次，就能完成整棵DOM树的比较。
tree diff 概述：
基于策略一，React 对树的算法进行了简洁明了的优化，即对树进行分层比较，两棵树只会对同一层次的节点进行比较。
既然 DOM 节点跨层级的移动操作少到可以忽略不计，针对这一现象，React 通过 updateDepth 对 Virtual DOM 树进行层级控制，只会对相同颜色方框内的 DOM 节点进行比较，即同一个父节点下的所有子节点。当发现节点已经不存在，则该节点及其子节点会被完全删除掉，不会用于进一步的比较。这样只需要对树进行一次遍历，便能完成整个 DOM 树的比较。
updateChildren: function(nextNestedChildrenElements, transaction, context) {
updateDepth++;
var errorThrown = true;
try {
this._updateChildren(nextNestedChildrenElements, transaction, context);
errorThrown = false;
} finally {
updateDepth--;
if (!updateDepth) {
if (errorThrown) {
clearQueue();
} else {
processQueue();
}
}
}
}分析至此，大部分人可能都存在这样的疑问：如果出现了 DOM 节点跨层级的移动操作，React diff 会有怎样的表现呢？是的，对此我也好奇不已，不如试验一番。
如下图，A 节点（包括其子节点）整个被移动到 D 节点下，由于 React 只会简单的考虑同层级节点的位置变换，而对于不同层级的节点，只有创建和删除操作。当根节点发现子节点中 A 消失了，就会直接销毁 A；当 D 发现多了一个子节点 A，则会创建新的 A（包括子节点）作为其子节点。此时，React diff 的执行情况：create A -> create B -> create C -> delete A。
由此可发现，当出现节点跨层级移动时，并不会出现想象中的移动操作，而是以 A 为根节点的树被整个重新创建，所以：
当进行跨层级的移动操作，react并不是简单的进行移动，而是进行了删除和创建的操作
这是一种影响 React 性能的操作，因此 React 官方建议不要进行 DOM 节点跨层级的操作。
提示：在开发组件时，保持稳定的 DOM 结构会有助于性能的提升。例如，可以通过 CSS 隐藏或显示节点，而不是真的移除或添加 DOM 节点。
component diff React
对不同的组件间的比较，有三种策略
同一类型的两个组件，按原策略（层级比较）继续比较Virtual DOM树即可。
同一类型的两个组件，组件A变化为组件B时，可能Virtual DOM没有任何变化，如果知道这点（变换的过程中，Virtual DOM没有改变），可节省大量计算时间，所以 用户 可以通过 shouldComponentUpdate() 来判断是否需要 判断计算。
不同类型的组件，将一个（将被改变的）组件判断为dirty component（脏组件），从而替换整个组件的所有节点。
注意：如果组件A和组件B的结构相似，但是 React判断是不同类型的组件，则不会比较其结构，而是删除组件A及其子节点，创建组件B及其子节点。
如下图，当 component D 改变为 component G 时，即使这两个 component 结构相似，一旦 React 判断 D 和 G 是不同类型的组件，就不会比较二者的结构，而是直接删除 component D，重新创建 component G 以及其子节点。虽然当两个 component 是不同类型但结构相似时，React diff 会影响性能，但正如 React 官方博客所言：不同类型的 component 是很少存在相似 DOM tree 的机会，因此这种极端因素很难在实现开发过程中造成重大影响的。
element diff
当节点处于同一层级时，diff提供三种节点操作：INSERT_MARKUP（插入）、MOVE_EXISTING（移动）和 REMOVE_NODE（删除）。
插入：组件 C 不在集合（A,B）中，需要插入
删除：
组件D在集合（A,B,D）中，但D的节点已经更改，不能复用和更新，所以需要删除旧的D ，再创建新的。
组件 D 之前在 集合（A,B,D）中，但集合变成新的集合（A,B）了，D 就需要被删除。
移动：组件D已经在集合（A,B,C,D）里了，且集合更新时，D没有发生更新，只是位置改变，如新集合（A,D,B,C），D在第二个，无须像传统diff，让旧集合的第二个B和新集合的第二个D 比较，并且删除第二个位置的B，再在第二个位置插入D，而是（对同一层级的同组子节点） 添加唯一key进行区分，移动即可。
看着上图的 B，React先从新中取得B，然后判断旧中是否存在相同节点B，当发现存在节点B后，就去判断是否移动B。
B在旧 中的index=1，它的lastIndex=0，不满足 index < lastIndex 的条件，因此 B 不做移动操作。此时，一个操作是，lastIndex=(index,lastIndex)中的较大数=1.
看着 A，A在旧的index=0，此时的lastIndex=1，满足index<lastIndex，对A进行移动操作，此时lastIndex=max(index,lastIndex)=1。
看着D，同，不移动，由于D在旧的index=3，比较时，lastIndex=1，所以改变lastIndex=max(index,lastIndex)=3
看着C，同，移动，C在旧的index=2，满足index<lastIndex（lastIndex=3），所以移动。
React 提出优化策略：允许开发者对同一层级的同组子节点，添加唯一 key 进行区分，虽然只是小小的改动，性能上却发生了翻天覆地的变化！
element diff 为diff算法核心，还是的阅读 snabbdom.js 源码分析，如：《Virtual DOM和snabbdom.js》、《解析 snabbdom 源码》
vue：
vue2.0加入了virtual dom，和react拥有相同的 diff 优化原则，差异就在于, diff的过程就是调用patch函数，就像打补丁一样修改真实dom。
Vue 并未完全自主开发一套 Virtual DOM，而是借鉴了另一个开源库snabbdom，其核心算法逻辑代码请参考https://github.com/snabbdom/snabbdom/blob/v0.7.3/src/snabbdom.ts#L179
从数据改变的set方法开始的diff算法如下图所示：
如果新旧两个节点完全不一样了isSameVnode返回false，则整个节点更新，如果节点本身是一样的，就比较他们的子节点
patch
当数据发生改变时，set方法会让调用Dep.notify通知所有订阅者Watcher，订阅者就会调用patch给真实的DOM打补丁
function patch (oldVnode, vnode) {
// 对于同类型节点调用patchVnode(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;
}
function sameVnode (a, b) {
return (
a.key === b.key &&
a.tag === b.tag &&
a.isComment === b.isComment &&
isDef(a.data) === isDef(b.data) &&
sameInputType(a, b)
);
}
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)
}
}
}sameVnode 函数可以解析为什么需要加key优化
updateChildren
updateChildren是vue diff的核心
过程可以概括为：oldCh和newCh各有两个头尾的变量StartIdx和EndIdx，它们的2个变量相互比较，一共有4种比较方式。如果4种比较都没匹配，如果设置了key，就会用key进行比较，在比较的过程中，变量会往中间靠，一旦StartIdx>EndIdx表明oldCh和newCh至少有一个已经遍历完了，就会结束比较
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)
}
}代码很长，解读参照文章下面提到的大神文章。原理示意图如下：
Vue 2.x vs Vue 3.x
Vue2的核心Diff算法采用了双端比较的算法，同时从新旧children的两端开始进行比较，借助key值找到可复用的节点，再进行相关操作。相比React的Diff算法，同样情况下可以减少移动节点次数，减少不必要的性能损耗，更加的优雅
Vue3.x借鉴了 ivi算法和 inferno算法。在创建VNode时就确定其类型，以及在mount/patch的过程中采用位运算来判断一个VNode的类型，在这个基础之上再配合核心的Diff算法，使得性能上较Vue2.x有了提升。(实际的实现可以结合Vue3.x源码看
该算法中还运用了动态规划的思想求解最长递归子序列
具体推荐阅读：《vue3为何向Inferno与ivi靠拢》
参看文章：
传统diff、react优化diff、vue优化diff https://www.jianshu.com/p/398e63dc1969
react，vue diff算法 https://zhuanlan.zhihu.com/p/128623934
聊一聊Diff算法（React、Vue2.x、Vue3.x） https://juejin.im/post/5eabb8776fb9a0437d2b1ecb
https://dennisgo.cn/Articles/Vue/reactive.html
浅谈react diff实现 https://github.com/yinguangyao/blog/issues/27
转载本站文章《diff算法：react与vuediff算法对比，snabbdom.js 》,
请注明出处：https://www.zhoulujun.cn/html/webfront/ECMAScript/jsBase/2020_0628_8489.html