vue3 diff 算法示例

目录
  • 一、可能性(常见):
  • 二、找规律
  • 三、算法优化
  • 最长的递增子序列
  • 完整代码

一、可能性(常见):

1.

旧的:a b c
新的:a b c d

2.

旧的:  a b c
新的:d a b c

3.

旧的:a b c d
新的:a b c

4.

旧的:d a b c
新的:  a b c

5.

旧的:a b c d e i f g
新的:a b e c d h f g

对应的真实虚拟节点(为方便理解,文中用字母代替):

// vnode对象
const a = {
  type: 'div', // 标签
  props: {style: {color: 'red'}}, // 属性
  children: [], // 子元素
  key: 'key1', // key
  el: '<div style="color: 'red'"></div>', // 真实dom节点
  ...
}

二、找规律

去掉前面和后面相同的部分

// c1表示旧的子节点,c2表示新的子节点
const patchKeyedChildren = (c1, c2) => {
  let i = 0
  let e1 = c1.length - 1
  let e2 = c2.length - 1
  // 从前面比
  while (i <= e1 && i <= e2) {
    const n1 = c1[i]
    const n2 = c2[i]
    // 标签和key是否相同
    // if (n1.type === n2.type && n1.key === n2.key)
    if (n1 === n2) {
      // 继续对比其属性和子节点
    } else {
      break
    }
    i++
  }
  // 从后面比
  while (i <= e1 && i <= e2) {
    const n1 = c1[e1]
    const n2 = c2[e2]
    // 标签和key是否相同
    // if (n1.type === n2.type && n1.key === n2.key)
    if (n1 === n2) {
      // 继续对比其属性和子节点
    } else {
      break
    }
    e1--
    e2--
  }
  console.log(i, e1, e2)
}
// 调用示例
patchKeyedChildren(['a', 'b', 'c', 'd'], ['a', 'b', 'c'])

通过这个函数可以得到:

1.

旧的:a b c
新的:a b c d

i = 3  e1 = 2  e2 = 3

2.

旧的:  a b c
新的:d a b c

i = 0  e1 = -1  e2 = 0

3.

旧的:a b c d
新的:a b c

i = 3  e1 = 3  e2 = 2

4.

旧的:d a b c
新的:  a b c

i = 0  e1 = 0  e2 = -1

5.

旧的:a b c d e i f g
新的:a b e c d h f g

i = 2  e1 = 5  e2 = 5

扩展:

旧的:a b c
新的:a b c d e f
i = 3  e1 = 2  e2 = 5

旧的:a b c
新的:a b c
i = 3  e1 = 2  e2 = 2

旧的:e d a b c
新的:    a b c
i = 0  e1 = 1  e2 = -1

旧的:c d e  
新的:e c d h
i = 0  e1 = 2  e2 = 3

从上面结果中我们可以找到规律:

  • 当i大于e1时,只需添加新的子节点
  • 当i大于e2时,只需删除旧的子节点
// 当i大于e1时
if (i > e1) {
  if (i <= e2) {
    while (i <= e2) {
      const nextPos = e2 + 1
      const anchor = nextPos < c2.length ? c2[nextPos].el : null
      // 添加新的子节点c2[i]在anchor的前面
      // todo
      i++
    }
  }
}
// 当i大于e2时
else if (i > e2) {
  if (i <= e1) {
    while (i <= e1) {
      // 删除旧的子节点c1[i]
      // todo
      i++
    }
  }
}
  • 其它,特殊处理
// 其它
let s1 = i
let s2 = i
// 以新的子节点作为参照物
const keyToNewIndexMap = new Map()
for (let i = s2; i <= e2; i++) {
  // 节点的key做为唯一值
  // keyToNewIndexMap.set(c2[i].key, i)
  keyToNewIndexMap.set(c2[i], i)
}
// 新的总个数
const toBePatched = e2 - s2 + 1
// 记录新子节点在旧子节点中的索引
const newIndexToOldIndexMap = new Array(toBePatched).fill(0)
// 循环老的子节点
for (let i = s1; i <= e1; i++) {
  const oldChild = c1[i]
  // let newIndex = keyToNewIndexMap.get(oldChild.key)
  let newIndex = keyToNewIndexMap.get(oldChild)
  // 在新子节点中不存在
  if (newIndex === undefined) {
    // 删除oldChild
    // todo
  } else {
    newIndexToOldIndexMap[newIndex - s2] = i + 1 // 永远不会等于0, 这样0就可以表示需要创建了
    // 继续对比其属性和子节点
    // todo
  }
}
console.log(newIndexToOldIndexMap)
// 需要移动位置
for (let i = toBePatched - 1; i >= 0; i--) {
  let index = i + s2
  let current = c2[index]
  let anchor = index + 1 < c2.length ? c2[index + 1].el : null
  if (newIndexToOldIndexMap[i] === 0) {
    // 在anchor前面插入新的节点current
    // todo
  } else {
    // 在anchor前面插入对应旧节点.el,current.el元素等于对应的旧节点.el(在其它代码中赋值了)
    // todo
  }
}

第1种和第2种比较简单,不做过多的讲解,我们来看看第3种,以下面为例

序号: 0 1  2 3 4 5  6 7
旧的:(a b) c d e i (f g)
新的:(a b) e c d h (f g)

  • 前面a b和后面f g是一样的,会去掉,只剩中间乱序部分
  • 以新的节点为参照物,循环旧的节点,从旧的节点中去掉新的没有的节点,如i
  • 标记旧的中没有的节点,没有就为0,表示需要创建;有就序号+1,表示可以复用

标记:       4+1 2+1 3+1  0
新的:(...)   e   c   d   h (...)

  • 从后往前循坏,h为0,创建,放在它下一个f前面;d不为0,复用旧的中的d,放在h前面;c不为0,复用旧的中的c,放在d前面;e不为0,复用旧的中的e,放在c前面

到目的为止,新旧元素的更替已经全部完成,但大家有没有发现一个问题,e c d h四个元素都移动了一次,我们可以看出如果只移动e和创建h,c和d保持不变,效率会更高

三、算法优化

1.

序号: 0 1  2 3 4 5  6 7
旧的:(a b) c d e i (f g)
新的:(a b) e c d h (f g)
对应的标记是[5, 3, 4, 0]

2.

序号:0 1 2 3 4 5
旧的:c d e i f g
新的:e c d f g j
对应的标记是[3, 1, 2, 5, 6, 0]

从上面两个例子中可以看出:
第1个的最优解是找到c d,只需移动e,创建h
第2个的最优解是找到c d f g,只需移动e,创建j

过程:

  • 从标记中找到最长的递增子序列
  • 通过最长的递增子序列找到对应的索引值
  • 通过索引值找到对应的值

注意0表示直接创建,不参与计算

例子:

  • [3, 1, 2, 5, 6, 0]的最长的递增子序列为[1, 2, 5, 6],
  • 对应的索引为[1, 2, 3, 4],
  • 然后我们遍历e c d f g j,标记中为0的,比如j,直接创建;c d f g索引分别等于1 2 3 4,保持不变;e等于0,移动
// 需要移动位置
// 找出最长的递增子序列对应的索引值,如:[5, 3, 4, 0] -> [1, 2]
let increment = getSequence(newIndexToOldIndexMap)
console.log(increment)
let j = increment.length - 1
for (let i = toBePatched - 1; i >= 0; i--) {
  let index = i + s2
  let current = c2[index]
  let anchor = index + 1 < c2.length ? c2[index + 1].el : null
  if (newIndexToOldIndexMap[i] === 0) {
    // 在anchor前面插入新的节点current
    // todo
  } else {
    if (i !== increment[j]) {
      // 在anchor前面插入对应旧节点.el,current.el元素等于对应的旧节点.el(在其它代码中赋值了)
      // todo
    } else { // 不变
      j--
    }
  }
}

最长的递增子序列

// 最长的递增子序列,https://en.wikipedia.org/wiki/Longest_increasing_subsequence
function getSequence(arr) {
  const len = arr.length
  const result = [0] // 以第一项为基准
  const p = arr.slice() // 标记索引,slice为浅复制一个新的数组
  let resultLastIndex
  let start
  let end
  let middle
  for (let i = 0; i < len; i++) {
    let arrI = arr[i]
    if (arrI !== 0) { // vue中等于0,表示需要创建
      resultLastIndex = result[result.length - 1]
      // 插到末尾
      if (arr[resultLastIndex] < arrI) {
        result.push(i)
        p[i] = resultLastIndex // 前面的那个是谁
        continue
      }
      // 递增序列,二分类查找
      start = 0
      end = result.length - 1
      while(start < end) {
        middle = (start + end) >> 1 // 相当于Math.floor((start + end)/2)
        if (arr[result[middle]] < arrI) {
          start = middle + 1
        } else  {
          end = middle
        }
      }
      // 找到最近的哪一项比它大的,替换
      if (arr[result[end]] > arrI) {
        result[end] = i
        if (end > 0) {
          p[i] = result[end - 1] // 前面的那个是谁
        }
      }
    }
  }
  let i = result.length
  let last = result[i - 1]
  while(i-- > 0) {
    result[i] = last
    last = p[last]
  }
  return result
}
console.log(getSequence([5, 3, 4, 0])) // [1, 2]
console.log(getSequence([3, 1, 2, 5, 6, 0])) // [ 1, 2, 3, 4 ]

讲解后续补充...

完整代码

// 最长的递增子序列,https://en.wikipedia.org/wiki/Longest_increasing_subsequence
function getSequence(arr) {
  const len = arr.length
  const result = [0] // 以第一项为基准
  const p = arr.slice() // 标记索引,slice为浅复制一个新的数组
  let resultLastIndex
  let start
  let end
  let middle
  for (let i = 0; i < len; i++) {
    let arrI = arr[i]
    if (arrI !== 0) { // vue中等于0,表示需要创建
      resultLastIndex = result[result.length - 1]
      // 插到末尾
      if (arr[resultLastIndex] < arrI) {
        result.push(i)
        p[i] = resultLastIndex // 前面的那个是谁
        continue
      }
      // 递增序列,二分类查找
      start = 0
      end = result.length - 1
      while(start < end) {
        middle = (start + end) >> 1 // 相当于Math.floor((start + end)/2)
        if (arr[result[middle]] < arrI) {
          start = middle + 1
        } else  {
          end = middle
        }
      }
      // 找到最近的哪一项比它大的,替换
      if (arr[result[end]] > arrI) {
        result[end] = i
        if (end > 0) {
          p[i] = result[end - 1] // 前面的那个是谁
        }
      }
    }
  }
  let i = result.length
  let last = result[i - 1]
  while(i-- > 0) {
    result[i] = last
    last = p[last]
  }
  return result
}
// c1表示旧的子节点,c2表示新的子节点
const patchKeyedChildren = (c1, c2) => {
  let i = 0
  let e1 = c1.length - 1
  let e2 = c2.length - 1
  // 从前面比
  while (i <= e1 && i <= e2) {
    const n1 = c1[i]
    const n2 = c2[i]
    // 标签和key是否相同
    // if (n1.type === n2.type && n1.key === n2.key)
    if (n1 === n2) {
      // 继续对比其属性和子节点
    } else {
      break
    }
    i++
  }
  // 从后面比
  while (i <= e1 && i <= e2) {
    const n1 = c1[e1]
    const n2 = c2[e2]
    // 标签和key是否相同
    // if (n1.type === n2.type && n1.key === n2.key)
    if (n1 === n2) {
      // 继续对比其属性和子节点
    } else {
      break
    }
    e1--
    e2--
  }
  console.log(i, e1, e2)
  // 当i大于e1时
  if (i > e1) {
    if (i <= e2) {
      while (i <= e2) {
        const nextPos = e2 + 1
        const anchor = nextPos < c2.length ? c2[nextPos].el : null
        // 添加子节点c2[i]在anchor的前面
        // todo
        i++
      }
    }
  }
  // 当i大于e2时
  else if (i > e2) {
    if (i <= e1) {
      while (i <= e1) {
        // 删除子节点c1[i]
        // todo
        i++
      }
    }
  }
  // 其它
  else {
    let s1 = i
    let s2 = i
    // 以新的子节点作为参照物
    const keyToNewIndexMap = new Map()
    for (let i = s2; i <= e2; i++) {
      // 节点的key做为唯一值
      // keyToNewIndexMap.set(c2[i].key, i)
      keyToNewIndexMap.set(c2[i], i)
    }
    // 新的总个数
    const toBePatched = e2 - s2 + 1
    // 记录新子节点在旧子节点中的索引
    const newIndexToOldIndexMap = new Array(toBePatched).fill(0)
    // 循环老的子节点
    for (let i = s1; i <= e1; i++) {
      const oldChild = c1[i]
      // let newIndex = keyToNewIndexMap.get(oldChild.key)
      let newIndex = keyToNewIndexMap.get(oldChild)
      // 在新子节点中不存在
      if (newIndex === undefined) {
        // 删除oldChild
        // todo
      } else {
        newIndexToOldIndexMap[newIndex - s2] = i + 1 // 永远不会等于0, 这样0就可以表示需要创建了
        // 继续对比其属性和子节点
        // todo
      }
    }
    console.log(newIndexToOldIndexMap)
    // 需要移动位置
    // 找出最长的递增子序列对应的索引值,如:[5, 3, 4, 0] -> [1, 2]
    let increment = getSequence(newIndexToOldIndexMap)
    console.log(increment)
    let j = increment.length - 1
    for (let i = toBePatched - 1; i >= 0; i--) {
      let index = i + s2
      let current = c2[index]
      let anchor = index + 1 < c2.length ? c2[index + 1].el : null
      if (newIndexToOldIndexMap[i] === 0) {
        // 在anchor前面插入新的节点current
        // todo
      } else {
        if (i !== increment[j]) {
          // 在anchor前面插入对应旧节点.el,current.el元素等于对应的旧节点.el(在其它代码中赋值了)
          // todo
        } else { // 不变
          j--
        }
      }
    }
  }
}
// 调用示例
patchKeyedChildren(['c', 'd', 'e', 'i', 'f', 'g'], ['e', 'c', 'd', 'f', 'g', 'j'])

以上就是vue3 diff 算法示例的详细内容,更多关于vue3 diff 算法的资料请关注我们其它相关文章!

(0)

相关推荐

  • vue的diff算法知识点总结

    源码:https://github.com/vuejs/vue/blob/dev/src/core/vdom/patch.js 虚拟dom diff算法首先要明确一个概念就是diff的对象是虚拟dom,更新真实dom则是diff算法的结果 Vnode基类 constructor ( ... ) { this.tag = tag this.data = data this.children = children this.text = text this.elm = elm this.ns = u

  • 详解vue的diff算法原理

    我的目标是写一个非常详细的关于diff的干货,所以本文有点长.也会用到大量的图片以及代码举例,目的让看这篇文章的朋友一定弄明白diff的边边角角. 先来了解几个点... 1. 当数据发生变化时,vue是怎么更新节点的? 要知道渲染真实DOM的开销是很大的,比如有时候我们修改了某个数据,如果直接渲染到真实dom上会引起整个dom树的重绘和重排,有没有可能我们只更新我们修改的那一小块dom而不要更新整个dom呢?diff算法能够帮助我们. 我们先根据真实DOM生成一颗 virtual DOM ,当

  • 简单谈谈Vue中的diff算法

    目录 概述 虚拟Dom(virtual dom) 原理 实现过程 patch方法 sameVnode函数 patchVnode函数 updateChildren函数 结语 概述 diff算法,可以说是Vue的一个比较核心的内容,之前只会用Vue来进行一些开发,具体的核心的内容其实涉猎不多,最近正好看了下这方面的内容,简单聊下Vue2.0的diff算法的实现吧,具体从几个实现的函数来进行分析 虚拟Dom(virtual dom) virtual DOM是将真实的DOM的数据抽取出来,以对象的形式模

  • Vue3组件更新中的DOM diff算法示例详解

    目录 同步头部节点 同步尾部节点 添加新的节点 删除多余节点 处理未知子序列 移动子节点 建立索引图 更新和移除旧节点 移动和挂载新节点 最长递增子序列 总结 总结 在vue的组件更新过程中,新子节点数组相对于旧子节点数组的变化,无非是通过更新.删除.添加和移动节点来完成,而核心 diff 算法,就是在已知旧子节点的 DOM 结构.vnode 和新子节点的 vnode 情况下,以较低的成本完成子节点的更新为目的,求解生成新子节点 DOM 的系列操作. 举例来说,假说我们有一个如下的列表 <ul>

  • 详解vue3.0 diff算法的使用(超详细)

    前言:随之vue3.0beta版本的发布,vue3.0正式版本相信不久就会与我们相遇.尤玉溪在直播中也说了vue3.0的新特性typescript强烈支持,proxy响应式原理,重新虚拟dom,优化diff算法性能提升等等.小编在这里仔细研究了vue3.0beta版本diff算法的源码,并希望把其中的细节和奥妙和大家一起分享. 首先我们来思考一些大中厂面试中,很容易问到的问题: 1 什么时候用到diff算法,diff算法作用域在哪里? 2 diff算法是怎么运作的,到底有什么作用? 3 在v-f

  • 详解Vue2的diff算法

    前言 双端比较算法是vue2.x采用的diff算法,本篇文章只是对双端比较算法粗略的过程进行了一下分析,具体细节还是得Vue源码,Vue的源码在这 过程 假设当前有两个数组arr1和arr2 let arr1 = [1,2,3,4,5] let arr2 = [4,3,5,1,2] 那么其过程有五步 arr1[0] 和 arr2[0]比较 arr1[ arr1.length-1 ] 和 arr2[ arr2.length-1 ] 比较 arr1[0] 和 arr2[ arr2.length-1

  • vue3 diff 算法示例

    目录 一.可能性(常见): 二.找规律 三.算法优化 最长的递增子序列 完整代码 一.可能性(常见): 1. 旧的:a b c新的:a b c d 2. 旧的:  a b c新的:d a b c 3. 旧的:a b c d新的:a b c 4. 旧的:d a b c新的:  a b c 5. 旧的:a b c d e i f g新的:a b e c d h f g 对应的真实虚拟节点(为方便理解,文中用字母代替): // vnode对象 const a = { type: 'div', // 标

  • Vue3 diff算法的简单解刨

    目录 性能比较 前置与后置的预处理 节点无序 最长递增子序列 上篇我们介绍了vue2中的双端diff算法的优势(相比于简单算法相同场景下移动DOM次数更少).如今Vue3的势头正盛,在diff算法方面也做了相应的变化,利用到了最长递增子序列把性能又提升了一个档次.对于技术栈使用Vue的同学来说又是必须要学习的一部分. 性能比较 此图借鉴了<Vuejs设计与实现>这本书 ivi和inferno所采用的快速diff算法的性能要稍优于Vue2的双端diff算法.既然快速diff算法这么高效,我们当然

  • Vue3 diff算法之双端diff算法详解

    目录 双端Diff算法 双端比较的原理 简单Diff的不足 双端Diff介绍 Diff流程 第一次diff 第二次diff 第三次diff 第四次diff 双端Diff的优势 非理想情况的处理方式 添加新元素 移除不存在得节点 双端Diff完整代码 双端Diff算法 双端Diff在可以解决更多简单Diff算法处理不了的场景,且比简单Diff算法性能更好.本篇是以简单Diff算法的案例来展开的,不过没有了解简单Diff算法直接看双端Diff算法也是可以看明白的. 双端比较的原理 引用简单Diff算

  • React Diff算法不采用Vue的双端对比原因详解

    目录 前言 React 官方的解析 Fiber 的结构 Fiber 链表的生成 React 的 Diff 算法 第一轮,常见情况的比对 第二轮,不常见的情况的比对 重点如何协调更新位置信息 小结 图文解释 React Diff 算法 最简单的 Diff 场景 复杂的 Diff 场景 Vue3 的 Diff 算法 第一轮,常见情况的比对 第二轮,复杂情况的比对 Vue2 的 Diff 算法 第一轮,简单情况的比对 第二轮,不常见的情况的比对 React.Vue3.Vue2 的 Diff 算法对比

  • React实现核心Diff算法的示例代码

    目录 Diff算法的设计思路 Demo介绍 Diff算法实现 遍历前的准备工作 遍历after 遍历后的收尾工作 总结 Diff算法的设计思路 试想,Diff算法需要考虑多少种情况呢?大体分三种,分别是: 节点属性变化,比如: // 更新前 <ul> <li key="0" className="before">0</li> <li key="1">1</li> </ul>

  • 详解为什么Vue中不要用index作为key(diff算法)

    前言 Vue 中的 key 是用来做什么的?为什么不推荐使用 index 作为 key?常常听说这样的问题,本篇文章带你从原理来一探究竟. 另外本文的结论对于性能的毁灭是针对列表子元素顺序会交换.或者子元素被删除的特殊情况,提前说明清楚,喷子绕道. 本篇已经收录在 Github 仓库,欢迎 Star: https://github.com/sl1673495/blogs/issues/39 示例 以这样一个列表为例: <ul> <li>1</li> <li>

  • 深入浅析React中diff算法

    React中diff算法的理解 diff算法用来计算出Virtual DOM中改变的部分,然后针对该部分进行DOM操作,而不用重新渲染整个页面,渲染整个DOM结构的过程中开销是很大的,需要浏览器对DOM结构进行重绘与回流,而diff算法能够使得操作过程中只更新修改的那部分DOM结构而不更新整个DOM,这样能够最小化操作DOM结构,能够最大程度上减少浏览器重绘与回流的规模. 虚拟DOM diff算法的基础是Virtual DOM,Virtual DOM是一棵以JavaScript对象作为基础的树,

随机推荐