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

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

article 2024/10/25 2:26:43

文章目录

    • 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 oldEnd<j 成立，说明在预处理过程中，所有旧节点都处理完毕了（开头的j>结尾的oldEnd）
  • 条件2 newEnd>=j成立，说明在预处理后，新节点中，有未处理的节点，即新增节点

因此，索引值在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 <= newEnd
  • j > 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 中的预处理思路，先处理新旧两组子节点中相同的前置节点和相同的后置节点。当前置节点和后置节点全部处理完毕后，如果无法简单地通过挂载新节点或者卸载已经不存在的节点来完成更新，则需要根据节点的索引关系，构造出一个最长递增子序列。最长递增子序列所指向的节点即为不需要移动的节点。


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

相关文章：

  • 梳理一下spring中，与message相关的知识点
  • 物联网消息队列Emqx日志配置及日志追踪以及Centos7上的rc.local开机不执行、git提交的小问题
  • 比较相同机器上 redis和mysql分别单独承载的 最大连接数量
  • 激活函数（sigmoid、tanh、ReLu）
  • 面试官：数据库 delete 表数据，磁盘空间还是被一直占用，为什么?
  • Git文件操作指令和文件状态
  • 文案创作新思路：Python与文心一言API的完美结合
  • 《计算机视觉》—— 基于dlib库的人脸关键部位的轮廓检测
  • 【MySQL】详解表的约束
  • 【途牛旅游网-注册/登录安全分析报告】
  • vue2.x中的数据劫持
  • 视频剪辑和转换gif一体化UI页面【可以解决gif体积过大】
  • 【YOLOv11】制作使用YOLOv11的docker环境
  • 一道面试题：为什么要使用Docker？
  • Java项目-基于springboot框架的智慧外贸系统项目实战(附源码+文档)
  • COVON全意卫生巾凭借其轻薄、透气、绵柔的特点，在东南亚市场上迅速走红
  • 攻坚金融关键业务系统，OceanBase亮相2024金融科技大会
  • 调整Android板子的分辨率
  • 内网python smtplib用ssh隧道通过跳板机发邮件
  • 微积分复习笔记 Calculus Volume 1 - 3.2 he Derivative as a Function
  • 【Linux学习】（3）Linux的基本指令操作
  • 关闭或开启Win11系统的自动更新
  • springboot接口Get请求实体类入参
  • VirtualBox、VMware安装Linux后重启再次进入安装界面的问题解决
  • 微信小程序用开发工具在本地真机调试可以正常访问摄像头，发布了授权后却无法访问摄像头，解决方案
  • 钡铼技术R10工业4G路由服务智慧城市建设