Vue3渲染器之快速Diff算法

简介: Vue3渲染器之快速Diff算法

Vue3中使用的就是快速Diff算法性能优于Vue2所采用的双端 Diff算法
可能其他的文章会让你先看一道算法题,即力扣第300题最长递增子序列,对于没有算法基础的同学理解会有困难.
里面涉及到动态规划,二分查找,Vue源码中采用的是二分查找.区别就是二分复杂度是nlogn,动态规划是n的平方,笔者写这篇文章的时候也只是弄懂了动态规划.
所以如果实在看不懂可以先跳过,毕竟并不是快速Diff第一步就需要它.

快速 Diff 算法第一步是预处理

image.png
其实很简单就是比较首和尾是否相同.上面就是前置节点1,后置节点2,3相同

对于相同的前置节点和后置节点,由于它们在新旧两组子节点中的相对位置不变,所以我们无须移动它们,但仍然需要在它们之间打补丁。

  1. 遍历前置节点,新旧节点只需要从同一位置开始比较,所以只需要设置一个索引j的值为 0.进入while循环,判断key是否相同.退出循环,j变成1
  2. 遍历后置节点,新旧节点因为长度可能不同,需要声明两个索引newEnd,oldEnd,指向新旧数组最后一个元素
    进入while循环,判断key是否相同.退出循环,此时newEnd变成1,oldEnd变成0.这些指的都是数组下标.

由这几个下标可知:

  1. oldEnd < j 成立:说明在预处理过程中,所有旧子节点都处理完毕了
  2. newEnd >= j 成立:说明在预处理过后,在新的一组子节点中,仍然有未被处理的节点,而这些遗留的节点将被视作新增节点
  3. 当这两个条件都满足,表示旧节点数组不用处理,新节点数组中需要添加节点,添加范围就是j和newEnd之间的元素.
  4. 找到一个挂载点进行挂载,即是新数组中下标为newEnd+1的元素.然后循环将j和newEnd之间的元素进行挂载
// 预处理完毕后,如果满足如下条件,则说明从 j --> newEnd 之间的节点应作为新节点插入
if (j > oldEnd && j <= newEnd) {
   
   
  // 锚点的索引
  const anchorIndex = newEnd + 1
  // 锚点元素
  const anchor =
    anchorIndex < newChildren.length ? newChildren[anchorIndex].el : null
  // 采用 while 循环,调用 patch 函数逐个挂载新增节点
  while (j <= newEnd) {
   
   
    patch(null, newChildren[j++], container, anchor)
  }
}

接下来看另一种情况,就是要将旧节点元素删除

image.png

这里很类似,就不再赘述

else if (j > newEnd && j <= oldEnd) {
   
   
     // j -> oldEnd 之间的节点应该被卸载
     while (j <= oldEnd) {
   
   
     unmount(oldChildren[j++])
     }
     }

上面给出的例子比较理想化,当处理完相同的前置节点或后置节点后,新旧两组子节点中总会有一组子节点全部被处理完毕。在这种情况下,只需要简单地挂载、卸载节点即可

对于所有的Diff算法都遵循两个规则

  1. 判断是否有节点需要移动,以及应该如何移动
  2. 找出那些需要被添加或移除的节点。

对于非理想的情况下,当相同的前置节点和后置节点被处理完毕后,索引 j、newEnd 和 oldEnd都不满足上面两个条件,所以需要增加新的 else 分支

现在我们的代码逻辑是

先进行预处理,预处理之后获取下标j newEnd oldEnd,根据他们的关系进入不同的条件分支 一种情况是新节点全部被处理,另一种是旧节点全部被处理,非理想情况下新旧都没有处理完当成最后一种情况

下面这种情况 多了一个节点7,少了一个节点6,预处理之后新旧数组都没处理完。

   children: [
                {
   
    type: 'p', children: '1', key: 1 },
                {
   
    type: 'p', children: '2', key: 2 },
                {
   
    type: 'p', children: '3', key: 3 },
                {
   
    type: 'p', children: '4', key: 4 },
                {
   
    type: 'p', children: '6', key: 6 },
                {
   
    type: 'p', children: '5', key: 5 },
            ]
  vnode.children =
            [
                {
   
    type: 'p', children: '1', key: 1 },
                {
   
    type: 'p', children: '3', key: 3 },
                {
   
    type: 'p', children: '4', key: 4 },
                {
   
    type: 'p', children: '2', key: 2 },
                {
   
    type: 'p', children: '7', key: 7 },
                {
   
    type: 'p', children: '5', key: 5 },
            ]
  1. 我们需要构造一个数组source,它的长度等于新的一组子节点在经过预处理之后剩余未处理节点的数量,并且 source 中每个元素的初始值都是 -1
    const count = newEnd - j + 1
    const source = new Array(count)
    source.fill(-1)
    
  2. source 数组将用来存储新的一组子节点中的节点在旧的一组子节点中的位置索引也就是[2, 3, 1, -1]
  3. 可以使用双重for循环,如果查找到新旧数组元素key相同,则将旧数组的索引赋给source的对应下标,但是复杂度有点高。所以可以新建一个索引表,即新数组的key,对应新数组的下标。
  4. 第一个 for 循环用来构建索引表,索引表存储的是节点的 key 值与节点在新 的一组子节点中位置索引之间的映射,第二个 for 循环用来遍历旧的 一组子节点。可以看到,我们拿旧子节点的 key 值去索引表 keyIndex 中查找该节点在新的一组子节点中的位置,并将查找结果存储到变量 u 中。如果 u 存在,说明该节点是可复用的,所以我们调用 patch 函数进行打补丁,并填充 source 数组;否则说明该节点已经不存在于新的一组子节点中了,这时我们需要调用 unmount 函数卸载它。
                            // 构建索引表
                            const keyIndex = {
   
   }
                            for (; newStart <= newEnd; newStart++) {
   
   
                                keyIndex[newChildren[newStart].key] = newStart
                            }
                            for (; oldStart <= oldEnd; oldStart++) {
   
   
                                oldVNode = oldChildren[oldStart]
                                let u = keyIndex[oldVNode.key]
                                if (u) {
   
   
                                    newVNode = newChildren[u]
                                    // 调用 patch 函数完成更新
                                    patch(oldVNode, newVNode, container)
                                    source[u - j] = oldStart
                                }
                                else {
   
   
                                    //not found
                                    unmount(oldVNode)
                                }
                            }
  1. 此时我们只需要专注于source.由于在处理source时,旧节点数组需要被卸载的已经卸载了,source中的-1代表新元素需要挂载。那么我们现在要考虑的是哪些元素需要移动,这与之前讲的简单diff有些相似,如果一个新元素在旧节点数组的索引小于上一个元素在旧节点数组的索引,那么他就需要移动。
  2. 换言之,我们只需要找到一条最长的递增子序列就能保证大多数节点不需要移动,(最长递增子序列可能有多种情况但只需要任意一种即可),上面的例子获得的子序列索引数组就是[0,1]代表key为2,3节点。也就是不需要移动
  3. 接下来就只需要处理剩下的source元素,如果等于-1代表新增节点。具体处理如下,大功告成
for (let i = source.length - 1; i >= 0; i--) {
   
   
    if (source[i] === -1) {
   
   
        const pos = i + j 
        const newVNode = newChildren[pos] 
        let anchor = newChildren[pos + 1] ? newChildren[pos + 1].el: null patch(null, newVNode, container, anchor)
    }
    if (getSequence(source).filter(item = >item !== i)) {
   
   
        const pos = i + j 
        const newVNode = newChildren[pos] 
        let anchor = newChildren[pos + 1] ? newChildren[pos + 1].el: null insert(newVNode.el, container, anchor)
    }
}

这是我自己写的返回最长递增子序列索引数组函数,仅供参考哦

var lengthOfLIS = function (nums) {
   
   
  let dp = [];
  let arr = [[0]];
  dp.length = nums.length;
  dp.fill(1);
  for (let i = 1; i < nums.length; i++) {
   
   
    let flag = false;
    for (let j = 0; j < i; j++) {
   
   
      if (nums[i] > nums[j]) {
   
   
        flag = true;
        if (dp[i] < dp[j] + 1) {
   
   
          arr[i] = [...arr[j], i];
        }
        dp[i] = Math.max(dp[i], dp[j] + 1);
      } else if (!flag) {
   
   
        arr[i] = [i];
      }
    }
  }
  console.log(arr);
  let length = 0;
  let index = 0;
  for (let i = 0; i < arr.length; i++) {
   
   
    if (arr[i].length > length) {
   
   
      index = i;
      length = arr[i].length;
    }
  }
};
lengthOfLIS([1, 2, 3, 4, 1]);
相关文章
|
1月前
|
敏捷开发 人工智能 JavaScript
Figma-Low-Code:快速将Figma设计转换为Vue.js应用,支持低代码渲染、数据绑定
Figma-Low-Code 是一个开源项目,能够直接将 Figma 设计转换为 Vue.js 应用程序,减少设计师与开发者之间的交接时间,支持低代码渲染和数据绑定。
87 3
Figma-Low-Code:快速将Figma设计转换为Vue.js应用,支持低代码渲染、数据绑定
|
3月前
|
监控 JavaScript 前端开发
Vue 异步渲染
【10月更文挑战第23天】Vue 异步渲染是提高应用性能和用户体验的重要手段。通过理解异步渲染的原理和优化策略,我们可以更好地利用 Vue 的优势,开发出高效、流畅的前端应用。同时,在实际开发中,要注意数据一致性、性能监控和调试等问题,确保应用的稳定性和可靠性。
|
4月前
|
算法 JavaScript UED
Diff 算法的实现原理
【10月更文挑战第18天】Diff 算法是 Vue.js 中实现高效 DOM 更新的核心机制,通过合理的比较和优化策略,能够在保证界面正确性的同时,最大程度地减少 DOM 操作,提高应用的性能和用户体验。
65 2
|
4月前
|
算法 JavaScript
Vue 中的 Diff 算法
【10月更文挑战第18天】需要注意的是,Diff 算法虽然能够提高性能,但在某些复杂的场景下,可能仍然会存在一些性能瓶颈。因此,在实际开发中,我们需要根据具体情况合理地使用 Diff 算法,并结合其他优化手段来提高应用的性能。
30 1
|
4月前
|
JavaScript 算法 前端开发
vue 中diff算法
【10月更文挑战第10天】
54 1
|
21天前
|
算法 数据安全/隐私保护 计算机视觉
基于Retinex算法的图像去雾matlab仿真
本项目展示了基于Retinex算法的图像去雾技术。完整程序运行效果无水印,使用Matlab2022a开发。核心代码包含详细中文注释和操作步骤视频。Retinex理论由Edwin Land提出,旨在分离图像的光照和反射分量,增强图像对比度、颜色和细节,尤其在雾天条件下表现优异,有效解决图像去雾问题。
|
21天前
|
算法 数据可视化 安全
基于DWA优化算法的机器人路径规划matlab仿真
本项目基于DWA优化算法实现机器人路径规划的MATLAB仿真,适用于动态环境下的自主导航。使用MATLAB2022A版本运行,展示路径规划和预测结果。核心代码通过散点图和轨迹图可视化路径点及预测路径。DWA算法通过定义速度空间、采样候选动作并评估其优劣(目标方向性、障碍物距离、速度一致性),实时调整机器人运动参数,确保安全避障并接近目标。
116 68
|
1月前
|
算法 数据安全/隐私保护
室内障碍物射线追踪算法matlab模拟仿真
### 简介 本项目展示了室内障碍物射线追踪算法在无线通信中的应用。通过Matlab 2022a实现,包含完整程序运行效果(无水印),支持增加发射点和室内墙壁设置。核心代码配有详细中文注释及操作视频。该算法基于几何光学原理,模拟信号在复杂室内环境中的传播路径与强度,涵盖场景建模、射线发射、传播及接收点场强计算等步骤,为无线网络规划提供重要依据。
|
1月前
|
机器学习/深度学习 数据采集 算法
基于GA遗传优化的CNN-GRU-SAM网络时间序列回归预测算法matlab仿真
本项目基于MATLAB2022a实现时间序列预测,采用CNN-GRU-SAM网络结构。卷积层提取局部特征,GRU层处理长期依赖,自注意力机制捕捉全局特征。完整代码含中文注释和操作视频,运行效果无水印展示。算法通过数据归一化、种群初始化、适应度计算、个体更新等步骤优化网络参数,最终输出预测结果。适用于金融市场、气象预报等领域。
基于GA遗传优化的CNN-GRU-SAM网络时间序列回归预测算法matlab仿真
|
1月前
|
算法
基于龙格库塔算法的锅炉单相受热管建模与matlab数值仿真
本设计基于龙格库塔算法对锅炉单相受热管进行建模与MATLAB数值仿真,简化为喷水减温器和末级过热器组合,考虑均匀传热及静态烟气处理。使用MATLAB2022A版本运行,展示自编与内置四阶龙格库塔法的精度对比及误差分析。模型涉及热传递和流体动力学原理,适用于优化锅炉效率。