前端进阶之最长递增子序列算法和vue.js中的Diff算法

前端进阶之最长递增子序列算法和vue.js中的Diff算法

最长递增子序列

什么是子序列

子序列的概念派生自数组，通过删除（或不删除）数组中的元素而不改变其余元素的顺序，得到的数组就是原数组的子序列。 例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

[Leetcode] 300. 最长递增子序列

最长递增子序列问题是一个经典的算法问题，通过动态规划可以很好地理解和解决这个问题。但是在处理大数据集时，更好的方式是使用二分查找法将时间复杂度优化到 O(nlogn)。

vue.js的Diff算法

在Vue.js中，Diff算法是虚拟DOM算法的核心部分，它负责比较新旧两个虚拟DOM树的差异，并计算出最小的更新操作来应用到真实的DOM上，从而达到渲染性能提高的最终目标。

DOM有哪几种操作：

  1. 挂载；
  2. 卸载；
  3. 修改（文本节点的变更）；

移动DOM总比删除&创建DOM更高效，在获取最大移动次数的前提下，剩下的就是需要添加（新的VDom)和删除（旧的VDom）的dom元素。

  • 判断是否有节点需要移动，以及应该如何移动;
  • 找出那些需要被添加或移除的节点

Vue Diff算法的一些前提

  • 比较只会在同层级进行, 不会跨层级比较；
  • 在比较同层级的多个子节点时，Vue.js会从两端（头部和尾部）开始进行比较，这样可以快速处理那些仅在头部或尾部发生变化的情况；
  • 假如当前节点VNodeType或key不同，Vue.js会认为这是两个完全不同的节点，会进行替换操作。如果节点相同，Vue.js会检查节点的属性和子节点，并递归地应用Diff算法。

vue中用到的一些Diff方式

  1. 简单Diff；
  2. 双端Diff；
  3. 快速Diff；

简单Diff

遍历新旧两组子节点中数量较少的那一组，并逐个调用patch函数进行打补丁，然后比较新旧两组子节点的数量，如果新的一组子节点数量更多，说明有新子节点需要挂载；否则说明在旧的一组子节点中，有节点需要卸载。

另外，可以通过给节点增加属性key作为身份标识符，以此来确定新旧节点的对应关系，从而找出可复用的节点。

然后，拿新的一组子节点中的节点去旧的一组子节点中寻找可复用的节点。如果找到了，则记录该节点的位置索引。我们把这个位置索引称为最大索引。在整个更新过程中，如果一个节点的索引值小于最大索引，则说明该节点对应的真实 DOM 元素需要移动。

双端Diff

  1. 对于新旧两组子节点，首先分别对头部和尾部进行对比，找出未移动的节点。
  2. 在上一步完成后，在对比完成后的基础上，进行交叉对比，即旧头和新尾，旧尾和新头进行对比，进一步找出可复用的节点。
  3. 接下来，在剩余未对比的节点中，找出可复用的节点。先是创建一个Key -> Index 的哈希表，用来记录旧节点的索引顺序。然后通过遍历新的一组节点，根据key找出可复用的节点。
  4. 完成上述三步后，删除未复用的节点，创建新增的节点，并对复用的节点根据新的顺序进行移动操作。

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

快速Diff

这是vue3采用的Diff算法。

通过key确定当前节点是否可复用，假如key相等，则只针对当前节点下的子节点children进行diff。

预处理操作

「去除相同前置和后置元素」 ，此优化由 Neil Fraser 提出，可以比较容易实现而且带来带来比较明显的提升；

先处理掉相同的前置节点和后置节点，假如用字符串作为例子🌰去描述的话，应该是是这样的：

// 预处理之前的数据
let oldStr = "I'm OK"
let newStr = "I am not OK"
// 预处理完成后的数据
oldStr = "'m"
newStr = " am not"

原字符串中相同的前置部分的I 和 后置部分的 OK被处理掉，只保留内容不同的部分。然后再把旧的子字符串（'m）删掉，新的子字符串（ am not）添加进去即可。

但是，对你一定会说但是。

这种情况是比较理想的一种情况，假如没有任何相同的前置和后置节点，且存在乱序的可复用DOM节点，应该如何才能最大限度的减少DOM的操作次数呢？这时候就可以用到最长递增子序列算法了。

为什么最长递增子序列能保证DOM操作次数最少？

子序列的特点就是元素在原数组的中相对位置保持一致，即假如元素x在原数组中处于元素y的后面，那么在子序列中也一定会处在元素y的后面。 现在我们把数组元素换成DOM元素的话，子序列就能保证新旧DOM中的元素位置关系不会变。 最长能保证最多的DOM元素位置关系没有变更，从而确保需要DOM变动的次数最少。

PatchFlag —— 一个小插曲

Vue 3借助PatchFlag实现了靶向更新

在Vue 2中，每次更新都需要进行全量对比，而Vue 3通过引入静态标记来减少非动态内容的对比消耗。这种方法只对比带有标记的部分，从而提高了更新的效率。具体实现是在compile阶段将获取的PatchFlag信息存储到VNode上。当在进行Diff时，针对不同类型的PatchFlag，进行不同的处理处理，以达到降低Diff成本的目的。假如没有标记type信息，则按照传统流程进行full diff。

例如，如果一个节点只有class属性可能变化，那么在patch过程中只需要检查class属性，而不是进行全属性比较。

静态标记使用位运算符进行组合和检查。例如，可以通过|运算符来组合多个标记，使用&运算符来检查某个标记是否存在。

PatchFlag 有哪些类型

  • TEXT：动态文本节点
  • CLASS：动态class绑定
  • STYLE：动态style
  • PROPS：动态属性，不包括类名和样式
  • FULL_PROPS：动态key，当key变化时需要完整的diff算法比较
  • HYDRATE_EVENTS：带有事件监听器的节点
  • STABLE_FRAGMENT：子节点顺序不变的Fragment
  • KEYED_FRAGMENT：带有key属性的Fragment
  • UNKEYED_FRAGMENT：子节点没有key的Fragment
  • NEED_PATCH：只需要non-props修补的元素
  • DYNAMIC_SLOTS：动态的slot
  • DEV_ROOT_FRAGMENT：仅因为用户在模板根级别放置注释而创建的片段（开发时使用的标志）
  • HOISTED：已提升的静态vnode，更新时跳过整个子树
  • BAIL：指示diff算法退出优化模式