vue3的快速diff之最长递增子序列 |
您所在的位置：网站首页 › 什么叫递增 › vue3的快速diff之最长递增子序列 |
vue3的快速diff之最长递增子序列
|
前言
大家好，之前看了《Vue.JS设计与实现》这本书，对于vue3的快速diff算法有用到最长递增子序列有点迷糊，今天来了解一下吧，leetcode300题 最长递增子序列，它主要用到了贪心+二分法查找（优化过）求值，最后移动最少的dom来更新视图的目的。 最长递增子序列给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 例如，[0,1,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 我们知道官方的解法有两种：动态规划、贪心+二分查找 动态规划思路：如果要求数组[2，5，3，7]的最长递增子序列，我们可以换一个思路，假设为一个行程问题，比如说从数组索引3到索引0，比作从D(7)、C(3)、B(5)、A(2)的行程规划，要求只能从大的数到小的数，走的步数越多越好；比如C不能直达到B，因为C比B小； 所以我们要算出D到A的最多步数，可以先算出C到A的最多步数，再算出D到他们的步数，D和A、B、C每一项进行比较，D大于它就在之前的基础上+1，算出D分别到A、B、C的步数，取最大值。 依次类推：先算出A到B的最多步数，再算出C到A、B的最多步数，再算出D到A、B、C的最多步数，算出每一项的最多步数，最后取里面的最大值。为什么取最大值，因为和行程问题不同，它们最后结果的起点和终点可以不是A和D。 实现： 首先创建一个dp数组，长度和传入的nums数组一样，值都为1，记录每一项最长递增子序列的值。 首先从数组i=1开始，比较该项nums[1]和前面项nums[0]，若大于该值则取出dp[j]+1 若i=n,循环比较i前面的所有项，满足j5;7>3,所以要找出最大值 dp[3] = Math.max(dp[3], dp[j]+1) /** * @param {number[]} nums * @return {number} */ var lengthOfLIS = function(nums) { let dp = new Array(nums.length).fill(1); for(let i = 1;i < nums.length; i++) { for(let j = 0; j < i; j++) { if(nums[i] > nums[j]) { dp[i] = Math.max(dp[i], dp[j]+1) } } } return Math.max(...dp) }; 贪心+二分查找这个不看答案真的很难想到，用一个tail数组来存放结果 首先将nums第一项存入数组，循环数组，nums[i]>tail[tail.length - 1]就将该值push到数组里面（这样就是会使最长递增子序列的长度增加） 否则，使用二分法在tail数组中找到和nums[i]值接近的数，替换tail的这一项 最后tail的长度就是最长递增子序列的值 var lengthOfLIS = function (nums) { let n = nums.length; if (n tail[tail.length - 1]) { //当nums中的元素比tail中的最后一个大时 可以放心push进tail tail.push(nums[i]); } else { // 二分法查找和nums[i]值接近的数 let left = 0; let right = tail.length - 1; while (left < right) { let mid = (left + right) >> 1; if (tail[mid] < nums[i]) { left = mid + 1; } else { right = mid; } } // 替换该值 tail[left] = nums[i]; } } return tail.length; }; vue3diff的最长子序列vue3采用的贪心+二分法，复杂度更低。 arr数组的值，表示在旧的childVnode对应的位置顺序。 对于let arr = [1, 5, 6, 7, 8, 2, 3, 4, 9]; 贪心+二分法 的历程是： 1 1,5 1,5,6 1,5,6,7 1,5,6,7,8 1,2,6,7,8 1,2,3,7,8 1,2,3,4,8 1,2,3,4,8,9 我们发现[1,2,3,4,8,9]确实不是正确的结果，但长度是正确的；[1,5,6,7,8,9]才是正确的结果， vue3的diff需要的，我们最后需要一个修正过程，这个时候需要一个p数组，p[i]记录的是，当前操作的result[start]的前一项 贪心+二分法 加入p数组： 括号里式对应的索引 1(0) 1(0),5(1) 新增 p=[undefined, 0] 1(0),5(1),6(2) 新增 p=[undefined, 0, 1] 1(0),5(1),6(2),7(3) 新增 p=[undefined, 0, 1, 2] 1(0),5(1),6(2),7(3),8(4) 新增 p=[undefined, 0, 1, 2, 3] 1(0),2(5),6(2),7(3),8(4) 替换 p=[undefined, 0, 1, 2, 3, 0] 1(0),2(5),3(6),7(3),8(4) 替换 p=[undefined, 0, 1, 2, 3, 0, 5] 1(0),2(5),3(6),4(7),8(4) 替换 p=[undefined, 0, 1, 2, 3, 0, 5, 6] 1(0),2(5),3(6),4(7),8(4),9(8) 新增 p=[undefined, 0, 1, 2, 3, 0, 5, 6, 4] 我们知道[0,5,6,7,4,8]索引， 对应的结果[1,2,3,4,8,9]不对 所以根据p记录的替换前的值，重建数组 最后一位是9(8)是不会算错了，我们知道最大一项对应的索引是8，所以p[8]获取的值是4，4就是它前一项的索引值；再根据p[4]获取的值是3，做为前一项的值，依次类推重建result result[5]= 8 end: p[8] === 4 result[4] = 4 end: p[4] === 3 result[3] = 3 end: p[3] === 3 result[2] = 2 end: p[2] === 2 result[1] = 1 end: p[1] === 1 result[0] = 0 end: p[0] === 0 对应的正确的索引是 [0,1,2,3,4,8] 结果[1,5,6,7,8,9] function getSequence(arr) { const p = [] const result = [0] // 存储最长增长子序列的索引数组 let i, j, start, end, mid const len = arr.length for (i = 0; i < len; i++) { const arrI = arr[i] if (arrI !== 0) { j = result[result.length - 1] if (arr[j] < arrI) { // 如果arr[i] > arr[j], 当前值比最后一项还大，可以直接push到索引数组(result)中去 p[i] = j // p记录的当前位置下，前一项的索引值 result.push(i) continue } // 二分法查找和arrI值接近的数 start = 0 end = result.length - 1 while (start < end) { mid = ((start + end) / 2) | 0 if (arr[result[mid]] < arrI) { start = mid + 1 } else { end = mid } } if (arrI < arr[result[start]]) { if (start > 0) { p[i] = result[start - 1] // 记录当前位置下，替换位置的前一项的索引值 } // 替换该值 result[start] = i } } } // 通过数组p，修正最长递增子序列对应的值 start = result.length end = result[start - 1] while (start-- > 0) { result[start] = end end = p[end]; } return result } 最后这次主要了解了一下，最长递增子序列算法题的动态规划解法和贪心和二分法解法，vue3的快速diff阶段，应用了贪心和二分法（通过优化操作保证每次子序列的顺序正确）计算最长递增子序列，因为传入的是oldChildren对应的索引，如果索引是递增的，说明dom的排列顺序不用变化；所以计算得到的递增子序列的dom是不需要再进行移动操作，做到最少的dom操作。 看到这里，如果这篇文章对你有帮助的话，欢迎大家点赞~ |
【本文地址】
今日新闻 |
推荐新闻 |