您的位置：首页 > 财经 > 金融 > 成都小程序开发平台_廊坊百度推广代运营_搜索推广和信息流推广的区别_软文范例大全100

成都小程序开发平台_廊坊百度推广代运营_搜索推广和信息流推广的区别_软文范例大全100

2024/11/17 4:49:03 来源：https://blog.csdn.net/karshey/article/details/143040010  浏览:  次   关键词：成都小程序开发平台_廊坊百度推广代运营_搜索推广和信息流推广的区别_软文范例大全100
成都小程序开发平台_廊坊百度推广代运营_搜索推广和信息流推广的区别_软文范例大全100

文章目录

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

版权声明:

本网仅为发布的内容提供存储空间，不对发表、转载的内容提供任何形式的保证。凡本网注明“来源：XXX网络”的作品，均转载自其它媒体，著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处。

我们尊重并感谢每一位作者，均已注明文章来源和作者。如因作品内容、版权或其它问题，请及时与我们联系，联系邮箱：809451989@qq.com，投稿邮箱：809451989@qq.com

最新新闻

热搜词

20222405 2024-2025-1 《网络与系统攻防技术》实验六实验报告 重新开始刷题啦 各种内置函数技巧总结 Springboot 集成Apollo配置中心【记录】 大数据告诉你——垃圾围城，现行的垃圾分类制度，作用到底能有多大？ 基于Java+SSM+JSP+MYSQL实现的宠物领养收养管理系统功能设计与实现一

声明：本站所有新闻及新闻图片来源于其他网站，如有侵权，请及时联系我们！

客户服务 | 关于我们 | 版权声明

版权所有：

Copyright 2024 尧图网 All Rights Reserved.QQ:809451989