聊聊 Vue 的双端 diff 算法

发表于 1年以前  | 总阅读数:569 次

Vue 和 React 都是基于 vdom 的前端框架,组件渲染会返回 vdom,渲染器再把 vdom 通过增删改的 api 同步到 dom。

当再次渲染时,会产生新的 vdom,渲染器会对比两棵 vdom 树,对有差异的部分通过增删改的 api 更新到 dom。

这里对比两棵 vdom 树,找到有差异的部分的算法,就叫做 diff 算法。

diff 算法是渲染器中最复杂的部分,也是面试的热点问题。今天我们就通过 Vue 的 diff 算法来探究下 diff 算法吧。

diff 算法

我们知道,两棵树做 diff,复杂度是 O(n^3) 的,因为每个节点都要去和另一棵树的全部节点对比一次,这就是 n 了,如果找到有变化的节点,执行插入、删除、修改也是 n 的复杂度。所有的节点都是这样,再乘以 n,所以是 O(n * n * n) 的复杂度。

这样的复杂度对于前端框架来说是不可接受的,这意味着 1000 个节点,渲染一次就要处理 1000 * 1000 * 1000,一共 10 亿次。

所以前端框架的 diff 约定了两种处理原则:只做同层的对比,type 变了就不再对比子节点。

因为 dom 节点做跨层级移动的情况还是比较少的,一般情况下都是同一层级的 dom 的增删改。

这样只要遍历一遍,对比一下 type 就行了,是 O(n) 的复杂度,而且 type 变了就不再对比子节点,能省下一大片节点的遍历。另外,因为 vdom 中记录了关联的 dom 节点,执行 dom 的增删改也不需要遍历,是 O(1)的,整体的 diff 算法复杂度就是 O(n) 的复杂度。

1000 个节点渲染一次最多对比 1000 次,这样的复杂度就是可接受的范围了。

但是这样的算法虽然复杂度低了,却还是存在问题的。

比如一组节点,假设有 5 个,类型是 ABCDE,下次渲染出来的是 EABCD,这时候逐一对比,发现 type 不一样,就会重新渲染这 5 个节点。

而且根据 type 不同就不再对比子节点的原则,如果这些节点有子节点,也会重新渲染。

dom 操作是比较慢的,这样虽然 diff 的算法复杂度是低了,重新渲染的性能也不高。

所以,diff 算法除了考虑本身的时间复杂度之外,还要考虑一个因素:dom 操作的次数。

上面那个例子的 ABCDE 变为 EABCD,很明显只需要移动一下 E 就行了,根本不用创建新元素。

但是怎么对比出是同个节点发生了移动呢?

判断 type 么?那不行,同 type 的节点可能很多,区分不出来的。

最好每个节点都是有唯一的标识。

所以当渲染一组节点的时候,前端框架会让开发者指定 key,通过 key 来判断是不是有点节点只是发生了移动,从而直接复用。

这样,diff 算法处理一组节点的对比的时候,就要根据 key 来再做一次算法的优化。

我们会把基于 key 的两组节点的 diff 算法叫做多节点 diff 算法,它是整个 vdom 的 diff 算法的一部分。

接下来我们来学习一下多节点 diff 算法:

简单 diff

假设渲染 ABCD 一组节点,再次渲染是 DCAB,这时候怎么处理呢?

多节点 diff 算法的目的是为了尽量复用节点,通过移动节点代替创建。

所以新 vnode 数组的每个节点我们都要找下在旧 vnode 数组中有没有对应 key 的,有的话就移动到新的位置,没有的话再创建新的。

也就是这样的:

const oldChildren = n1.children
const newChildren = n2.children

let lastIndex = 0
// 遍历新的 children
for (let i = 0; i < newChildren.length; i++) {
    const newVNode = newChildren[i]
    let j = 0
    let find = false
    // 遍历旧的 children
    for (j; j < oldChildren.length; j++) {
      const oldVNode = oldChildren[j]
      // 如果找到了具有相同 key 值的两个节点,则调用 patch 函数更新
      if (newVNode.key === oldVNode.key) {
        find = true
        patch(oldVNode, newVNode, container)

        处理移动...

        break //跳出循环,处理下一个节点
      }
   }
   // 没有找到就是新增了
   if (!find) {
      const prevVNode = newChildren[i - 1]
      let anchor = null
      if (prevVNode) {
        anchor = prevVNode.el.nextSibling
      } else {
        anchor = container.firstChild
      }
      patch(null, newVNode, container, anchor)
   }
}

这里的 patch 函数的作用是更新节点的属性,重新设置事件监听器。如果没有对应的旧节点的话,就是插入节点,需要传入一个它之后的节点作为锚点 anchor。

我们遍历处理新的 vnode:

先从旧的 vnode 数组中查找对应的节点,如果找到了就代表可以复用,接下来只要移动就好了。

如果没找到,那就执行插入,锚点是上一个节点的 nextSibling。

那如果找到了可复用的节点之后,那移动到哪里呢?

其实新的 vnode 数组中记录的顺序就是目标的顺序。所以把对应的节点按照新 vnode 数组的顺序来移动就好了。

const prevVNode = newChildren[i - 1]
if (prevVNode) {
    const anchor = prevVNode.el.nextSibling
    insert(newVNode.el, container, anchor)
}

要插入到 i 的位置,那就要取 i-1 位置的节点的 nextSibling 做为锚点来插入当前节点。

但是并不是所有的节点都需要移动,比如处理到第二个新的 vnode,发现它在旧的 vnode 数组中的下标为 4,说明本来就是在后面了,那就不需要移动了。反之,如果是 vnode 查找到的对应的旧的 vnode 在当前 index 之前才需要移动。

也就是这样:

let j = 0
let find = false
// 遍历旧的 children
for (j; j < oldChildren.length; j++) {
    const oldVNode = oldChildren[j]
    // 如果找到了具有相同 key 值的两个节点,则调用 patch 函数更新之
    if (newVNode.key === oldVNode.key) {
        find = true
        patch(oldVNode, newVNode, container)

        if (j < lastIndex) { // 旧的 vnode 数组的下标在上一个 index 之前,需要移动
          const prevVNode = newChildren[i - 1]
          if (prevVNode) {
            const anchor = prevVNode.el.nextSibling
            insert(newVNode.el, container, anchor)
          }
        } else {// 不需要移动
          // 更新 lastIndex
          lastIndex = j
        }
        break
    }
}

查找新的 vnode 在旧的 vnode 数组中的下标,如果找到了的话,说明对应的 dom 就是可以复用的,先 patch 一下,然后移动。

移动的话判断下下标是否在 lastIndex 之后,如果本来就在后面,那就不用移动,更新下 lastIndex 就行。

如果下标在 lastIndex 之前,说明需要移动,移动到的位置前面分析过了,就是就是新 vnode 数组 i-1 的后面。

这样,我们就完成了 dom 节点的复用和移动。

新的 vnode 数组全部处理完后,旧的 vnode 数组可能还剩下一些不再需要的,那就删除它们:

// 遍历旧的节点
for (let i = 0; i < oldChildren.length; i++) {
    const oldVNode = oldChildren[i]
    // 拿着旧 VNode 去新 children 中寻找相同的节点
    const has = newChildren.find(
      vnode => vnode.key === oldVNode.key
    )
    if (!has) {
      // 如果没有找到相同的节点,则移除
      unmount(oldVNode)
    }
}

这样,我们就完成了两组 vnode 的 diff 和对应 dom 的增删改。

小结一下:

diff 算法的目的是根据 key 复用 dom 节点,通过移动节点而不是创建新节点来减少 dom 操作。

对于每个新的 vnode,在旧的 vnode 中根据 key 查找一下,如果没查找到,那就新增 dom 节点,如果查找到了,那就可以复用。

复用的话要不要移动要判断下下标,如果下标在 lastIndex 之后,就不需要移动,因为本来就在后面,反之就需要移动。

最后,把旧的 vnode 中在新 vnode 中没有的节点从 dom 树中删除。

这就是一个完整的 diff 算法的实现。

这个 diff 算法我们是从一端逐个处理的,叫做简单 diff 算法。

简单 diff 算法其实性能不是最好的,比如旧的 vnode 数组是 ABCD,新的 vnode 数组是 DABC,按照简单 diff 算法,A、B、C 都需要移动。

那怎么优化这个算法呢?

从一个方向顺序处理会有这个问题,那从两个方向同时对比呢?

这就是双端 diff 算法:

双端 diff

简单 diff 算法能够实现 dom 节点的复用,但有的时候会做一些没必要的移动。双端 diff 算法解决了这个问题,它是从两端进行对比。

我们需要 4 个指针,分别指向新旧两个 vnode 数组的头尾:

头和尾的指针向中间移动,直到 oldStartIdx <= oldEndIdx 并且 newStartIdx <= newEndIdx,说明就处理完了全部的节点。

每次对比下两个头指针指向的节点、两个尾指针指向的节点,头和尾指向的节点,是不是 key是一样的,也就是可复用的。

如果是可复用的话就直接用,调用 patch 更新一下,如果是头尾这种,还要移动下位置。

也就是这样的:

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (oldStartVNode.key === newStartVNode.key) { // 头头
    patch(oldStartVNode, newStartVNode, container)
    oldStartVNode = oldChildren[++oldStartIdx]
    newStartVNode = newChildren[++newStartIdx]
  } else if (oldEndVNode.key === newEndVNode.key) {//尾尾
    patch(oldEndVNode, newEndVNode, container)
    oldEndVNode = oldChildren[--oldEndIdx]
    newEndVNode = newChildren[--newEndIdx]
  } else if (oldStartVNode.key === newEndVNode.key) {//头尾,需要移动
    patch(oldStartVNode, newEndVNode, container)
    insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling)

    oldStartVNode = oldChildren[++oldStartIdx]
    newEndVNode = newChildren[--newEndIdx]
  } else if (oldEndVNode.key === newStartVNode.key) {//尾头,需要移动
    patch(oldEndVNode, newStartVNode, container)
    insert(oldEndVNode.el, container, oldStartVNode.el)

    oldEndVNode = oldChildren[--oldEndIdx]
    newStartVNode = newChildren[++newStartIdx]
  } else {

    // 头尾没有找到可复用的节点
  }
}

头头和尾尾的对比比较简单,头尾和尾头的对比还要移动下节点。

比如旧 vnode 的头节点是新的 vnode 的尾节点,那就要把它移动到旧的 vnode 的尾节点的位置。

也就是:

insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling)

插入节点的锚点节点是 oldEndVNode 对应的 dom 节点的 nextSibling。

如果旧 vnode 的尾节点是新 vnode 的头结点,那就要把它移动到旧 vnode 的头结点的位置。

也就是:

insert(oldEndVNode.el, container, oldStartVNode.el)

插入节点的锚点节点是 oldStartVNode 对应的 dom 节点(因为要插在它之前)。

从双端进行对比,能尽可能的减少节点移动的次数。

当然,还要处理下如果双端都没有可复用节点的情况:

如果双端都没有可复用节点,那就在旧节点数组中找,找到了就把它移动过来,并且原位置置为 undefined。没找到的话就插入一个新的节点。

也就是这样:

const idxInOld = oldChildren.findIndex(
  node => node.key === newStartVNode.key
)
if (idxInOld > 0) {
  const vnodeToMove = oldChildren[idxInOld]
  patch(vnodeToMove, newStartVNode, container)
  insert(vnodeToMove.el, container, oldStartVNode.el)
  oldChildren[idxInOld] = undefined
} else {
  patch(null, newStartVNode, container, oldStartVNode.el)
}

因为有了一些 undefined 的节点,所以要加上空节点的处理逻辑:

if (!oldStartVNode) {
    oldStartVNode = oldChildren[++oldStartIdx]
} else if (!oldEndVNode) {
    oldEndVNode = newChildren[--oldEndIdx]
}

这样就完成了节点的复用和移动的逻辑。

那确实没有可复用的节点的那些节点呢?

经过前面的移动之后,剩下的节点都被移动到了中间,如果新 vnode 有剩余,那就批量的新增,如果旧 vnode 有剩余那就批量的删除。

因为前面一个循环的判断条件是 oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx,这样如果 old vnode 多了,最后 newStartIdx 会小于 newEndIdx。如果 new vnode 多了,最后 oldStartIdx 会小于 oldEndIdx。

所以判断条件是这样的:

if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {
  // 添加新节点
  for (let i = newStartIdx; i <= newEndIdx; i++) {
    patch(null, newChildren[i], container, oldStartVNode.el)
  }
} else if (newEndIdx < newStartIdx && oldStartIdx <= oldEndIdx) {
  // 移除操作
  for (let i = oldStartIdx; i <= oldEndIdx; i++) {
    unmount(oldChildren[i])
  }
}

这样就是一个完整的 diff 算法了,包括查找可复用节点和移动节点、新增和删除节点。

而且因为从两侧查找节点,会比简单 diff 算法性能更好一些。

比如 ABCD 到 DABC,简单 diff 算法需要移动 ABC 三个节点,而双端 diff 算法只需要移动 D 一个节点。

小结一下:

双端 diff 是头尾指针向中间移动的同时,对比头头、尾尾、头尾、尾头是否可以复用,如果可以的话就移动对应的 dom 节点。

如果头尾没找到可复用节点就遍历 vnode 数组来查找,然后移动对应下标的节点到头部。

最后还剩下旧的 vnode 就批量删除,剩下新的 vnode 就批量新增。

双端 diff 算法是 Vue2 采用的 diff 算法,性能还不错。

后来,Vue3 又对 diff 算法进行了一次升级,叫做快速 diff 算法。这个后面再讲。

总结

React 和 Vue 都是基于 vdom 的前端框架,组件产生 vdom,渲染器再把 vdom 通过增删改的 dom api 更新到 dom。

当再次渲染出 vdom 时,就要新旧两棵 vdom 树做 diff,只更新变化的 dom 节点。

两棵树的 diff 是 O(n^3) 的,时间复杂度太高,因此前端框架规定了只做同层 diff,还有 type 不一样就认为节点不一样,不再对比子节点。这样时间复杂度一下子就降到了 O(n)。

但是对于多个子节点的 diff 不能粗暴的删除和新增,要尽量复用已有的节点,也就是通过移动代替新增。

所以多节点的时候,要指定 key,然后 diff 算法根据 key 来查找和复用节点。

简单 diff 算法是依次根据 key 查找旧节点的,移动的话通过 lastIndex 判断,大于它就不用动,小于它才需要移动。剩下的节点再批量删除和新增。

但是简单 diff 算法局限性还是比较大的,有些情况下性能并不好,所以 vue2 用的是双端 diff 算法。

双端 diff 算法是头尾指针向中间移动,分别判断头尾节点是否可以复用,如果没有找到可复用的节点再去遍历查找对应节点的下标,然后移动。全部处理完之后也要对剩下的节点进行批量的新增和删除。

其实 diff 算法最重要的就是找到可复用的节点,然后移动到正确的位置。只不过不同的算法查找顺序不一样。

vue2 是用的双端 diff 的算法,而 vue3 则通过最长递增子序列的算法做了进一步的优化,关于优化后的 diff 算法,我们之后再聊。

本文由哈喽比特于1年以前收录,如有侵权请联系我们。
文章来源:https://mp.weixin.qq.com/s/mFGT6szPzYuCaz1Rgvt9TQ

 相关推荐

刘强东夫妇:“移民美国”传言被驳斥

京东创始人刘强东和其妻子章泽天最近成为了互联网舆论关注的焦点。有关他们“移民美国”和在美国购买豪宅的传言在互联网上广泛传播。然而,京东官方通过微博发言人发布的消息澄清了这些传言,称这些言论纯属虚假信息和蓄意捏造。

发布于:6月以前  |  808次阅读  |  详细内容 »

博主曝三大运营商,将集体采购百万台华为Mate60系列

日前,据博主“@超能数码君老周”爆料,国内三大运营商中国移动、中国电信和中国联通预计将集体采购百万台规模的华为Mate60系列手机。

发布于:6月以前  |  770次阅读  |  详细内容 »

ASML CEO警告:出口管制不是可行做法,不要“逼迫中国大陆创新”

据报道,荷兰半导体设备公司ASML正看到美国对华遏制政策的负面影响。阿斯麦(ASML)CEO彼得·温宁克在一档电视节目中分享了他对中国大陆问题以及该公司面临的出口管制和保护主义的看法。彼得曾在多个场合表达了他对出口管制以及中荷经济关系的担忧。

发布于:6月以前  |  756次阅读  |  详细内容 »

抖音中长视频App青桃更名抖音精选,字节再发力对抗B站

今年早些时候,抖音悄然上线了一款名为“青桃”的 App,Slogan 为“看见你的热爱”,根据应用介绍可知,“青桃”是一个属于年轻人的兴趣知识视频平台,由抖音官方出品的中长视频关联版本,整体风格有些类似B站。

发布于:6月以前  |  648次阅读  |  详细内容 »

威马CDO:中国每百户家庭仅17户有车

日前,威马汽车首席数据官梅松林转发了一份“世界各国地区拥车率排行榜”,同时,他发文表示:中国汽车普及率低于非洲国家尼日利亚,每百户家庭仅17户有车。意大利世界排名第一,每十户中九户有车。

发布于:6月以前  |  589次阅读  |  详细内容 »

研究发现维生素 C 等抗氧化剂会刺激癌症生长和转移

近日,一项新的研究发现,维生素 C 和 E 等抗氧化剂会激活一种机制,刺激癌症肿瘤中新血管的生长,帮助它们生长和扩散。

发布于:6月以前  |  449次阅读  |  详细内容 »

苹果据称正引入3D打印技术,用以生产智能手表的钢质底盘

据媒体援引消息人士报道,苹果公司正在测试使用3D打印技术来生产其智能手表的钢质底盘。消息传出后,3D系统一度大涨超10%,不过截至周三收盘,该股涨幅回落至2%以内。

发布于:7月以前  |  446次阅读  |  详细内容 »

千万级抖音网红秀才账号被封禁

9月2日,坐拥千万粉丝的网红主播“秀才”账号被封禁,在社交媒体平台上引发热议。平台相关负责人表示,“秀才”账号违反平台相关规定,已封禁。据知情人士透露,秀才近期被举报存在违法行为,这可能是他被封禁的部分原因。据悉,“秀才”年龄39岁,是安徽省亳州市蒙城县人,抖音网红,粉丝数量超1200万。他曾被称为“中老年...

发布于:6月以前  |  445次阅读  |  详细内容 »

亚马逊股东起诉公司和贝索斯,称其在购买卫星发射服务时忽视了 SpaceX

9月3日消息,亚马逊的一些股东,包括持有该公司股票的一家养老基金,日前对亚马逊、其创始人贝索斯和其董事会提起诉讼,指控他们在为 Project Kuiper 卫星星座项目购买发射服务时“违反了信义义务”。

发布于:6月以前  |  444次阅读  |  详细内容 »

苹果上线AppsbyApple网站,以推广自家应用程序

据消息,为推广自家应用,苹果现推出了一个名为“Apps by Apple”的网站,展示了苹果为旗下产品(如 iPhone、iPad、Apple Watch、Mac 和 Apple TV)开发的各种应用程序。

发布于:6月以前  |  442次阅读  |  详细内容 »

特斯拉美国降价引发投资者不满:“这是短期麻醉剂”

特斯拉本周在美国大幅下调Model S和X售价,引发了该公司一些最坚定支持者的不满。知名特斯拉多头、未来基金(Future Fund)管理合伙人加里·布莱克发帖称,降价是一种“短期麻醉剂”,会让潜在客户等待进一步降价。

发布于:6月以前  |  441次阅读  |  详细内容 »

光刻机巨头阿斯麦:拿到许可,继续对华出口

据外媒9月2日报道,荷兰半导体设备制造商阿斯麦称,尽管荷兰政府颁布的半导体设备出口管制新规9月正式生效,但该公司已获得在2023年底以前向中国运送受限制芯片制造机器的许可。

发布于:6月以前  |  437次阅读  |  详细内容 »

马斯克与库克首次隔空合作:为苹果提供卫星服务

近日,根据美国证券交易委员会的文件显示,苹果卫星服务提供商 Globalstar 近期向马斯克旗下的 SpaceX 支付 6400 万美元(约 4.65 亿元人民币)。用于在 2023-2025 年期间,发射卫星,进一步扩展苹果 iPhone 系列的 SOS 卫星服务。

发布于:6月以前  |  430次阅读  |  详细内容 »

𝕏(推特)调整隐私政策,可拿用户发布的信息训练 AI 模型

据报道,马斯克旗下社交平台𝕏(推特)日前调整了隐私政策,允许 𝕏 使用用户发布的信息来训练其人工智能(AI)模型。新的隐私政策将于 9 月 29 日生效。新政策规定,𝕏可能会使用所收集到的平台信息和公开可用的信息,来帮助训练 𝕏 的机器学习或人工智能模型。

发布于:6月以前  |  428次阅读  |  详细内容 »

荣耀CEO谈华为手机回归:替老同事们高兴,对行业也是好事

9月2日,荣耀CEO赵明在采访中谈及华为手机回归时表示,替老同事们高兴,觉得手机行业,由于华为的回归,让竞争充满了更多的可能性和更多的魅力,对行业来说也是件好事。

发布于:6月以前  |  423次阅读  |  详细内容 »

AI操控无人机能力超越人类冠军

《自然》30日发表的一篇论文报道了一个名为Swift的人工智能(AI)系统,该系统驾驶无人机的能力可在真实世界中一对一冠军赛里战胜人类对手。

发布于:7月以前  |  423次阅读  |  详细内容 »

AI生成的蘑菇科普书存在可致命错误

近日,非营利组织纽约真菌学会(NYMS)发出警告,表示亚马逊为代表的电商平台上,充斥着各种AI生成的蘑菇觅食科普书籍,其中存在诸多错误。

发布于:7月以前  |  420次阅读  |  详细内容 »

社交媒体平台𝕏计划收集用户生物识别数据与工作教育经历

社交媒体平台𝕏(原推特)新隐私政策提到:“在您同意的情况下,我们可能出于安全、安保和身份识别目的收集和使用您的生物识别信息。”

发布于:7月以前  |  411次阅读  |  详细内容 »

国产扫地机器人热销欧洲,国产割草机器人抢占欧洲草坪

2023年德国柏林消费电子展上,各大企业都带来了最新的理念和产品,而高端化、本土化的中国产品正在不断吸引欧洲等国际市场的目光。

发布于:6月以前  |  406次阅读  |  详细内容 »

罗永浩吐槽iPhone15和14不会有区别,除了序列号变了

罗永浩日前在直播中吐槽苹果即将推出的 iPhone 新品,具体内容为:“以我对我‘子公司’的了解,我认为 iPhone 15 跟 iPhone 14 不会有什么区别的,除了序(列)号变了,这个‘不要脸’的东西,这个‘臭厨子’。

发布于:6月以前  |  398次阅读  |  详细内容 »
 目录