建站之星网站建设下载版,wordpress+微官网主题,聊城网站建设开发,南宁模板建站双端Diff算法
双端Diff算法指的是#xff0c;在新旧两组子节点的四个端点之间分别进行比较#xff0c;并试图找到可复用的节点。相比简单Diff算法#xff0c;双端Diff算法的优势在于#xff0c;对于同样的更新场景#xff0c;执行的DOM移动操作次数更少。
简单 Diff 算法…双端Diff算法
双端Diff算法指的是在新旧两组子节点的四个端点之间分别进行比较并试图找到可复用的节点。相比简单Diff算法双端Diff算法的优势在于对于同样的更新场景执行的DOM移动操作次数更少。
简单 Diff 算法单向 Diff 工作原理简单 Diff 算法从一个序列的起始位置开始逐个比较元素找出不同之处。 特点 顺序性仅从一个方向进行比较一旦发现不同之处就会停止继续比较。 复杂度时间复杂度为 O(n)其中 n 是序列的长度。 结果不唯一因为只按照一个方向进行比较可能会忽略一些潜在的更优的匹配方式。
双端 Diff 算法双向 Diff
工作原理双端 Diff 算法同时从两个序列的起始位置开始向中间移动逐个比较元素找出不同之处。特点 - 双向性同时从两个方向进行比较可以更全面地考虑匹配情况。 - 优化效率通过跳过相同的前缀和后缀部分减少了比较的次数提高了效率。 - 复杂度时间复杂度为 O(nm)其中 n 和 m 分别是两个序列的长度。 - 结果更准确考虑了更多的匹配可能性得到更准确的差异结果。
双端Diff算法的比较方式 双端Diff算法是一种同时对新旧两组子节点的两个端点进行比较的算法因此我们需要四个索引值分别指向新旧两组节点的端点。
function patchChildren(n1, n2, container) {if (typeof n2.children string) {// 省略部分代码} else if (Array.isArray(n2.children)) {// 封装 patchKeyedChildren 函数处理两组子节点patchKeyedChildren(n1, n2, container);} else {// 省略部分代码}
}
function patchKeyedChildren(n1, n2, container) {const oldChildren n1.children;const newChildren n2.children;// 四个索引值let oldStartIdx 0;let oldEndIdx oldChildren.length - 1;let newStartIdx 0;let newEndIdx newChildren.length - 1;// 四个索引指向的 vnode 节点let oldStartVNode oldChildren[oldStartIdx];let oldEndVNode oldChildren[oldEndIdx];let newStartVNode newChildren[newStartIdx];let newEndVNode newChildren[newEndIdx];
}上面的代码中我们将两组子节点的打补丁工程封装到了 patchKeyedChildren 函数中。该函数中先获取两组新旧子节点 oldChildren 和 newChildren然后创建四个索引值分别指向新旧两组子节点的收尾即 oldStartIdx简称为旧前、oldEndIdx简称为旧后、newStartIdx简称为新前、newEndIdx简称为新后以及四个索引值对应的 vnode。其中 oldStartVNode 和 oldEndVNode 是旧的一组子节点的第一个节点和最后一个节点newStartVNode 和 newEndVNode 则是新的一组子节点的第一个子节点和最后一个子节点。
双端比较每一轮均分为四个步骤
比较旧的一组子节点的第一个子节点p-1简称为旧前于新的一组子节点的第一个子节点p-4简称为新前看看他们是否相同。由于两者的 key 值不同因此不相同不可复用于是什么都不做。比较旧的一组子节点的最后一个子节点p-4简称为旧后于新的一组子节点的最后一个子节点p-3简称为新后看看他们是否相同。由于两者的 key 值不同因此不相同不可复用于是什么都不做。比较旧的一组子节点的第一个子节点p-1简称为旧前于新的一组子节点的最后一个子节点p-3简称为新后看看他们是否相同。由于两者的 key 值不同因此不相同不可复用于是什么都不做。比较旧的一组子节点的最后一个子节点p-4简称为旧后于新的一组子节点的第一个子节点p-4简称为新前。由于他们的 key 相同因此可以进行DOM复用。
四个步骤命中任何一步均说明命中的节点可以进行DOM复用因此后续只需要进行DOM移动操作完成更新即可。
function patchKeyedChildren(n1, n2, container) {const oldChildren n1.children;const newChildren n2.children;// 四个索引值let oldStartIdx 0;let oldEndIdx oldChildren.length - 1;let newStartIdx 0;let newEndIdx newChildren.length - 1;// 四个索引指向的 vnode 节点let oldStartVNode oldChildren[oldStartIdx];let oldEndVNode oldChildren[oldEndIdx];let newStartVNode newChildren[newStartIdx];let newEndVNode newChildren[newEndIdx];while(oldEndIdx oldStartIdx newEndIdx newStartIdx) {if (oldStartVNode.key newStartVNode.key) {// 步骤一oldStartVNode 和 newStartVNode 比较// 调用 patch 函数在 oldStartIdx 和 newStartIdx 之间打补丁patch(oldStartVNode, newStartVNode, container);// 更新相关索引到下一个位置oldStartVNode oldChildren[oldStartIdx];newStartVNode newEndVNode[newEndIdx];} else if(oldEndVNode.key newEndVNode.key) {// 步骤二oldEndVNode 和 newEndVNode 比较// 节点在新的顺序中仍然处于尾部不需要移动但仍需打补丁patch(oldEndVNode, newEndVNode, container);// 更新索引和头尾部节点变量newEndVNode newChildren[--newEndIdx];oldEndVNode oldChildren[--oldEndIdx];} else if(oldStartVNode.key newEndVNode.key) {// 步骤三oldStartVNode 和 newEndVNode 比较// 调用 patch 函数在 oldStartIdx 和 newEndIdx之间打补丁patch(oldStartVNode, newEndVNode, container);// 将旧的一组子节点的头部节点对应的真是节点 DOM 节点 oldStartVNode.el 移动// 到旧一组子节点的尾部节点对应的真实 DOM 节点后面insert(oldStartVNode.el, container, oldEndVNode.el.nextSibiling);// 更新相关索引到下一个位置oldStartVNode oldChildren[oldStartIdx];newEndVNode newChildren[--newEndIdx];} else if(oldEndVNode.key newStartVNode.key) {// 步骤四oldEndVNode 和 newStartVNode 比较// 仍然需要调用 patch 函数进行打补丁patch(oldEndVNode, newStartVNode, container);// 移动 DOM 操作// oldEndVNode.el 移动到 oldStartVNode.el 前面insert(oldEndVNode.el, container, oldStartVNode.el);// 移动 DOM 完成后更新索引值并指向下一个位置oldEndVNode oldChildren[--oldEndIdx];newStartVNode newChildren[newStartIdx];}}
}上述代码
步骤四中找到了具有相同key值的节点说明原来处于尾部的节点在新的顺序周中应该处于头部。因此我们只需要以头部元素 oldStartVNode.el 作为锚点将尾部元素 oldEndVNode.el 移动到锚点前面即可移动前仍然需要调用 patch 函数在新旧虚拟节点之间打补丁。然后还需要更新索引oldEndIdx 向上移动newStartIdx 向下移动同时更新 oldEndVNode 和 newStartVNode。步骤三中找到了具有相同key值的节点说明原来处于头部的节点在新的顺序中应该处于尾部。因此我们需要以 oldEndVNode.el.nextSibiling旧一组节点的尾部节点对应的真实 DOM 节点的兄弟节点 作为锚点将头部元素 oldStartVNode.el 移动到锚点之前即可移动前需要调用 patch 函数对新旧虚拟节点进行打补丁然后更新相关的索引oldStartIdx 向下移动newEndIdx 向上移动同时更新 oldStartVNode 和 newEndVNode。步骤二中找到了具有相同key值的节点说明原来处于尾部的节点在新的顺序中仍然处于尾部因此不需要进行移动调用 patch 函数进行新旧虚拟节点打补丁然后更新相关索引newEndIdx 和 oldEndIdx 均向上移动同时更新 newEndVNode 和 oldEndVNode。步骤一中找到了具有相同key值的节点说明原来处于头部的节点在新的顺序中仍然处于头部因此不需要进行移动调用 patch 函数进行新旧虚拟节点打补丁然后更新相关索引oldStartIdx 和 newEndIdx 均向下移动同时更新 oldStartVNode 和 newStartVNode。
非理想状况的处理方式 在四个步骤的比较过程中都无法找到可复用的节点此时我们通过增加额外的处理步骤盘外招来处理这种情况拿新的一组子节点中的头部节点去旧的一组子节点中寻找如下代码所示
while(oldEndIdx oldStartIdx newEndIdx newStartIdx) {if (oldStartVNode.key newStartVNode.key) {// 省略部分代码} else if(oldEndVNode.key newEndVNode.key) {// 省略部分代码} else if(oldStartVNode.key newEndVNode.key) {// 省略部分代码} else if(oldEndVNode.key newStartVNode.key) {// 省略部分代码} else {// 遍历旧的一组节点试图寻找与 newStartVNode 拥有相同 key 值的节点// idxInOld 就是新的一组子节点的头部节点在旧的一组节点中的索引const idxInOld oldChildren.findIndex(ele ele.key newStartVNode.key);}
}上图中我们拿新的一组子节点的头部节点p-2去旧的一组子节点中查找在索引为1的位置找到了可复用的节点。然后将节点p-2对应的真实 DOM 节点移动到当前旧的一组子节点的头部节点p-1所对应的真实 DOM 节点之前。
while(oldEndIdx oldStartIdx newEndIdx newStartIdx) {if (oldStartVNode.key newStartVNode.key) {// 省略部分代码} else if(oldEndVNode.key newEndVNode.key) {// 省略部分代码} else if(oldStartVNode.key newEndVNode.key) {// 省略部分代码} else if(oldEndVNode.key newStartVNode.key) {// 省略部分代码} else {// 遍历旧的一组节点试图寻找与 newStartVNode 拥有相同 key 值的节点// idxInOld 就是新的一组子节点的头部节点在旧的一组节点中的索引const idxInOld oldChildren.findIndex(ele ele.key newStartVNode.key);// idxInOld 0说明找了可复用的节点并且需要将其对应的真实 DOM 移动到头部if (idxInOld) {// idxInOld 位置对应的 vnode 就是需要移动的节点const vnodeToMove oldChildren[idxInOld];// 不要忘记除移动操作之外还应该打补丁patch(vnodeToMove, newStartVNode, container);// 将 vnodeToMove.el 移动到头部节点 oldStartVNode.el 之前因此将后者作为锚点insert(vnodeToMove.el, container, oldStartVNode.el);// 由于位置 idxInOld 处的节点所对应的真实 DOM 已经移动了别处因此将其设置为 undefinedoldChildren[idxInOld] undefined;// 最后更新 newStartIdx 到下一个位置newStartVNode newChildren[newStartIdx];}}
}上面代码中首先判断 idxInOld是否大于0条件成立说明找到了可复用的节点然后将该节点进行移动。先获取需要移动的节点oldChildren[idxInOld]移动前进行打补丁然后找到锚点oldStartVNode.el调用 insert 函数完成节点移动。移动完成后需要将 oldChildren[idxInOld] 设置为undefined同时更新 newStartIdx 向下移动。 然后再进行双端Diff的四个步骤进行节点移动和更新操作。由于旧的一组子节点中存在 undefined说明该节点已经被处理过直接跳过即可因此我们需要对代码进行补充。
while(oldEndIdx oldStartIdx newEndIdx newStartIdx) {// 增加两个判断分支如果头部节点为undefined说明该节点被处理过直接跳到下一个位置if (!oldStartVNode) {oldStartVNode oldChildren[oldStartIdx];} else if (!oldEndVNode) {oldEndVNode oldChildren[--endStartIdx];} else if (oldStartVNode.key newStartVNode.key) {// 省略部分代码} else if(oldEndVNode.key newEndVNode.key) {// 省略部分代码} else if(oldStartVNode.key newEndVNode.key) {// 省略部分代码} else if(oldEndVNode.key newStartVNode.key) {// 省略部分代码} else {// 遍历旧的一组节点试图寻找与 newStartVNode 拥有相同 key 值的节点// idxInOld 就是新的一组子节点的头部节点在旧的一组节点中的索引const idxInOld oldChildren.findIndex(ele ele.key newStartVNode.key);// idxInOld 0说明找了可复用的节点并且需要将其对应的真实 DOM 移动到头部if (idxInOld) {// idxInOld 位置对应的 vnode 就是需要移动的节点const vnodeToMove oldChildren[idxInOld];// 不要忘记除移动操作之外还应该打补丁patch(vnodeToMove, newStartVNode, container);// 将 vnodeToMove.el 移动到头部节点 oldStartVNode.el 之前因此将后者作为锚点insert(vnodeToMove.el, container, oldStartVNode.el);// 由于位置 idxInOld 处的节点所对应的真实 DOM 已经移动了别处因此将其设置为 undefinedoldChildren[idxInOld] undefined;// 最后更新 newStartIdx 到下一个位置newStartVNode newChildren[newStartIdx];}}
}添加新元素
前面说了非理想情况的处理即在一轮比较过程中不会命中四个步骤中的任何一步。这时我们会拿新的一组子节点中的头部节点去旧的一组子节点中寻找可复用的节点然而并非总能找到。如下所示 我们发现经过四个步骤均没有命中且p-4节点在旧的一组也没有相同的 key 值对应的节点因此可得p-4节点是一个新增节点我们应该将该节点挂载到正确的位置上。因为p-4节点是新的一组子节点中的头部节点所以需要将它挂载到当前头部节点旧的一组子节点的头部节点p-1的前面即可。
while(oldEndIdx oldStartIdx newEndIdx newStartIdx) {// 增加两个判断分支如果头部节点为undefined说明该节点被处理过直接跳到下一个位置if (!oldStartVNode) {oldStartVNode oldChildren[oldStartIdx];} else if (!oldEndVNode) {oldEndVNode oldChildren[--endStartIdx];} else if (oldStartVNode.key newStartVNode.key) {// 省略部分代码} else if(oldEndVNode.key newEndVNode.key) {// 省略部分代码} else if(oldStartVNode.key newEndVNode.key) {// 省略部分代码} else if(oldEndVNode.key newStartVNode.key) {// 省略部分代码} else {// 遍历旧的一组节点试图寻找与 newStartVNode 拥有相同 key 值的节点// idxInOld 就是新的一组子节点的头部节点在旧的一组节点中的索引const idxInOld oldChildren.findIndex(ele ele.key newStartVNode.key);// idxInOld 0说明找了可复用的节点并且需要将其对应的真实 DOM 移动到头部if (idxInOld) {// idxInOld 位置对应的 vnode 就是需要移动的节点const vnodeToMove oldChildren[idxInOld];// 不要忘记除移动操作之外还应该打补丁patch(vnodeToMove, newStartVNode, container);// 将 vnodeToMove.el 移动到头部节点 oldStartVNode.el 之前因此将后者作为锚点insert(vnodeToMove.el, container, oldStartVNode.el);// 由于位置 idxInOld 处的节点所对应的真实 DOM 已经移动了别处因此将其设置为 undefinedoldChildren[idxInOld] undefined;// 最后更新 newStartIdx 到下一个位置newStartVNode newChildren[newStartIdx];} else {// 将 newStartVNode 作为新的节点挂载到头部使用当前头部节点 oldStartVNode.el 作为锚点patch(null, newStartVNode, container, oldStartVNode.el);}newStartVNode newChildren[newStartIdx];}
}上面的代码所示当条件 idxInOld 0 不成立时说明 newStartVNode 节点是全新的节点。又由于
newStartVNode 节点是头部节点因此我们应该将其作为新的头部节点进行挂载。因此我们在调用 patch 函数挂载节点时我们使用 oldStartVNode.el 作为锚点。这步操作完成之后新旧两组子节点以及真实 DOM 节点如下图所示。 除了上述新增节点的方式还有另外一种情况如下所示 在经历三轮更新之后新旧两组子节点以及真实 DOM 节点的状态如下图所示 可以发现由于变量 oldStartIdx 的值大于 oldEndIdx 的值满足更新停止的条件因此更新停止。但是观察发现节点p-4在整个更新过程中被遗漏了因此我们添加额外的代码代码如下
while(oldEndIdx oldStartIdx newEndIdx newStartIdx) {// 省略部分代码
}
// 循环结束后检查索引值的情况
if (oldEndIdx oldStartIdx newStartIdx newEndIdx) {// 如果满足条件则说明有新的节点遗留需要挂载他们for (let i newStartIdx; i newEndIdx; i) {const anchor newChildren[newEndIdx 1] ? newChildren[newEndIdx 1].el : null;patch(null, newChildren[i], container, anchor);}
}我们在while循环之后增加了一个if条件语句检查四个索引值的情况。如果满足oldEndIdx oldStartIdx newStartIdx newEndIdx条件说明有新的一组子节点中有遗留的节点需要作为新节点挂载。其中索引值位于 newStartIdx 和 newEndIdx 之间的节点都是新节点。于是我们开启一个for循环遍历这个区间的节点并逐一进行挂载。挂载时的锚点仍然使用当前的头部节点 oldStartVNode.el。
移除不存在的元素
解决了新增节点的问题后我们来讨论关于移除元素的情况如下所示 经过两轮更新后如下所示 我们可以发现此时变量 newStartIdx 的值大于变量 newEndIdx 的值满足更新停止的条件于是更新结束。但是旧的一组子节点中存在未被处理的节点应该将其移除我们新增额外的代码处理代码如下
while(oldEndIdx oldStartIdx newEndIdx newStartIdx) {// 省略部分代码
}
if (oldEndIdx oldStartIdx newStart newEndIdx) {// 添加新节点// 省略部分代码
} else if (oldEndIdx oldStartIdx newStart newEndIdx) {// 移除操作for (let i oldStartIdx; i oldEndIdx; i) {unmount(oldChildren[i]);}
}与处理新增节点类似我们在while循环结束后又增加了一个 else…if 分支用于卸载已经不存在的节点。索引值位于 oldStartIdx 和 oldEndIdx 区间的节点都应该被卸载于是我们开启一个 for 循环将他们逐一卸载。
完整的代码如下
function patchKeyedChildren(n1, n2, container) {const oldChildren n1.children;const newChildren n2.children;// 四个索引值let oldStartIdx 0;let oldEndIdx oldChildren.length - 1;let newStartIdx 0;let newEndIdx newChildren.length - 1;// 四个索引指向的 vnode 节点let oldStartVNode oldChildren[oldStartIdx];let oldEndVNode oldChildren[oldEndIdx];let newStartVNode newChildren[newStartIdx];let newEndVNode newChildren[newEndIdx];while(oldEndIdx oldStartIdx newEndIdx newStartIdx) {// 增加两个判断分支如果头部节点为undefined说明该节点被处理过直接跳到下一个位置if (!oldStartVNode) {oldStartVNode oldChildren[oldStartIdx];} else if (!oldEndVNode) {oldEndVNode oldChildren[--endStartIdx];} else if (oldStartVNode.key newStartVNode.key) {// 第一步oldStartVNode 和 newStartVNode 比较// 调用 patch 函数在 oldStartIdx 和 newStartIdx 之间打补丁patch(oldStartVNode, newStartVNode, container);// 更新相关索引到下一个位置oldStartVNode oldChildren[oldStartIdx];newStartVNode newEndVNode[newEndIdx];} else if(oldEndVNode.key newEndVNode.key) {// 第二步oldEndVNode 和 newEndVNode 比较// 节点在新的顺序中仍然处于尾部不需要移动但仍需打补丁patch(oldEndVNode, newEndVNode, container);// 更新索引和头尾部节点变量newEndVNode newChildren[--newEndIdx];oldEndVNode oldChildren[--oldEndVNode];} else if(oldStartVNode.key newEndVNode.key) {// 第三步oldStartVNode 和 newEndVNode 比较// 调用 patch 函数在 oldStartIdx 和 newEndIdx之间打补丁patch(oldStartVNode, newEndVNode, container);// 将旧的一组子节点的头部节点对应的真是节点 DOM 节点 oldStartVNode.el 移动// 到旧一组子节点的尾部节点对应的真实 DOM 节点后面insert(oldStartVNode.el, container, oldEndVNode.el.nextSibiling);// 更新相关索引到下一个位置oldStartVNode oldChildren[oldStartIdx];newEndVNode newChildren[--newEndIdx];} else if(oldEndVNode.key newStartVNode.key) {// 第四步oldEndVNode 和 newStartVNode 比较// 仍然需要调用 patch 函数进行打补丁patch(oldEndVNode, newStartVNode, container);// 移动 DOM 操作// oldEndVNode.el 移动到 oldStartVNode.el 前面insert(oldEndVNode.el, container, oldStartVNode.el);// 移动 DOM 完成后更新索引值并指向下一个位置oldEndVNode oldChildren[--oldEndIdx];newStartVNode newChildren[newStartIdx];} else {// 遍历旧的一组节点试图寻找与 newStartVNode 拥有相同 key 值的节点// idxInOld 就是新的一组子节点的头部节点在旧的一组节点中的索引const idxInOld oldChildren.findIndex(ele ele.key newStartVNode.key);// idxInOld 0说明找了可复用的节点并且需要将其对应的真实 DOM 移动到头部if (idxInOld) {// idxInOld 位置对应的 vnode 就是需要移动的节点const vnodeToMove oldChildren[idxInOld];// 不要忘记除移动操作之外还应该打补丁patch(vnodeToMove, newStartVNode, container);// 将 vnodeToMove.el 移动到头部节点 oldStartVNode.el 之前因此将后者作为锚点insert(vnodeToMove.el, container, oldStartVNode.el);// 由于位置 idxInOld 处的节点所对应的真实 DOM 已经移动了别处因此将其设置为 undefinedoldChildren[idxInOld] undefined;// 最后更新 newStartIdx 到下一个位置newStartVNode newChildren[newStartIdx];} else {// 将 newStartVNode 作为新的节点挂载到头部使用当前头部节点 oldStartVNode.el 作为锚点patch(null, newStartVNode, container, oldStartVNode.el);}newStartVNode newChildren[newStartIdx];}// 循环结束后检查索引值的情况if (oldEndIdx oldStartIdx newStartIdx newEndIdx) {// 如果满足条件则说明有新的节点遗留需要挂载他们for (let i newStartIdx; i newEndIdx; i) {const anchor newChildren[newEndIdx 1] ? newChildren[newEndIdx 1].el : null;patch(null, newChildren[i], container, anchor);}}
}
