在郑州做网站,小红书搜索关键词排名,产品包装设计模板,中企动力邮箱文章目录 11.1 相同的前置元素和后置元素11.2 判断是否需要进行 DOM 移动操作11.3 如何移动元素11.4 总结 系列目录#xff1a;【Vue.js设计与实现】阅读笔记目录
非常快的Diff算法。
11.1 相同的前置元素和后置元素
不同于简单 Diff 算法和双端 Diff 算法#xff0c… 文章目录 11.1 相同的前置元素和后置元素11.2 判断是否需要进行 DOM 移动操作11.3 如何移动元素11.4 总结 系列目录【Vue.js设计与实现】阅读笔记目录
非常快的Diff算法。
11.1 相同的前置元素和后置元素
不同于简单 Diff 算法和双端 Diff 算法快速 Diff 算法包含预处理步骤这其实是借鉴了纯文本 Diff 算法的思路。
首先进行全等比较若全等就不用Diff了
if(text1 text2) return再进行预处理处理相同的前缀和后缀如图 const patchKeyedChildren (n1, n2, container) {const newChildren n2.children;const oldChildren n1.children;// 处理相同前置节点j指向新旧两组子节点的开头let j 0;let oldVNode oldChildren[j];let newVNode newChildren[j];// 直到遇到不同key值节点为止while (oldVNode.key newVNode.key) {patch(oldVNode, newVNode, container);j;oldVNode oldChildren[j];newVNode newChildren[j];}// 处理相同后置节点let oldEnd oldChildren.length - 1;let newEnd newChildren.length - 1;oldVNode oldChildren[oldEnd];newVNode newChildren[newEnd];while (oldVNode.key newVNode.key) {patch(oldVNode, newVNode, container);oldEnd--;newEnd--;oldVNode oldChildren[oldEnd];newVNode newChildren[newEnd];}
};预处理相同前后缀后 可以发现还遗留了一个未处理的p-4节点。我们可以很容易看出来这是一个新增节点但是如何得出这是新增节点的结论
我们需要观察三个索引j、newEnd、oldEnd之间的关系
条件1 oldEndj 成立说明在预处理过程中所有旧节点都处理完毕了开头的j结尾的oldEnd条件2 newEndj成立说明在预处理后新节点中有未处理的节点即新增节点
因此索引值在j和newEnd之间的节点都要作为新节点挂载
// 预处理完毕// 挂载新节点
if (j oldEnd j newEnd) {const anchorIndex newEnd 1;const anchor anchorIndex newChildren.length? newChildren[anchorIndex].el: null;while (j newEnd) {patch(null, newChildren[j], container, anchor);}
}以上是新增节点的情况接下来是删除节点的情况。 条件是j newEnd j oldEnd
要卸载j-oldEnd的节点由图知从上到下是从小到大
// 预处理完毕// 挂载新节点
if (j oldEnd j newEnd) {const anchorIndex newEnd 1;const anchor anchorIndex newChildren.length? newChildren[anchorIndex].el: null;while (j newEnd) {patch(null, newChildren[j], container, anchor);}
} else if (j newEnd j oldEnd) {// 卸载旧节点while (j oldEnd) {unmount(oldChildren[j]);}
}11.2 判断是否需要进行 DOM 移动操作
前面的例子都是理想状况去掉前后缀后只需要简单的新增/移除。实际上还会出现不理想的情况如 处理完前后缀后还需要更多的处理。
其实不管是简单Diff、双端Diff还是快速Diff他们的处理规则都相同
判断是否有节点需要移动以及如何移动找出那些需要被添加或移除的节点
接下来我们将判断哪些节点要移动以及如何移动。处理完前后缀后我们会发现j、newEnd和oldEnd不满足上述的两种条件新增/移除
j oldEnd j newEndj newEnd j oldEnd
因此我们需要新增一个else来处理这种情况。
首先我们需要构造一个数组source它的长度等于新的一组子节点在经过预处理之后剩余未处理节点的数量并且 source 中每个元素的初始值都是 -1。
source 数组将用来存储新的一组子节点中的节点在旧的一组子节点中的位置索引后面将会使用它计算出一个最长递增子序列并用于辅助完成 DOM 移动的操作 else {// 构造source数组// 新的一组子节点中剩余未处理节点的数量const count newEnd - j 1;const source new Array(count);source.fill(-1);// source节点存储新节点在旧节点的索引const oldStart j;const newStart j;for (let i oldStart; i oldEnd; i) {const oldVNode oldChildren[i];// 找到具有相同key的可复用节点for (let k newStart; k newEnd; k) {const newVNode newChildren[k];if (oldVNode.key newVNode.key) {patch(oldVNode, newVNode, container);source[k - newStart] i;}}}
}source数组如下 这里需要注意的是由于数组 source 的索引是从 0 开始的而未处理节点的索引未必从 0 开始所以在填充数组时需要使用表达式 k - newStart的值作为数组的索引值。外层循环的变量 i 就是当前节点在旧的一组子节点中的位置索引因此直接将变量 i 的值赋给 source[k - newStart] 即可。 相当于都偏移 k - newStart。
不过上述代码是双层嵌套的循环复杂度可能太高了我们得优化一下我们可以为新的一组子节点构建一张索引表用来存储节点的 key 和节点位置索引之间的映射。 这样就不用循环寻找了直接在索引表新节点 key-i中里拿。
// 构建索引表:新节点 key-i
const keyIndex {};
for (let i newStart; i newEnd; i) {keyIndex[newChildren[i].key] i;
}双层循环就可以改为一层循环
若k存在说明旧节点在新节点中存在可以复用否则卸载。
// 构建索引表:新节点 key-i
const keyIndex {};
for (let i newStart; i newEnd; i) {keyIndex[newChildren[i].key] i;
}for (let i oldStart; i oldEnd; i) {const oldVNode oldChildren[i];const k keyIndex[oldVNode.key];if (typeof k ! undefined) {newVNode newChildren[k];patch(oldVNode, newVNode, container);source[k - newStart] i;} else {// 不存在说明旧节点在新节点中不存在卸载unmount(oldVNode);}
}接下来我们将判断是否需要移动与简单Diff相同找递增的索引递增的索引不需要移动。 否则需要新增moved 和pos
let moved false;
let pos 0;const keyIndex {};
for (let i newStart; i newEnd; i) {keyIndex[newChildren[i].key] i;
}for (let i oldStart; i oldEnd; i) {const oldVNode oldChildren[i];const k keyIndex[oldVNode.key];if (typeof k ! undefined) {newVNode newChildren[k];patch(oldVNode, newVNode, container);source[k - newStart] i;// 判断节点是否需要移动:找递增的索引若存在小于递减的索引说明要移动if (k pos) {moved true;} else {pos k;}} else {unmount(oldVNode);}
}除此之外我们还需要一个数量标识代表已经更新过的节点数量。我们知道已经更新过的节点数量应该小于新的一组子节点中需要更新的节点数量。一旦前者超过后者则说明有多余的节点我们应该将它们卸载。
count就是需要更新的节点数量。新增一个patched表示已更新过的节点数量
// 记录更新过的节点数量
let patched 0;for (let i oldStart; i oldEnd; i) {const oldVNode oldChildren[i];// 如果更新过的节点数量小于需要更新的节点数量则更新if (patched count) {const k keyIndex[oldVNode.key];if (typeof k ! undefined) {newVNode newChildren[k];patch(oldVNode, newVNode, container);source[k - newStart] i;patched;if (k pos) {moved true;} else {pos k;}} else {unmount(oldVNode);}} else {// 如果更新过的节点数量大于需要更新的节点数量则卸载多余节点unmount(oldVNode);}
}完整代码
const patchKeyedChildren (n1, n2, container) {const newChildren n2.children;const oldChildren n1.children;// 处理相同前置节点j指向新旧两组子节点的开头let j 0;let oldVNode oldChildren[j];let newVNode newChildren[j];// 直到遇到不同key值节点为止while (oldVNode.key newVNode.key) {patch(oldVNode, newVNode, container);j;oldVNode oldChildren[j];newVNode newChildren[j];}// 处理相同后置节点let oldEnd oldChildren.length - 1;let newEnd newChildren.length - 1;oldVNode oldChildren[oldEnd];newVNode newChildren[newEnd];while (oldVNode.key newVNode.key) {patch(oldVNode, newVNode, container);oldEnd--;newEnd--;oldVNode oldChildren[oldEnd];newVNode newChildren[newEnd];}// 预处理完毕// 挂载新节点if (j oldEnd j newEnd) {const anchorIndex newEnd 1;const anchor anchorIndex newChildren.length? newChildren[anchorIndex].el: null;while (j newEnd) {patch(null, newChildren[j], container, anchor);}} else if (j newEnd j oldEnd) {// 卸载旧节点while (j oldEnd) {unmount(oldChildren[j]);}} else {// 构造source数组// 新的一组子节点中剩余未处理节点的数量const count newEnd - j 1;const source new Array(count);source.fill(-1);const oldStart j;const newStart j;let moved false;let pos 0;const keyIndex {};for (let i newStart; i newEnd; i) {keyIndex[newChildren[i].key] i;}// 记录更新过的节点数量let patched 0;for (let i oldStart; i oldEnd; i) {const oldVNode oldChildren[i];// 如果更新过的节点数量小于需要更新的节点数量则更新if (patched count) {const k keyIndex[oldVNode.key];if (typeof k ! undefined) {newVNode newChildren[k];patch(oldVNode, newVNode, container);source[k - newStart] i;patched;if (k pos) {moved true;} else {pos k;}} else {unmount(oldVNode);}} else {// 如果更新过的节点数量大于需要更新的节点数量则卸载多余节点unmount(oldVNode);}}}
};11.3 如何移动元素
接下来我们讨论如何进行DOM移动操作。我们有source索引数组[2,3,1,-1] 我们要找source的最长递增子序列它是[2,3]对应的索引是[0,1]。我们重新编号。 在新的一组子节点中重新编号后索引值为0和1的这两个节点在更新前后顺序没有变化。
即旧节点的p-3和p-4不需要移动。
为了完成节点的移动我们还需要创建两个索引值i和s
i指向新的一组子节点中的最后一个节点s指向最长递增子序列中的最后一个元素即上述的[0,1]的1 如上图所示我们去掉了旧的一组子节点和无关的线条、变量。
我们开启一个for循环让i和s按照如图所示的方向移动
// DOM 移动操作
if (moved) {// 计算最长递增子序列 的 索引const seq lis(source);// s指向最长递增子序列的最后一个元素let s seq.length - 1;// i指向新一组节点的最后一个元素let i count - 1;for (i; i 0; i--) {if (i ! seq[s]) {// 说明该节点需要移动} else {s--;}}
}我们按照这样的思路更新判断条件 i ! seq[s]如果节点的索引 i 不等于 seq[s]的值则说明该节点对应的真实 DOM 需要移动。
如图所示还要考虑source[i]-1的情况说明这是一个全新节点需要挂载 if (source[i] -1) {// 说明是新节点要挂载const pos i newStart; // 在新children中的真实位置索引const newVNode newChildren[pos];// 该节点的下一个节点的位置索引const nextPos pos 1;const anchor nextPos newChildren.length? newChildren[nextPos].el: null;patch(null, newVNode, container, anchor);
}挂载完后i--往上走 进行上述2个判断
source[i]是否为-1不是的说明不是一个新节点i!seq[s]成立。说明此节点需要移动。下面不需要判断了
移动节点的实现思路类似于挂载全新节点不同点在于移动节点是通过insert函数完成的
else if (i ! seq[s]) {// 说明该节点需要移动// 该节点在新节点中的真是位置索引const pos i newStart;const newVNode newChildren[pos];const nextPos pos 1;const anchor nextPos newChildren.length? newChildren[nextPos].el: null;// 移动insert(newVNode.el, container, anchor);
} 实现完后状态如下 进行2个判断
source[i]是否为-1不是的说明不是一个新节点i!seq[s]不是的说明它不需要移动不需要移动s--即可
状态如下 进行三个判断得到s–
然后就结束了。 关于获取最长递增子序列可以自行搜索。 move相关代码
// DOM 移动操作
if (moved) {// 计算最长递增子序列 的 索引const seq lis(source);// s指向最长递增子序列的最后一个元素let s seq.length - 1;// i指向新一组节点的最后一个元素let i count - 1;for (i; i 0; i--) {if (source[i] -1) {// 说明是新节点要挂载const pos i newStart; // 在新children中的真实位置索引const newVNode newChildren[pos];// 该节点的下一个节点的位置索引const nextPos pos 1;const anchor nextPos newChildren.length? newChildren[nextPos].el: null;patch(null, newVNode, container, anchor);} else if (i ! seq[s]) {// 说明该节点需要移动// 该节点在新节点中的真是位置索引const pos i newStart;const newVNode newChildren[pos];const nextPos pos 1;const anchor nextPos newChildren.length? newChildren[nextPos].el: null;// 移动insert(newVNode.el, container, anchor);} else {s--;}}
}完整代码
const patchKeyedChildren (n1, n2, container) {const newChildren n2.children;const oldChildren n1.children;// 处理相同前置节点j指向新旧两组子节点的开头let j 0;let oldVNode oldChildren[j];let newVNode newChildren[j];// 直到遇到不同key值节点为止while (oldVNode.key newVNode.key) {patch(oldVNode, newVNode, container);j;oldVNode oldChildren[j];newVNode newChildren[j];}// 处理相同后置节点let oldEnd oldChildren.length - 1;let newEnd newChildren.length - 1;oldVNode oldChildren[oldEnd];newVNode newChildren[newEnd];while (oldVNode.key newVNode.key) {patch(oldVNode, newVNode, container);oldEnd--;newEnd--;oldVNode oldChildren[oldEnd];newVNode newChildren[newEnd];}// 预处理完毕// 挂载新节点if (j oldEnd j newEnd) {const anchorIndex newEnd 1;const anchor anchorIndex newChildren.length? newChildren[anchorIndex].el: null;while (j newEnd) {patch(null, newChildren[j], container, anchor);}} else if (j newEnd j oldEnd) {// 卸载旧节点while (j oldEnd) {unmount(oldChildren[j]);}} else {// 构造source数组// 新的一组子节点中剩余未处理节点的数量const count newEnd - j 1;const source new Array(count);source.fill(-1);const oldStart j;const newStart j;let moved false;let pos 0;const keyIndex {};for (let i newStart; i newEnd; i) {keyIndex[newChildren[i].key] i;}// 记录更新过的节点数量let patched 0;for (let i oldStart; i oldEnd; i) {const oldVNode oldChildren[i];// 如果更新过的节点数量小于需要更新的节点数量则更新if (patched count) {const k keyIndex[oldVNode.key];if (typeof k ! undefined) {newVNode newChildren[k];patch(oldVNode, newVNode, container);source[k - newStart] i;patched;if (k pos) {moved true;} else {pos k;}} else {unmount(oldVNode);}} else {// 如果更新过的节点数量大于需要更新的节点数量则卸载多余节点unmount(oldVNode);}}// DOM 移动操作if (moved) {// 计算最长递增子序列 的 索引const seq lis(source);// s指向最长递增子序列的最后一个元素let s seq.length - 1;// i指向新一组节点的最后一个元素let i count - 1;for (i; i 0; i--) {if (source[i] -1) {// 说明是新节点要挂载const pos i newStart; // 在新children中的真实位置索引const newVNode newChildren[pos];// 该节点的下一个节点的位置索引const nextPos pos 1;const anchor nextPos newChildren.length? newChildren[nextPos].el: null;patch(null, newVNode, container, anchor);} else if (i ! seq[s]) {// 说明该节点需要移动// 该节点在新节点中的真是位置索引const pos i newStart;const newVNode newChildren[pos];const nextPos pos 1;const anchor nextPos newChildren.length? newChildren[nextPos].el: null;// 移动insert(newVNode.el, container, anchor);} else {s--;}}}}
};11.4 总结 快速 Diff 算法在实测中性能最优。它借鉴了文本 Diff 中的预处理思路先处理新旧两组子节点中相同的前置节点和相同的后置节点。当前置节点和后置节点全部处理完毕后如果无法简单地通过挂载新节点或者卸载已经不存在的节点来完成更新则需要根据节点的索引关系构造出一个最长递增子序列。最长递增子序列所指向的节点即为不需要移动的节点。
