【Vue.js设计与实现】第三篇第10章：渲染器-双端 Diff 算法-阅读笔记

🕗 发布于 2024-10-19 05:59 vue.js 算法笔记

文章目录

系列目录：【Vue.js设计与实现】阅读笔记目录

10.1　双端比较的原理

简单 Diff 算法的问题在于，它对 DOM 的移动操作并不是最优的。

如图：

在这里插入图片描述
按照简单Diff算法，它的移动有两次如下：

在这里插入图片描述
然而，上述更新过程并非最优解。在这个例子中，其实只需要通过一步DOM 节点的移动操作即可完成更新，即只需要把真实 DOM 节点 p-3 移动到真实 DOM 节点 p-1 前面：

在这里插入图片描述
简单Diff算法做不到这点，但双端Diff算法可以。接下来将介绍此算法。

双端 Diff 算法是一种同时对新旧两组子节点的两个端点进行比较的算法。

在这里插入图片描述
如图，有四个索引：

新子节点头
新子节点尾
旧子节点头
旧子节点尾

对应有四个节点。

比较新子节点头和旧子节点头，若相同，说明想从旧到新，旧节点头不需要动，更新新旧子节点头的索引和节点即可
比较新子节点尾和旧子节点尾，若相同，说明想从旧到新，旧节点尾不需要动，更新新旧子节点尾的索引和节点即可
比较旧子节点头和新子节点尾，若相同，说明想从旧到新，旧子节点头需要到旧子节点尾后，还要更新旧子节点头和新子节点尾的索引和节点
比较旧子节点尾和新子节点头，若相同，说明想从旧到新，旧子节点尾需要到旧子节点头前，还要更新旧子节点尾和新子节点头的索引和节点

一致循环上述过程，知道新/旧节点头尾相遇。

举例：

在这里插入图片描述
第一轮比较：旧子节点尾和新子节点头 相同，说明旧子节点尾需要到旧子节点头前，即4到1前，更新索引，即：

在这里插入图片描述
第二轮比较：新子节点尾和旧子节点尾相同，不需要移动，更新索引，即：

在这里插入图片描述
第三轮比较：旧子节点头和新子节点尾相同，旧子节点头需要到旧子节点尾后，即1到2后（此时2是旧子节点尾），更新索引，即：

在这里插入图片描述
第四轮比较：新子节点头和旧子节点头相同，结束。

代码：

const patchKeyedChildren = (n1, n2, container) => {
const oldChildren = n1.children;
const newChildren = n2.children;
// 四个索引值
let oldStartIdx = 0,
oldEndIdx = oldChildren.length - 1,
newStartIdx = 0,
newEndIdx = newChildren.length - 1;
// 四个索引值指向的vnode节点
let oldStartVNode = oldChildren[oldStartIdx],
oldEndVNode = oldChildren[oldEndIdx],
newStartVNode = newChildren[newStartIdx],
newEndVNode = newChildren[newEndIdx];

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (oldStartVNode.key === newStartVNode.key) {
// 第一步
patch(oldStartVNode, newStartVNode, container);
oldStartVNode = oldChildren[++oldStartIdx];
newStartVNode = newChildren[++newStartIdx];
} else if (oldEndVNode.key === newEndVNode.key) {
// 第二步
// 都在尾部，不需要移动
patch(oldEndVNode, newEndVNode, container);
oldEndVNode = oldChildren[--oldEndIdx];
newEndVNode = newChildren[--newEndIdx];
} else if (oldStartVNode.key === newEndVNode.key) {
// 第三步
patch(oldStartVNode, newEndVNode, container);
insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling);
oldStartVNode = oldChildren[++oldStartIdx];
newEndVNode = newChildren[--newEndIdx];
} else if (oldEndVNode.key === newStartVNode.key) {
// 第四步
patch(oldEndVNode, newStartVNode, container);
// oldEndVNode移到oldStartVNode前
insert(oldEndVNode.el, container, oldStartVNode.el);
// 更新索引值
oldEndVNode = oldChildren[--oldEndIdx];
newStartVNode = newChildren[++newStartIdx];
}
}
};

const patchChildren = (n1, n2, container) => {
if (typeof n2.children === "string") {
// ...
} else if (Array.isArray(n2.children)) {
// 封装patchKeyChildren函数处理两组子节点
patchKeyedChildren(n1, n2, container);
} else {
// ...
}
};

10.2　双端比较的优势

比普通Diff优势大，显然的。不赘述了。

10.3　非理想状况的处理方式

上述例子都是比较理想的例子：每一轮比较都会命中四个步骤中的一个。实际上可能出现都没命中的情况。

如：

在这里插入图片描述
解决方法：通过增加额外的处理步骤来处理这种非理想情况。 拿新的一组子节点中的头部节点去旧的一组子节点中寻找。若找到，则需要把它提到旧节点头的前面，并把原本位置的置为undefined，表示此节点已经处理过。

else {
// 四个条件都没有命中:在旧节点中找到跟newStartVNode一样的节点
const idxInOld = oldChildren.findIndex(
(vnode) => vnode.key === newStartVNode.key
);

if (idxInOld > 0) {
// 存在
const vnodeToMove = oldChildren[idxInOld];
patch(vnodeToMove, newStartVNode, container);
// 将它移到头部节点之前
insert(vnodeToMove.el, container, oldStartVNode.el);
// 移走后，原来位置置undefined
oldChildren[idxInOld] = undefined;
// 更新newStartIdx位置
newStartVNode = newChildren[++newStartIdx];
}
}

然后就可以开始循环操作：是否满足四个条件，不满足则在旧节点列表中新节点头。

注意，已处理过的节点为undefined，我们要在代码中增加对它的处理。

// 若头尾节点为undefined,说明此节点已经处理过，需要更新索引，且这两种情况一个循环最多只会出现其中之一
if (!oldStartVNode) {
oldStartVNode = oldChildren[++oldStartIdx];
} else if (!oldEndVNode) {
oldEndVNode = oldChildren[--oldEndIdx];
} else if (oldStartVNode.key === newStartVNode.key) {
// ...
}

上图diff步骤如下：

新子节点头在旧节点中找到，挪到旧节点头前，对应旧节点原有位置变为undefined：

在这里插入图片描述
更新索引：

满足条件4：

在这里插入图片描述
满足条件1：

在这里插入图片描述
最后满足条件1：

在这里插入图片描述
更新完毕。

完整代码：

const patchKeyedChildren = (n1, n2, container) => {
const oldChildren = n1.children;
const newChildren = n2.children;
// 四个索引值
let oldStartIdx = 0,
oldEndIdx = oldChildren.length - 1,
newStartIdx = 0,
newEndIdx = newChildren.length - 1;
// 四个索引值指向的vnode节点
let oldStartVNode = oldChildren[oldStartIdx],
oldEndVNode = oldChildren[oldEndIdx],
newStartVNode = newChildren[newStartIdx],
newEndVNode = newChildren[newEndIdx];

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
// 若头尾节点为undefined,说明此节点已经处理过，需要更新索引，且这两种情况一个循环最多只会出现其中之一
if (!oldStartVNode) {
oldStartVNode = oldChildren[++oldStartIdx];
} else if (!oldEndVNode) {
oldEndVNode = oldChildren[--oldEndIdx];
} else if (oldStartVNode.key === newStartVNode.key) {
// 第一步
patch(oldStartVNode, newStartVNode, container);
oldStartVNode = oldChildren[++oldStartIdx];
newStartVNode = newChildren[++newStartIdx];
} else if (oldEndVNode.key === newEndVNode.key) {
// 第二步
// 都在尾部，不需要移动
patch(oldEndVNode, newEndVNode, container);
oldEndVNode = oldChildren[--oldEndIdx];
newEndVNode = newChildren[--newEndIdx];
} else if (oldStartVNode.key === newEndVNode.key) {
// 第三步
patch(oldStartVNode, newEndVNode, container);
insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling);
oldStartVNode = oldChildren[++oldStartIdx];
newEndVNode = newChildren[--newEndIdx];
} else if (oldEndVNode.key === newStartVNode.key) {
// 第四步
patch(oldEndVNode, newStartVNode, container);
// oldEndVNode移到oldStartVNode前
insert(oldEndVNode.el, container, oldStartVNode.el);
// 更新索引值
oldEndVNode = oldChildren[--oldEndIdx];
newStartVNode = newChildren[++newStartIdx];
} else {
// 四个条件都没有命中:在旧节点中找到跟newStartVNode一样的节点
const idxInOld = oldChildren.findIndex(
(vnode) => vnode.key === newStartVNode.key
);

if (idxInOld > 0) {
// 存在
const vnodeToMove = oldChildren[idxInOld];
patch(vnodeToMove, newStartVNode, container);
// 将它移到头部节点之前
insert(vnodeToMove.el, container, oldStartVNode.el);
// 移走后，原来位置置undefined
oldChildren[idxInOld] = undefined;
// 更新newStartIdx位置
newStartVNode = newChildren[++newStartIdx];
}
}
}
};

10.4　添加新元素

若有新元素在头部，且四个条件都未满足，如图：

在这里插入图片描述
直接在旧头部节点之前挂载即可：

// 不满足四个条件的else
if (idxInOld > 0) {
// 存在
const vnodeToMove = oldChildren[idxInOld];
patch(vnodeToMove, newStartVNode, container);
// 将它移到头部节点之前
insert(vnodeToMove.el, container, oldStartVNode.el);
// 移走后，原来位置置undefined
oldChildren[idxInOld] = undefined;
} else {
// 不存在:直接挂载到头节点之前
patch(null, newStartVNode, container, oldStartVNode.el);
}

// 更新newStartIdx位置
newStartVNode = newChildren[++newStartIdx];

在这里插入图片描述
若有新元素在头部，但有条件满足，如图：

在这里插入图片描述
那么上述代码没法处理这种情况，因为会直接漏掉新节点：

在这里插入图片描述

因此，我们也要处理这种情况：

while(...){
// ...
}
// 处理新增节点被遗漏的情况
if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {
for (let i = newStartIdx; i <= newEndIdx; i++) {
patch(null, newChildren[i], container, oldStartVNode.el);
}
}

至于为什么判断条件是：oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx，如图：

在这里插入图片描述

10.5　移除不存在的元素

如图：

在这里插入图片描述

发现有多余的节点要删除，判断条件为：newEndIdx < newStartIdx && oldStartIdx <= oldEndIdx

// 处理新增节点被遗漏的情况
if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {
// ...
} else if (newEndIdx < newStartIdx && oldStartIdx <= oldEndIdx) {
// 移除
for (let i = oldStartIdx; i <= oldEndIdx; i++) {
unmount(oldChildren[i]);
}
}

10.6　总结

本章我们介绍了双端 Diff 算法的原理及其优势。

双端 Diff 算法指的是，在新旧两组子节点的四个端点之间分别进行比较，并试图找到可复用的节点。 相比简单 Diff 算法，双端 Diff 算法的优势在于，对于同样的更新场景，执行的 DOM 移动操作次数更少。

原文地址：https://blog.csdn.net/karshey/article/details/143020784

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Flutter在 iOS 中实现无弹窗获取剪切板内容
下一篇：Flutter Scaffold组件

一次性入门三款分布式定时任务调度框架：Quartz、ElasticJob3.0、xxl-job
三款分布式任务调度框架，一篇文章全部入门
阅读更多2024-10-19
Python OpenCV精讲系列 - 目标检测与识别深入理解（二十）
Haar特征是一种简单的图像特征，用于检测局部图像结构的变化。它由一组简单的黑色和白色矩形组成，用于计算图像中不同区域之间的平均像素强度差异。HOG（Histogram of Oriented Gra
阅读更多2024-10-19
OpenMediaVault安装插件以及重置web控制台密码
需要安装好openmediavault-md插件。
阅读更多2024-10-19
快速了解kubernetes中的存储管理
Secret 对象类型用来保存敏感信息，例如密码、OAuth 令牌和 ssh key。- 敏感信息放在 secret 中比放在 Pod 的定义或者容器镜像中来说更加安全和灵活- Pod 可以用两种方式
阅读更多2024-10-19
代理 IP：促进在线教育资源普及与公平的新助力
当某个地区的网络拥堵时，学生可以通过代理 IP 选择其他网络较为畅通的线路，确保学习的顺畅进行。对于一些教育资源匮乏的地区，代理 IP 可以帮助学生访问其他地区的在线教育平台，获取更多的学习资料、课程
阅读更多2024-10-19
代码训练营 day38|LeetCode 62，LeetCode 63
今天主要学习了dp的一系列操作，今天难度不大，有点dp那味儿了加油，坚持打卡的第38天。
阅读更多2024-10-19
Dynamic 3D Gaussians: Tracking by Persistent Dynamic View Synthesis 阅读
Dynamic 3D Gaussians:Tracking by Persistent Dynamic View Synthesis 论文阅读
阅读更多2024-10-19
JS模块化及import、export
本文探讨了模块化编程的背景与目的，强调了通过降低代码重复、提高可读性和便于维护等优势来改善软件开发过程。文章还介绍了五大模块化原则，包括单一职责原则和依赖倒置原则，以确保代码的灵活性和可扩展性。此外，
阅读更多2024-10-19
css 如何根据子元素给他的父元素设置样式
'active' : 'unactive' }">子元素啊根据一个变量来加样式</div>其中能马上想到的就是：这个class的判断可以加在parent后面，但是如果不改变
阅读更多2024-10-19
前端学习---(2)CSS基础
关于文字样式的属性，都具有继承性。这些属性包括：color、 text-开头的、line-开头的、font-开头的。CSS 是用来指定文档如何展示给用户的一门语言——如网页的样式、布局、等等。css语
阅读更多2024-10-19

【Vue.js设计与实现】第三篇第10章：渲染器-双端 Diff 算法-阅读笔记

文章目录

10.1 双端比较的原理

10.2 双端比较的优势

10.3 非理想状况的处理方式

10.4 添加新元素

10.5 移除不存在的元素

10.6 总结

相关文章