当前位置： 首页 > article >正文

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

article 2024/10/22 11:16:13

文章目录

    • 10.1　双端比较的原理
    • 10.2　双端比较的优势
    • 10.3　非理想状况的处理方式
    • 10.4　添加新元素
    • 10.5　移除不存在的元素
    • 10.6　总结

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

10.1　双端比较的原理

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

如图：

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

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

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

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

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

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

对应有四个节点。

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

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

举例：

在这里插入图片描述
第一轮比较：旧子节点尾和新子节点头 相同，说明旧子节点尾需要到旧子节点头前，即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 移动操作次数更少。


http://www.kler.cn/news/360066.html

相关文章：

  • 如何使用postman进行自动化
  • Milvus 到 TiDB 向量迁移实践
  • 关于游戏行业工作的迷茫
  • Sqlite3 操作笔记
  • Java设计模式：工厂模式详解
  • ERC论文阅读(01)--BiosERC论文阅读笔记
  • 数据结构(8.3_2)——快速排序
  • 校园周边美食探索及分享平台的设计与实现(论文+源码)_kaic
  • 数控机械制造工厂ERP适用范围有哪些
  • STM32-Modbus协议(一文通)
  • ​通过‌组策略编辑器关闭​
  • 计算机毕业设计 基于 Python的考研学习系统的设计与实现 Python毕业设计选题 前后端分离 附源码 讲解 文档
  • Python基础和理论学习
  • IP池与代理池的区别
  • 三品PLM系统解决方案赋能航空制造企业 研发管理升级赢得市场主动
  • 配置nginx服务通过ip访问多网站
  • CISP/NISP二级练习题-第一卷
  • 《逆行人生》观后感
  • 查看台架上已安装的DDH、DE等RPM包
  • Anomalib 1.x 系列之四：输入切片（tiling）