经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » JS/JS库/框架 » Vue.js » 查看文章
Vue3 Diff算法之最长递增子序列,学不会来砍我!
来源:cnblogs  作者:柏成  时间:2024/1/19 9:48:39  对本文有异议

专栏分享: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] ,最终的最长递增子序列是什么?

  1. // [2, 8, 9, 11, 15] No!这一个不是最长递增子序列
  2. // [2, 5, 6, 7, 11, 15] 这一个才是最长的!

这个时候我们只需移动 9,8,3 三个节点即可,而不是全部节点!增子序列越长,所需要移动的节点次数就越少

我们可以利用 贪心算法 + 二分查找 获取原始的最长递增子序列,时间复杂度:O(NlogN)

  1. // 3
  2. // 2(2替换3)
  3. // 2, 8
  4. // 2, 8, 9
  5. // 2, 5, 9(5替换掉8,二分查找,找到第一个比5大的进行替换,即所有大于当前值的结果中的最小值)
  6. // 2, 5, 6(6替换掉9,二分查找,找到第一个比6大的进行替换)
  7. // ...
  8. // 2, 5, 6, 7, 11, 15(最长递增子序列)

由于贪心算法都是取当前局部最优解,有可能会导致最长递增子序列在原始数组中不是正确的顺序

例如数组:[3, 2, 8, 9, 5, 6, 7, 11, 15, 4],此算法求得结果如下。虽然序列不对,但序列长度是没问题的,在vue3 中我们会用 前驱节点追溯 来解决此问题

  1. // 2, 4, 6, 7, 11, 15(最长递增子序列)

让我们整理一下思路,用代码实现此算法

  1. 遍历数组,如果当前这一项比我们最后一项大则直接放到末尾

  2. 如果当前这一项比最后一项小,需要在序列中通过二分查找找到比当前大的这一项,用他来替换掉

  3. 前驱节点追溯,替换掉错误的节点

最优情况

  1. function getSequence(arr) {
  2. const len = arr.length
  3. const result = [0] // 默认以数组中第0个为基准来做序列,注意!!存放的是数组索引
  4. let resultLastIndex // 结果集中最后的索引
  5. for (let i = 0; i < len; i++) {
  6. let arrI = arr[i]
  7. // 因为在vue newIndexToOldIndexMap 中,0代表需要创建新元素,无需进行位置移动操作
  8. if (arrI !== 0) {
  9. resultLastIndex = result[result.length - 1]
  10. if (arrI > arr[resultLastIndex]) { // 比较当前项和最后一项的值,如果大于最后一项,则将当前索引添加到结果集中
  11. result.push(i) // 记录索引
  12. continue
  13. }
  14. }
  15. }
  16. return result
  17. }
  18. // 最长递增子序列:[10, 11, 12, 13, 14, 15, 16]
  19. // 最长递增子序列索引:[0, 1, 2, 3, 4, 5, 6]
  20. const result = getSequence([10, 11, 12, 13, 14, 15, 16, 0])
  21. console.log(result) // [0, 1, 2, 3, 4, 5, 6]

贪心+二分查找

  1. 遍历数组,如果当前这一项比我们最后一项大则直接放到末尾

  2. 如果当前这一项比最后一项小,需要在序列中通过二分查找找到比当前大的这一项,用他来替换掉

  1. function getSequence(arr) {
  2. const len = arr.length
  3. const result = [0] // 默认以数组中第0个为基准来做序列,注意!!存放的是数组 索引
  4. let resultLastIndex // 结果集中最后的索引
  5. let start
  6. let end
  7. let middle
  8. for (let i = 0; i < len; i++) {
  9. let arrI = arr[i]
  10. // 因为在vue newIndexToOldIndexMap 中,0代表需要创建新元素,无需进行位置移动操作
  11. if (arrI !== 0) {
  12. resultLastIndex = result[result.length - 1]
  13. if (arrI > arr[resultLastIndex]) {
  14. // 比较当前项和最后一项的值,如果大于最后一项,则将当前索引添加到结果集中
  15. result.push(i) // 记录索引
  16. continue
  17. }
  18. // 这里我们需要通过二分查找,在结果集中找到仅大于当前值的(所有大于当前值的结果中的最小值),用当前值的索引将其替换掉
  19. // 递增序列 采用二分查找 是最快的
  20. start = 0
  21. end = result.length - 1
  22. while (start < end) {
  23. // start === end的时候就停止了 .. 这个二分查找在找索引
  24. middle = ((start + end) / 2) | 0 // 向下取整
  25. // 1 2 3 4 middle 6 7 8 9 6
  26. if (arrI > arr[result[middle]]) {
  27. start = middle + 1
  28. } else {
  29. end = middle
  30. }
  31. }
  32. // 找到中间值后,我们需要做替换操作 start / end
  33. if (arrI < arr[result[end]]) {
  34. // 这里用当前这一项 替换掉以有的比当前大的那一项。 更有潜力的我需要他
  35. result[end] = i
  36. // p[i] = result[end - 1] // 记住他的前一个人是谁
  37. }
  38. }
  39. }
  40. return result
  41. }
  42. const result = getSequence([3, 2, 8, 9, 5, 6, 7, 11, 15])
  43. console.log(result) // [1, 4, 5, 6, 7, 8] (结果是最长递增子序列的索引)
  44. // 3
  45. // 2(2替换3)
  46. // 2, 8
  47. // 2, 8, 9
  48. // 2, 5, 9(5替换掉8,二分查找,找到第一个比5大的进行替换,即所有大于当前值的结果中的最小值)
  49. // 2, 5, 6(6替换掉9,二分查找,找到第一个比6大的进行替换)
  50. // ...
  51. // 2, 5, 6, 7, 11, 15(最长递增子序列)

如果 newIndexToOldIndexMap 数组为 [102, 103, 101, 105, 106, 108, 107, 109, 104]

  1. const result = getSequence([102, 103, 101, 105, 106, 108, 107, 109, 104])
  2. console.log(result) // [2, 1, 8, 4, 6, 7](结果是最长递增子序列的索引)
  3. // 102
  4. // 102, 103
  5. // 101, 103(102替换掉101,二分查找,找到第一个比101大的进行替换)
  6. // 101, 103, 105
  7. // 101, 103, 105, 106
  8. // 101, 103, 105, 106, 108
  9. // 101, 103, 105, 106, 107(107替换掉108,二分查找,找到第一个比107大的进行替换)
  10. // 101, 103, 105, 106, 107, 109
  11. // 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 ,则序列就被纠正了,思路如下

  1. 创建一个 回溯列表 p **[0, 0, 0, 0, 0, 0, 0, 0, 0]**,初始值均为0,长度和数组一样长,即传入getSequence 的数组

  2. 记录每个节点的前驱节点。无论是 追加到序列末尾 还是 替换序列中的某一项,都要记录一下他前面的节点,最终生成一个回溯列表 p [0, 0, 0, 1, 3, 4, 4, 6, 1]

  3. 然后通过 序列的最后一项 109 对应的索引 7 往前回溯,p[7] 是 6,p[6] 是 4,p[4] 是 3 ......,最终得到7 -> 6 -> 4 -> 3 -> 1 -> 0

  4. 因为是从后往前追溯的,result 则被纠正为 [0, 1, 3, 4, 6, 7],替换掉了顺序错误的节点

文字表达起来可能有点绕,可以看下这张图辅助理解

  1. export function getSequence(arr) {
  2. const len = arr.length
  3. const result = [0] // 默认以数组中第0个为基准来做序列,注意!!存放的是数组 索引
  4. let resultLastIndex // 结果集中最后的索引
  5. let start
  6. let end
  7. let middle
  8. const p = new Array(len).fill(0) // 最后要标记索引 放的东西不用关心,但是要和数组一样长
  9. for (let i = 0; i < len; i++) {
  10. let arrI = arr[i]
  11. /** 当前这一项比我们最后一项大则直接放到末尾 */
  12. if (arrI !== 0) {
  13. // 因为在vue newIndexToOldIndexMap 中,0代表需要创建新元素,无需进行位置移动操作
  14. resultLastIndex = result[result.length - 1]
  15. if (arrI > arr[resultLastIndex]) {
  16. // 比较当前项和最后一项的值,如果大于最后一项,则将当前索引添加到结果集中
  17. result.push(i) // 记录索引
  18. p[i] = resultLastIndex // 当前放到末尾的要记录他前面的索引,用于追溯
  19. continue
  20. }
  21. /**这里我们需要通过二分查找,在结果集中找到仅大于当前值的(所有大于当前值的结果中的最小值),用当前值的索引将其替换掉 */
  22. // 递增序列 采用二分查找 是最快的
  23. start = 0
  24. end = result.length - 1
  25. while (start < end) {
  26. // start === end的时候就停止了 .. 这个二分查找在找索引
  27. middle = ((start + end) / 2) | 0 // 向下取整
  28. // 1 2 3 4 middle 6 7 8 9 6
  29. if (arrI > arr[result[middle]]) {
  30. start = middle + 1
  31. } else {
  32. end = middle
  33. }
  34. }
  35. // 找到中间值后,我们需要做替换操作 start / end
  36. if (arrI < arr[result[end]]) {
  37. // 这里用当前这一项 替换掉以有的比当前大的那一项。 更有潜力的我需要他
  38. result[end] = i
  39. p[i] = result[end - 1] // 记住他的前一个人是谁
  40. }
  41. }
  42. }
  43. // 1) 默认追加记录前驱索引 p[i] = resultLastIndex
  44. // 2) 替换之后记录前驱索引 p[i] = result[end - 1]
  45. // 3) 记录每个人的前驱节点
  46. // 通过最后一项进行回溯
  47. let i = result.length
  48. let last = result[i - 1] // 找到最后一项
  49. while (i > 0) {
  50. i--
  51. // 倒叙追溯
  52. result[i] = last // 最后一项是确定的
  53. last = p[last]
  54. }
  55. return result
  56. }

优化Diff算法

我们求得是最长递增子序列的索引,若乱序节点的索引存在于最长递增子序列索引中,则跳过他,不移动。这样就最大限度减少了节点移动操作

利用最长递增子序列,优化Diff算法,代码如下

  1. // 获取最长递增子序列索引
  2. let increasingNewIndexSequence = getSequence(newIndexToOldIndexMap)
  3. let j = increasingNewIndexSequence.length - 1
  4. // 需要移动位置
  5. // 乱序节点需要移动位置,倒序遍历乱序节点
  6. for (let i = toBePatched - 1; i >= 0; i--) {
  7. let index = i + s2 // i是乱序节点中的index,需要加上s2代表总节点中的index
  8. let current = c2[index] // 找到当前节点
  9. let anchor = index + 1 < c2.length ? c2[index + 1].el : null
  10. if (newIndexToOldIndexMap[i] === 0) {
  11. // 创建新元素
  12. patch(null, current, container, anchor)
  13. } else {
  14. if (i != increasingNewIndexSequence[j]) {
  15. // 不是0,说明已经执行过patch操作了
  16. hostInsert(current.el, container, anchor)
  17. } else {
  18. // 跳过不需要移动的元素, 为了减少移动操作 需要这个最长递增子序列算法
  19. j--
  20. }
  21. }

原文链接:https://www.cnblogs.com/burc/p/17964032

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号