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)
  }
}
AI 代码解读

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

image.png

这里很类似,就不再赘述

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

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

对于所有的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 },
            ]
AI 代码解读
  1. 我们需要构造一个数组source,它的长度等于新的一组子节点在经过预处理之后剩余未处理节点的数量,并且 source 中每个元素的初始值都是 -1
    const count = newEnd - j + 1
    const source = new Array(count)
    source.fill(-1)
    
    AI 代码解读
  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)
                                }
                            }
AI 代码解读
  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)
    }
}
AI 代码解读

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

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]);
AI 代码解读
相关文章
Vue 异步渲染
【10月更文挑战第23天】Vue 异步渲染是提高应用性能和用户体验的重要手段。通过理解异步渲染的原理和优化策略,我们可以更好地利用 Vue 的优势,开发出高效、流畅的前端应用。同时,在实际开发中,要注意数据一致性、性能监控和调试等问题,确保应用的稳定性和可靠性。
Diff 算法的实现原理
【10月更文挑战第18天】Diff 算法是 Vue.js 中实现高效 DOM 更新的核心机制,通过合理的比较和优化策略,能够在保证界面正确性的同时,最大程度地减少 DOM 操作,提高应用的性能和用户体验。
34 2
|
2月前
|
Vue 中的 Diff 算法
【10月更文挑战第18天】需要注意的是,Diff 算法虽然能够提高性能,但在某些复杂的场景下,可能仍然会存在一些性能瓶颈。因此,在实际开发中,我们需要根据具体情况合理地使用 Diff 算法,并结合其他优化手段来提高应用的性能。
17 1
vue 中diff算法
【10月更文挑战第10天】
34 1
基于WOA算法的SVDD参数寻优matlab仿真
该程序利用鲸鱼优化算法(WOA)对支持向量数据描述(SVDD)模型的参数进行优化,以提高数据分类的准确性。通过MATLAB2022A实现,展示了不同信噪比(SNR)下模型的分类误差。WOA通过模拟鲸鱼捕食行为,动态调整SVDD参数,如惩罚因子C和核函数参数γ,以寻找最优参数组合,增强模型的鲁棒性和泛化能力。
基于WOA-SVM的乳腺癌数据分类识别算法matlab仿真,对比BP神经网络和SVM
本项目利用鲸鱼优化算法(WOA)优化支持向量机(SVM)参数,针对乳腺癌早期诊断问题,通过MATLAB 2022a实现。核心代码包括参数初始化、目标函数计算、位置更新等步骤,并附有详细中文注释及操作视频。实验结果显示,WOA-SVM在提高分类精度和泛化能力方面表现出色,为乳腺癌的早期诊断提供了有效的技术支持。
基于HMM隐马尔可夫模型的金融数据预测算法matlab仿真
本项目基于HMM模型实现金融数据预测,包括模型训练与预测两部分。在MATLAB2022A上运行,通过计算状态转移和观测概率预测未来值,并绘制了预测值、真实值及预测误差的对比图。HMM模型适用于金融市场的时间序列分析,能够有效捕捉隐藏状态及其转换规律,为金融预测提供有力工具。
基于GoogleNet深度学习网络的手语识别算法matlab仿真
本项目展示了基于GoogleNet的深度学习手语识别算法,使用Matlab2022a实现。通过卷积神经网络(CNN)识别手语手势,如&quot;How are you&quot;、&quot;I am fine&quot;、&quot;I love you&quot;等。核心在于Inception模块,通过多尺度处理和1x1卷积减少计算量,提高效率。项目附带完整代码及操作视频。
|
10天前
|
基于GA遗传算法的PID控制器参数优化matlab建模与仿真
本项目基于遗传算法(GA)优化PID控制器参数,通过空间状态方程构建控制对象,自定义GA的选择、交叉、变异过程,以提高PID控制性能。与使用通用GA工具箱相比,此方法更灵活、针对性强。MATLAB2022A环境下测试,展示了GA优化前后PID控制效果的显著差异。核心代码实现了遗传算法的迭代优化过程,最终通过适应度函数评估并选择了最优PID参数,显著提升了系统响应速度和稳定性。
AI助理

阿里云 AI 助理已上线!

快来体验一下吧。