- A+
专栏分享：vue2源码专栏，vue3源码专栏，vue router源码专栏，玩具项目专栏，硬核?推荐?
欢迎各位ITer关注点赞收藏???
Vue2 Diff算法可以参考【Vue2.x源码系列08】Diff算法原理
Vue3 Diff算法可以参考【Vue3.x源码系列06】Diff算法原理
在 上一章结尾乱序比对 算法中，可以看到，我们倒序遍历了新的乱序节点，对每一个节点都进行了插入操作（移动节点位置），这就有点浪费性能。
我们能不能尽可能少的移动节点位置，又能保证节点顺序是正确的呢？
例如旧节点 1, 3, 4, 2，新节点 1, 2, 3, 4。那我们完全可以只将 2 移动到 3 前面，只需移动一次！就能保证顺序是正确的！！！
ok！我们可以针对于乱序比对中生成的数组 newIndexToOldIndexMap 获取最长递增子序列
注意！vue3 中的最长递增子序列算法求的是 最长递增子序列的对应索引，下面示例我们用的是最长递增子序列，便于直观理解，可读性＋＋＋
举个实际例子捋一下思路
请听题，有一个数组，[3, 2, 8, 9, 5, 6, 7, 11, 15] ，最终的最长递增子序列是什么？
// [2, 8, 9, 11, 15] No！这一个不是最长递增子序列 // [2, 5, 6, 7, 11, 15] 这一个才是最长的！ 这个时候我们只需移动 9,8,3 三个节点即可，而不是全部节点！增子序列越长，所需要移动的节点次数就越少
我们可以利用 贪心算法 + 二分查找 获取原始的最长递增子序列，时间复杂度：O(NlogN)
// 3 // 2（2替换3） // 2, 8 // 2, 8, 9 // 2, 5, 9（5替换掉8，二分查找，找到第一个比5大的进行替换，即所有大于当前值的结果中的最小值） // 2, 5, 6（6替换掉9，二分查找，找到第一个比6大的进行替换） // ... // 2, 5, 6, 7, 11, 15（最长递增子序列） 由于贪心算法都是取当前局部最优解，有可能会导致最长递增子序列在原始数组中不是正确的顺序
例如数组：[3, 2, 8, 9, 5, 6, 7, 11, 15, 4]，此算法求得结果如下。虽然序列不对，但序列长度是没问题的，在vue3 中我们会用 前驱节点追溯 来解决此问题
// 2, 4, 6, 7, 11, 15（最长递增子序列） 让我们整理一下思路，用代码实现此算法
-
遍历数组，如果当前这一项比我们最后一项大则直接放到末尾
-
如果当前这一项比最后一项小，需要在序列中通过二分查找找到比当前大的这一项，用他来替换掉
-
前驱节点追溯，替换掉错误的节点
最优情况
function getSequence(arr) { const len = arr.length const result = [0] // 默认以数组中第0个为基准来做序列，注意！！存放的是数组索引 let resultLastIndex // 结果集中最后的索引 for (let i = 0; i < len; i++) { let arrI = arr[i] // 因为在vue newIndexToOldIndexMap 中，0代表需要创建新元素，无需进行位置移动操作 if (arrI !== 0) { resultLastIndex = result[result.length - 1] if (arrI > arr[resultLastIndex]) { // 比较当前项和最后一项的值，如果大于最后一项，则将当前索引添加到结果集中 result.push(i) // 记录索引 continue } } } return result } // 最长递增子序列：[10, 11, 12, 13, 14, 15, 16] // 最长递增子序列索引：[0, 1, 2, 3, 4, 5, 6] const result = getSequence([10, 11, 12, 13, 14, 15, 16, 0]) console.log(result) // [0, 1, 2, 3, 4, 5, 6] 贪心+二分查找
-
遍历数组，如果当前这一项比我们最后一项大则直接放到末尾
-
如果当前这一项比最后一项小，需要在序列中通过二分查找找到比当前大的这一项，用他来替换掉
function getSequence(arr) { const len = arr.length const result = [0] // 默认以数组中第0个为基准来做序列，注意！！存放的是数组 索引 let resultLastIndex // 结果集中最后的索引 let start let end let middle for (let i = 0; i < len; i++) { let arrI = arr[i] // 因为在vue newIndexToOldIndexMap 中，0代表需要创建新元素，无需进行位置移动操作 if (arrI !== 0) { resultLastIndex = result[result.length - 1] if (arrI > arr[resultLastIndex]) { // 比较当前项和最后一项的值，如果大于最后一项，则将当前索引添加到结果集中 result.push(i) // 记录索引 continue } // 这里我们需要通过二分查找，在结果集中找到仅大于当前值的（所有大于当前值的结果中的最小值），用当前值的索引将其替换掉 // 递增序列 采用二分查找 是最快的 start = 0 end = result.length - 1 while (start < end) { // start === end的时候就停止了 .. 这个二分查找在找索引 middle = ((start + end) / 2) | 0 // 向下取整 // 1 2 3 4 middle 6 7 8 9 6 if (arrI > arr[result[middle]]) { start = middle + 1 } else { end = middle } } // 找到中间值后，我们需要做替换操作 start / end if (arrI < arr[result[end]]) { // 这里用当前这一项 替换掉以有的比当前大的那一项。 更有潜力的我需要他 result[end] = i // p[i] = result[end - 1] // 记住他的前一个人是谁 } } } return result } const result = getSequence([3, 2, 8, 9, 5, 6, 7, 11, 15]) console.log(result) // [1, 4, 5, 6, 7, 8] （结果是最长递增子序列的索引） // 3 // 2（2替换3） // 2, 8 // 2, 8, 9 // 2, 5, 9（5替换掉8，二分查找，找到第一个比5大的进行替换，即所有大于当前值的结果中的最小值） // 2, 5, 6（6替换掉9，二分查找，找到第一个比6大的进行替换） // ... // 2, 5, 6, 7, 11, 15（最长递增子序列） 如果 newIndexToOldIndexMap 数组为 [102, 103, 101, 105, 106, 108, 107, 109, 104]
const result = getSequence([102, 103, 101, 105, 106, 108, 107, 109, 104]) console.log(result) // [2, 1, 8, 4, 6, 7]（结果是最长递增子序列的索引） // 102 // 102, 103 // 101, 103（102替换掉101，二分查找，找到第一个比101大的进行替换） // 101, 103, 105 // 101, 103, 105, 106 // 101, 103, 105, 106, 108 // 101, 103, 105, 106, 107（107替换掉108，二分查找，找到第一个比107大的进行替换） // 101, 103, 105, 106, 107, 109 // 101, 103, 104, 106, 107, 109（104替换掉105，二分查找，找到第一个比104大的进行替换） 得到的最长递增子序列为 101, 103, 104, 106, 107, 109，我们发现其在原始数组中并不是正确的顺序，虽然序列不对，但序列长度是没问题的。
下一章我们就以此为栗子，用 前驱节点追溯 纠正其错误的 101 和 104 节点
前驱节点追溯
再次提醒！最长递增子序列是 [101, 103, 104, 106, 107, 109]， 最长递增子序列的索引是[2, 1, 8, 4, 6, 7]，我们的 result 是最长递增子序列的索引 ！！！
我们发现，只要把 101 替换为 102， 104 替换为 105 ，则序列就被纠正了，思路如下
-
创建一个 回溯列表 p
**[0, 0, 0, 0, 0, 0, 0, 0, 0]**，初始值均为0，长度和数组一样长，即传入getSequence 的数组 -
记录每个节点的前驱节点。无论是 追加到序列末尾 还是 替换序列中的某一项，都要记录一下他前面的节点，最终生成一个回溯列表 p
[0, 0, 0, 1, 3, 4, 4, 6, 1] -
然后通过 序列的最后一项 109 对应的索引 7 往前回溯，p[7] 是 6，p[6] 是 4，p[4] 是 3 ......，最终得到
7 -> 6 -> 4 -> 3 -> 1 -> 0。 -
因为是从后往前追溯的，result 则被纠正为
[0, 1, 3, 4, 6, 7]，替换掉了顺序错误的节点
文字表达起来可能有点绕，可以看下这张图辅助理解
export function getSequence(arr) { const len = arr.length const result = [0] // 默认以数组中第0个为基准来做序列，注意！！存放的是数组 索引 let resultLastIndex // 结果集中最后的索引 let start let end let middle const p = new Array(len).fill(0) // 最后要标记索引 放的东西不用关心，但是要和数组一样长 for (let i = 0; i < len; i++) { let arrI = arr[i] /** 当前这一项比我们最后一项大则直接放到末尾 */ if (arrI !== 0) { // 因为在vue newIndexToOldIndexMap 中，0代表需要创建新元素，无需进行位置移动操作 resultLastIndex = result[result.length - 1] if (arrI > arr[resultLastIndex]) { // 比较当前项和最后一项的值，如果大于最后一项，则将当前索引添加到结果集中 result.push(i) // 记录索引 p[i] = resultLastIndex // 当前放到末尾的要记录他前面的索引，用于追溯 continue } /**这里我们需要通过二分查找，在结果集中找到仅大于当前值的（所有大于当前值的结果中的最小值），用当前值的索引将其替换掉 */ // 递增序列 采用二分查找 是最快的 start = 0 end = result.length - 1 while (start < end) { // start === end的时候就停止了 .. 这个二分查找在找索引 middle = ((start + end) / 2) | 0 // 向下取整 // 1 2 3 4 middle 6 7 8 9 6 if (arrI > arr[result[middle]]) { start = middle + 1 } else { end = middle } } // 找到中间值后，我们需要做替换操作 start / end if (arrI < arr[result[end]]) { // 这里用当前这一项 替换掉以有的比当前大的那一项。 更有潜力的我需要他 result[end] = i p[i] = result[end - 1] // 记住他的前一个人是谁 } } } // 1) 默认追加记录前驱索引 p[i] = resultLastIndex // 2) 替换之后记录前驱索引 p[i] = result[end - 1] // 3) 记录每个人的前驱节点 // 通过最后一项进行回溯 let i = result.length let last = result[i - 1] // 找到最后一项 while (i > 0) { i-- // 倒叙追溯 result[i] = last // 最后一项是确定的 last = p[last] } return result } 优化Diff算法
我们求得是最长递增子序列的索引，若乱序节点的索引存在于最长递增子序列索引中，则跳过他，不移动。这样就最大限度减少了节点移动操作
利用最长递增子序列，优化Diff算法，代码如下
// 获取最长递增子序列索引 let increasingNewIndexSequence = getSequence(newIndexToOldIndexMap) let j = increasingNewIndexSequence.length - 1 // 需要移动位置 // 乱序节点需要移动位置，倒序遍历乱序节点 for (let i = toBePatched - 1; i >= 0; i--) { let index = i + s2 // i是乱序节点中的index，需要加上s2代表总节点中的index let current = c2[index] // 找到当前节点 let anchor = index + 1 < c2.length ? c2[index + 1].el : null if (newIndexToOldIndexMap[i] === 0) { // 创建新元素 patch(null, current, container, anchor) } else { if (i != increasingNewIndexSequence[j]) { // 不是0，说明已经执行过patch操作了 hostInsert(current.el, container, anchor) } else { // 跳过不需要移动的元素， 为了减少移动操作 需要这个最长递增子序列算法 j-- } } 
