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

前端进阶之最长递增子序列算法和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 提出，可以比较容易实现而且带来带来比较明显的提升；

先处理掉相同的前置节点和后置节点，假如用字符串作为例子