快活林资源网

详解Vue2的diff算法
网络编程 2024/12/22 佚名
3 1
快活林资源网 Design By www.csstdc.com

前言

双端比较算法是vue2.x采用的diff算法，本篇文章只是对双端比较算法粗略的过程进行了一下分析，具体细节还是得Vue源码，Vue的源码在这

过程

假设当前有两个数组arr1和arr2

let arr1 = [1,2,3,4,5]
let arr2 = [4,3,5,1,2]

那么其过程有五步

  1.  arr1[0] 和 arr2[0]比较
  2.  arr1[ arr1.length-1 ] 和 arr2[ arr2.length-1 ] 比较
  3.  arr1[0] 和 arr2[ arr2.length-1 ] 比较
  4.  arr1[ arr1.length-1 ] 和 arr2[0] 比较
  5.  arr2[0] 和 arr1的每个元素进行比较

每次比较都是从数组的两端开始比较，如果是首位比较相等，那么比较的开头索引+1

如果是在末尾比较成功，那么比较的结束索引-1，当开头索引大于结束索引时说明比较已经结束

拆解过程

let arr1 = [1,2,3,4,5]
let arr2 = [4,3,5,1,2]

let oldStartIdx = 0 
let oldEndIdx = arr1.lenght -1
let newStartIdx = 0
let newEndIdx = arr2.length -1

let oldStartVNode = arr1[oldStartIdx]   
let oldEndVNode = arr1[oldEndIdx]  
let newStartVNode = arr2[newStartIdx]  
let newEndVNode = arr2[newEndIdx]

第一轮：
 1. 1和4比较不相等
 2. 5和2比较不相等
 3. 1和2比较不相等
 4. 5和4比较不相等
 5. 4和旧数组逐一比较，和索引为3的值相等，说明4由索引3变换位置为了0， newStartIdx++
 //比较完后,使用u_1表示比较成功的元素
 [1,2,3,u_1,5] //arr1
 [u_1,3,5,1,2] //arr2

第二轮：
 1. 1和3比较不相等
 2. 5和2比较不相等
 3. 1和2比较不相等
 4. 5和3比较不相等
 5. 3和旧数组逐一比较，和索引为2的值相等，3由索引2变换位置为了0， newStartIdx++
 //比较成功后,使用u_2表示比较成功的元素
 [1,2,u_2,u_1,5] //arr1
 [u_1,u_2,5,1,2] //arr2

第三轮： 
 1. 1和5比较不相等 
 2. 5和2比较不相等 
 3. 1和2比较不相等 
 4. 5和5比较相等,5已经从旧数组oldEndIdx位置移动到了newStartIdx位置,newStartIdx++, oldEndIdx-- 
 5. 第四步比较成功，进入下一轮 
 //比较成功后,使用u_3表示比较成功的元素 
 [1,2,u_2,u_1,u_3] //arr1 
 [u_1,u_2,u_3,1,2] //arr2

第四轮： 
 1. 1和1比较相等,1已经从旧数组oldStartIdx位置移动到newStartIdx位置,oldStartIdx++,newStartIdx++ 
 2. 第一步比较成功，进入下一轮 3. 第一步比较成功，进入下一轮 
 4. 第一步比较成功，进入下一轮 5. 第一步比较成功，进入下一轮 
 //比较成功后,使用u_4表示比较成功的元素 
 [u_4,2,u_2,u_1,u_3] //arr1 
 [u_1,u_2,u_3,u_4,2] //arr2


第五轮： 
 1. 2和2比较相等,1已经从旧数组oldStartIdx位置移动到newStartIdx位置,oldStartIdx++,newStartIdx++ 
 2. 第一步比较成功，进入下一轮 
 3. 第一步比较成功，进入下一轮 
 4. 第一步比较成功，进入下一轮 
 5. 第一步比较成功，进入下一轮 
 //比较成功后,使用u_5表示比较成功的元素 
 [u_4,u_5,u_2,u_1,u_3] //arr1 
 [u_1,u_2,u_3,u_4,u_5] //arr2

用一个gif图来表示

详解Vue2的diff算法

上代码

function diff(prevChildren, nextChildren) {  
 let oldStartIdx = 0 //旧数组起始索引  
 let oldEndIdx = prevChildren.length - 1 //旧数组结束索引  
 let newStartIdx = 0 //新数组其实索引  
 let newEndIdx = nextChildren.length - 1 //新数组结束索引  
 
 let oldStartVNode = prevChildren[oldStartIdx]   
 let oldEndVNode = prevChildren[oldEndIdx]  
 let newStartVNode = nextChildren[newStartIdx]  
 let newEndVNode = nextChildren[newEndIdx]  
 while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {   
  if (!oldStartVNode) { 
  //undefined 时前移一位    
  oldStartVNode = prevChildren[++oldStartIdx]   
 } else if (!oldEndVNode) { 
  //undefined 时后移一位    
  oldEndVNode = prevChildren[--oldEndIdx]   
 } else if (oldStartVNode.key === newStartVNode.key ) { //1.开始与开始    
  oldStartVNode = prevChildren[++oldStartIdx]    
  newStartVNode = nextChildren[++newStartIdx]   
 } else if ( oldEndVNode.key === newEndVNode.key ) { //2.结束与结束     
  oldEndVNode = prevChildren[--oldEndIdx]    
  newEndVNode = nextChildren[--newEndIdx]   
 } else if (oldStartVNode.key === newEndVNode.key ) { //3.开始与结束    
  oldStartVNode = prevChildren[++oldStartIdx]    
  newEndVNode = nextChildren[--newEndIdx]   
 } else if (oldEndVNode.key === newStartVNode.key ) { //4.结束与开始     
  oldEndVNode = prevChildren[--oldEndIdx]    
  newStartVNode = nextChildren[++newStartIdx]   
 } else {
  //5.新数组开头元素和旧数组每一个元素对比    
  const idxInOld = prevChildren.findIndex((node) => {     
   if (node && node.key === newStartVNode.key) {      
   return true     
   }     
  })    
  if (idxInOld >= 0) {     
   prevChildren[idxInOld] = undefined    
  } else {     
   //newStartVNode是新元素    
  }    
  newStartVNode = nextChildren[++newStartIdx]   
 }  
 } 
}


diff([1,2,3,4,5],[4,3,5,1,2])

我们发现，上面的算法走完后，如果新旧两个数组只是顺序变化，那么它能完美的diff出差异，但是如果新数组有新增或者删除的时候就不行了，因此我们在while循环完成后需要找出新增或者删除的元素，那怎么知道哪些是新增哪些是删除的元素呢？

在比较的第五步，选取的新数组的第一个元素和旧数组的所有元素逐一对比，这里我们就可以得出了这个数组是否是新增，如果对比相等，那就是位置变换，否则当前元素就是新增的，但是，while循环的条件是oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx，如果是以下情况

let arr1 = [1,2,3,4,5]
let arr2 = [1,2,3,4,5,6,7]

因为循环条件的导致，这里会在5次while后就结束了，因此在数组末尾的6和7永远走不了第五步的插入条件，那如何判断6和7是新增的呢？我们来观察一下while循环结束后的索引

//例子1
let arr1 = [1,2,3,4,5]
let arr2 = [1,2,3,4,5,6,7]
//diff后它们的索引为
oldStartIdx = 5, oldEndIdx = 4
newStartIdx = 5, newEndIdx = 6

//例子2
let arr1 = [1,2,3,4,5]
let arr2 = [4,5,6,7,1,3,2]
//diff后它们的索引为
oldStartIdx = 3, oldEndIdx = 2
newStartIdx = 6, newEndIdx = 5

//例子3
let arr1 = [1,2,3,4,5]
let arr2 = [7,1,3,5,6,4,2]
//diff后它们的索引为
oldStartIdx = 5, oldEndIdx = 4
newStartIdx = 4, newEndIdx = 4

//例子4
let arr1 = [1,2,3,4,5]
let arr2 = [2,4,1,5,7,3,6]
//diff后它们的索引为
oldStartIdx = 3, oldEndIdx = 2
newStartIdx = 6, newEndIdx = 6

我们发现，新增元素的索引和newStartIdx还有newEndIdx是一一对应的

  • 例子1：newStartIdx小于newEndIdx，并且是5和6，而新增元素6对应在arr2的索引为6,新增元素7对应在arr2的索引为7，此时6和7都已经越界出arr1的长度范围
  • 例子2：newStartIdx是大于newEndIdx，没有对应关系
  • 例子3：newStartIdx等于newEndIdx，我们发现arr2索引为4的元素正是新增元素6，但是6次时没有越界出arr1的长度范围,它刚好在数组的最后一个元素
  • 例子4：newStartIdx等于newEndIdx，arr2中索引为6的值正是新增元素6

那么得出的结论就是，如果在while循环结束后，如果newStartIdx是小于或者等于newEndIdx，那么在newStartIdx和newEndIdx索引之间对应的元素就是新增的元素，并且oldStartIdx总是比oldEndIdx大

上面说完了新增，那如果是删除元素呢"htmlcode"> 

//例子1
let arr1 = [4,3,5,6,7,2,1]
let arr2 = [1,3,5,4,2]
//diff后它们的索引为
oldStartIdx = 3, oldEndIdx = 4
newStartIdx = 3, newStartIdx = 2

//例子2
let arr1 = [7,2,3,5,6,1,4]
let arr2 = [5,1,2,3,4]
//diff后它们的索引为
oldStartIdx = 0, oldEndIdx = 4
newStartIdx = 4, newStartIdx = 3

//例子3
let arr1 = [1,5,4,2,6,7,3]
let arr2 = [4,5,1,2,3]
//diff后它们的索引为
oldStartIdx = 4, oldEndIdx = 5
newStartIdx = 4, newStartIdx = 3

同理新增的观察套路，发现newStartIdx总是比newStartIdx大，并且需要删除的元素总是在oldStartIdx和oldEndIdx对应的索引之间，那么我们只需要把oldStartIdx和oldEndIdx的元素删除即可，那问题来了，像例子2 中oldStartIdx和oldEndIdx索引之间的元素有7,2,3,5,6其中真正需要删除的只有7和6，这样子不就误删了2,3,5么？关键的来了，我们看例子2的2,3,5发现它们走的都是双端比较算法的第五步，第五步写的代码是

 const idxInOld = prevChildren.findIndex((node) => {     
  if (node && node.key === newStartVNode.key) {      
   return true     
  }     
 })    
 if (idxInOld >= 0) {     
  prevChildren[idxInOld] = undefined    
 } else {     
 //newStartVNode是新元素    
 }    
 newStartVNode = nextChildren[++newStartIdx]

如果idxInOld>0说明在旧数组中找到了，那么我们将preChildren[idxInOld]设置为undefined，也就是说2,3,5经过diff算法后，它们在arr1中的值已经被替换为了undefined，这里也是就为什么在diff算法开始需要判断!oldStartVNode和!oldEndVnode的原因了,下面我们完善代码

function diff(prevChildren, nextChildren) { 
 let oldStartIdx = 0 //旧数组起始索引 
 let oldEndIdx = prevChildren.length - 1 //旧数组结束索引 
 let newStartIdx = 0 //新数组其实索引 
 let newEndIdx = nextChildren.length - 1 //新数组结束索引 

 let oldStartVNode = prevChildren[oldStartIdx]  
 let oldEndVNode = prevChildren[oldEndIdx] 
 let newStartVNode = nextChildren[newStartIdx] 
 let newEndVNode = nextChildren[newEndIdx] 
 while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {  
  if (!oldStartVNode) { //undefined 时前移一位   
   oldStartVNode = prevChildren[++oldStartIdx]  
  } else if (!oldEndVNode) { 
   //undefined 时后移一位   
   oldEndVNode = prevChildren[--oldEndIdx]  
  } else if (oldStartVNode.key === newStartVNode.key ) { //1.开始与开始   
   oldStartVNode = prevChildren[++oldStartIdx]   
   newStartVNode = nextChildren[++newStartIdx]  
  } else if ( oldEndVNode.key === newEndVNode.key ) { //2.结束与结束    
   oldEndVNode = prevChildren[--oldEndIdx]   
   newEndVNode = nextChildren[--newEndIdx]  
  } else if (oldStartVNode.key === newEndVNode.key ) { //3.开始与结束   
   oldStartVNode = prevChildren[++oldStartIdx]   
   newEndVNode = nextChildren[--newEndIdx]  
  } else if (oldEndVNode.key === newStartVNode.key ) { //4.结束与开始    
   oldEndVNode = prevChildren[--oldEndIdx]   
   newStartVNode = nextChildren[++newStartIdx]  
  } else {   
    //5.新数组开头元素和旧数组每一个元素对比   
   const idxInOld = prevChildren.findIndex((node) => {    
    if (node && node.key === newStartVNode.key) {     
     return true    
    }    
   })   
   if (idxInOld >= 0) {    
    prevChildren[idxInOld] = undefined   
   } else {    
    //newStartVNode是新元素   
   }   
   newStartVNode = nextChildren[++newStartIdx]  
  } 
 } 
 if (oldStartIdx > oldEndIdx) {    
 for (; newStartIdx <= newEndIdx; ++newStartIdx) {   
 //新增内容   
 let vnode = nextChildren[newStartIdx]   
 } 
 } else if (newStartIdx > newEndIdx) {  
  for (let i = oldStartIdx; i <= oldEndIdx; i++) {   /
   /删除内容  
 } 
 }
}

diff([1,2,3,4,5],[4,3,5,1,2])

接下来我们使用两个gif图来表示一下diff过程

1.新增元素

详解Vue2的diff算法

2.减少元素

详解Vue2的diff算法

以上就是详解Vue2的diff算法的详细内容，更多关于Vue2的diff算法的资料请关注其它相关文章！

快活林资源网 Design By www.csstdc.com
广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！
快活林资源网 Design By www.csstdc.com
www.csstdc.com 快活林资源网
120,135影音资源
344,641技术资源
22,817软件资源
435,032站长资源

《魔兽世界》大逃杀！60人新游玩模式《强袭风暴》3月21日上线

暴雪近日发布了《魔兽世界》10.2.6 更新内容，新游玩模式《强袭风暴》即将于3月21 日在亚服上线，届时玩家将前往阿拉希高地展开一场 60 人大逃杀对战。

艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕，并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时，他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中，玩家将会进入一个全新的海盗主题大逃杀式限时活动，其中包含极高的风险和史诗级的奖励。

《强袭风暴》不是普通的战场，作为一个独立于主游戏之外的活动，玩家可以用大逃杀的风格来体验《魔兽世界》，不分职业、不分装备（除了你在赛局中捡到的），光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式，玩家在加入海盗主题的预赛大厅区域前，可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹，《巨龙崛起》和《魔兽世界：巫妖王之怒 经典版》的玩家都可以获得奖励。

更新日志

友情链接

杰晶网络 DDR爱好者之家 桃源资源网 杰网资源 富贵资源网 南强小屋 铁雪资源网 幽灵资源网 万梅资源网 狼山资源网 白云岛资源网 昆仑资源网 相思资源网 明霞山资源网 内蒙古资源网 黑松山资源网 茶园资源网 饿虎岗资源网 大旗谷资源网 常春岛资源网 岱庙资源网 兴国资源网 快活林资源网 蝙蝠岛资源网 帝王谷资源网 白云城资源网 伏龙阁资源网 清风细雨楼 天枫庄资源网 圆月山庄资源网 无争山庄资源网 神水资源网 移花宫资源网 神剑山庄资源网 无为清净楼资源网 金钱帮资源网 丐帮资源网 华山资源网 极乐门资源网 小李飞刀资源网 凤求凰客栈 风云阁资源网 金狮镖局 鸳鸯亭资源网 千金楼资源网 更多链接
快活林资源网 Design By www.csstdc.com