您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

我让虚拟DOM的diff算法过程动起来了

时间:2022-10-30 11:11:15  来源:今日头条  作者:街角小林

去年写了一篇文章手写一个虚拟DOM库,彻底让你理解diff算法介绍虚拟DOM的patch过程和diff算法过程,当时使用的是双端diff算法,今年看到了Vue3使用的已经是快速diff算法,所以也想写一篇来记录一下,但是肯定已经有人写过了,所以就在想能不能有点不一样的,上次的文章主要是通过画图来一步步展示diff算法的每一种情况和过程,所以就在想能不能改成动画的形式,于是就有了这篇文章。当然目前的实现还是基于双端diff算法的,后续会补充上快速diff算法。

传送门:双端Diff算法动画演示。


 

界面就是这样的,左侧可以输入要比较的新旧VNode列表,然后点击启动按钮就会以动画的形式来展示从头到尾的过程,右侧是水平的三个列表,分别代表的是新旧的VNode列表,以及当前的真实DOM列表,DOM列表初始和旧的VNode列表一致,算法结束后会和新的VNode列表一致。

需要说明的是这个动画只包含diff算法的过程,不包含patch过程。

先来回顾一下双端diff算法的函数:

const diff = (el, oldChildren, newChildren) => {// 指针let oldStartIdx = 0let oldEndIdx = oldChildren.length - 1let newStartIdx = 0let newEndIdx = newChildren.length - 1// 节点let oldStartVNode = oldChildren[oldStartIdx]let oldEndVNode = oldChildren[oldEndIdx]let newStartVNode = newChildren[newStartIdx]let newEndVNode = newChildren[newEndIdx]while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {if (oldStartVNode === null) {oldStartVNode = oldChildren[++oldStartIdx]} else if (oldEndVNode === null) {oldEndVNode = oldChildren[--oldEndIdx]} else if (newStartVNode === null) {newStartVNode = oldChildren[++newStartIdx]} else if (newEndVNode === null) {newEndVNode = oldChildren[--newEndIdx]} else if (isSameNode(oldStartVNode, newStartVNode)) { // 头-头patchVNode(oldStartVNode, newStartVNode)// 更新指针oldStartVNode = oldChildren[++oldStartIdx]newStartVNode = newChildren[++newStartIdx]} else if (isSameNode(oldStartVNode, newEndVNode)) { // 头-尾patchVNode(oldStartVNode, newEndVNode)// 把oldStartVNode节点移动到最后el.insertBefore(oldStartVNode.el, oldEndVNode.el.nextSibling)// 更新指针oldStartVNode = oldChildren[++oldStartIdx]newEndVNode = newChildren[--newEndIdx]} else if (isSameNode(oldEndVNode, newStartVNode)) { // 尾-头patchVNode(oldEndVNode, newStartVNode)// 把oldEndVNode节点移动到oldStartVNode前el.insertBefore(oldEndVNode.el, oldStartVNode.el)// 更新指针oldEndVNode = oldChildren[--oldEndIdx]newStartVNode = newChildren[++newStartIdx]} else if (isSameNode(oldEndVNode, newEndVNode)) { // 尾-尾patchVNode(oldEndVNode, newEndVNode)// 更新指针oldEndVNode = oldChildren[--oldEndIdx]newEndVNode = newChildren[--newEndIdx]} else {let findIndex = findSameNode(oldChildren, newStartVNode)// newStartVNode在旧列表里不存在,那么是新节点,创建插入if (findIndex === -1) {el.insertBefore(createEl(newStartVNode), oldStartVNode.el)} else { // 在旧列表里存在,那么进行patch,并且移动到oldStartVNode前let oldVNode = oldChildren[findIndex]patchVNode(oldVNode, newStartVNode)el.insertBefore(oldVNode.el, oldStartVNode.el)// 将该VNode置为空oldChildren[findIndex] = nullnewStartVNode = newChildren[++newStartIdx]// 旧列表里存在新列表里没有的节点,需要删除if (oldStartIdx <= oldEndIdx) {for (let i = oldStartIdx; i <= oldEndIdx; i++) {removeEvent(oldChildren[i])oldChildren[i] && el.removeChild(oldChildren[i].el)} else if (newStartIdx <= newEndIdx) {let before = newChildren[newEndIdx + 1] ? newChildren[newEndIdx + 1].el : nullfor (let i = newStartIdx; i <= newEndIdx; i++) {el.insertBefore(createEl(newChildren[i]), before)

该函数具体的实现步骤可以参考之前的文章,本文就不再赘述。

我们想让这个diff过程动起来,首先要找到动画的对象都有哪些,从函数的参数开始看,首先oldChildren和 newChildren两个VNode列表是必不可少的,可以通过两个水平的列表表示,然后是四个指针,这是双端diff算法的关键,我们通过四个箭头来表示,指向当前所比较的节点,然后就开启循环了,循环中新旧VNode列表其实基本上是没啥变化的,我们实际操作的是VNode对应的真实DOM元素,包括patch打补丁、移动、删除、新增等等操作,所以我们再来个水平的列表表示当前的真实DOM列表,最开始肯定是和旧的VNode列表是对应的,通过diff算法一步步会变成和新的VNode列表对应。

再来回顾一下创建VNode对象的h函数:

export const h = (tag, data = {}, children) => {let text = ''let ellet key// 文本节点if (typeof children === 'string' || typeof children === 'number') {text = childrenchildren = undefined} else if (!Array.isArray(children)) {children = undefinedif (data && data.key) {key = data.keyreturn {tag, // 元素标签children, // 子元素text, // 文本节点的文本el, // 真实domkey,data

我们输入的VNode列表数据会使用h函数来创建成VNode对象,所以可以输入的最简单的结构如下:

tag: 'div',children: '文本节点的内容',data: {key: 'a'

输入的新旧VNode列表数据会保存在store中,可以通过如下方式获取到:

// 输入的旧VNode列表store.oldVNode// 输入的新VNode列表store.newVNode

接下来定义相关的变量:

// 指针列表const oldPointerList = ref([])const newPointerList = ref([])// 真实DOM节点列表const actNodeList = ref([])// 新旧节点列表const oldVNodeList = ref([])const newVNodeList = ref([])// 提示信息const info = ref('')

指针的移动动画可以使用css的transition属性来实现,只要修改指针元素的left值即可,真实DOM列表的移动动画可以使用Vue的列表过渡组件TransitionGroup来轻松实现,模板如下:

 

{{ item.name }}

{{ item.value }}

旧的VNode列表

{{ item ? item.children : '空' }}

新的VNode列表

{{ item.children }}

{{ info }}

{{ item.value }}

{{ item.name }}

真实DOM列表

{{ item.children }}

双端diff算法过程中是不会修改新的VNode列表的,但是旧的VNode列表是有可能被修改的,也就是当首尾比较没有找到可以复用的节点,但是通过直接在旧的VNode列表中搜索找到了,那么会移动该VNode对应的真实DOM,移动后该VNode其实就相当于已经被处理过了,但是该VNode的位置又是在当前指针的中间,不能直接被删除,所以只好置为空null,所以可以看到模板中有处理这种情况。

另外我们还创建了一个info元素用来展示提示的文字信息,作为动画的描述。

但是这样还是不够的,因为每个旧的VNode是有对应的真实DOM元素的,但是我们输入的只是一个普通的json数据,所以模板还需要新增一个列表,作为旧的VNode列表的关联节点,这个列表只要提供节点引用即可,不需要可见,所以把它的display设为none:

// 根据输入的旧VNode列表创建元素const _oldVNodeList = computed(() => {return JSON.parse(store.oldVNode)// 引用DOM元素const oldNode = ref(null)const oldNodeList = ref([])

{{ item.children }}

然后当我们点击启动按钮,就可以给我们的三个列表变量赋值了,并使用h函数创建新旧VNode对象,然后传递给打补丁的patch函数就可以开始进行比较更新实际的DOM元素了:

const start = () => {nextTick(() => {// 表示当前真实的DOM列表actNodeList.value = JSON.parse(store.oldVNode)// 表示旧的VNode列表oldVNodeList.value = JSON.parse(store.oldVNode)// 表示新的VNode列表newVNodeList.value = JSON.parse(store.newVNode)nextTick(() => {let oldVNode = h('div',{ key: 1 },JSON.parse(store.oldVNode).map((item, index) => {// 创建VNode对象let vnode = h(item.tag, item.data, item.children)// 关联真实的DOM元素vnode.el = oldNodeList.value[index]return vnode// 列表的父节点也需要关联真实的DOM元素oldVNode.el = oldNode.valuelet newVNode = h('div',{ key: 1 },JSON.parse(store.newVNode).map(item => {return h(item.tag, item.data, item.children)// 调用patch函数进行打补丁patch(oldVNode, newVNode)

可以看到我们输入的新旧VNode列表是作为一个节点的子节点的,这是因为只有当比较的两个节点都存在非文本节点的子节点时才需要使用diff算法来高效的更新他们的子节点,当patch函数运行完后你可以打开控制台查看隐藏的DOM列表,会发现是和新的VNode列表保持一致的,那么你可能要问,为什么不直接用这个列表来作为真实DOM列表呢,还要自己额外创建一个actNodeList列表,其实是可以,但是diff算法过程中是使用insertBefore等方法来移动真实DOM节点的,所以不好加过渡动画,只会看到节点瞬间换位置,不符合我们的动画需求。

到这里效果如下:


 

接下来我们先把指针搞出来,我们创建一个处理函数对象,这个对象上会挂载一些方法,用于在diff算法过程中调用,在函数中更新相应的变量。

const handles = {// 更新指针updatePointers(oldStartIdx, oldEndIdx, newStartIdx, newEndIdx) {oldPointerList.value = [name: 'oldStartIdx',value: oldStartIdx},name: 'oldEndIdx',value: oldEndIdxnewPointerList.value = [name: 'newStartIdx',value: newStartIdx},name: 'newEndIdx',value: newEndIdx},

然后我们就可以在diff函数中通过handles.updatePointers()更新指针了:

const diff = (el, oldChildren, newChildren) => {// 指针handles.updatePointers(oldStartIdx, oldEndIdx, newStartIdx, newEndIdx)

这样指针就出来了:


 

然后在while循环中会不断改变这四个指针,所以在循环中也需要更新:

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {handles.updatePointers(oldStartIdx, oldEndIdx, newStartIdx, newEndIdx)

但是这样显然是不行的,为啥呢,因为循环也就一瞬间就结束了,而我们希望每次都能停留一段时间,很简单,我们写个等待函数:

const wait = t => {return new Promise(resolve => {setTimeout(resolve()},t || 3000

然后我们使用async/await语法,就可以轻松在循环中实现等待了:

const diff = async (el, oldChildren, newChildren) => {while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {handles.updatePointers(oldStartIdx, oldEndIdx, newStartIdx, newEndIdx)await wait()


 

接下来我们新增两个变量,来突出表示当前正在比较的两个VNode:

// 当前比较中的节点索引const currentCompareOldNodeIndex = ref(-1)const currentCompareNewNodeIndex = ref(-1)const handles = {// 更新当前比较节点updateCompareNodes(a, b) {currentCompareOldNodeIndex.value = acurrentCompareNewNodeIndex.value = b

 

{{ item ? item.children : '空' }}

 

 

{{ item.children }}

 

给当前比较中的节点添加一个类名,用来突出显示,接下来还是一样,需要在diff函数中调用该函数,但是,该怎么加呢:

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {if // ...} else if (isSameNode(oldStartVNode, newStartVNode)) {oldStartVNode = oldChildren[++oldStartIdx]newStartVNode = newChildren[++newStartIdx]} else if (isSameNode(oldStartVNode, newEndVNode)) {oldStartVNode = oldChildren[++oldStartIdx]newEndVNode = newChildren[--newEndIdx]} else if (isSameNode(oldEndVNode, newStartVNode)) {oldEndVNode = oldChildren[--oldEndIdx]newStartVNode = newChildren[++newStartIdx]} else if (isSameNode(oldEndVNode, newEndVNode)) {oldEndVNode = oldChildren[--oldEndIdx]newEndVNode = newChildren[--newEndIdx]} else {newStartVNode = newChildren[++newStartIdx]

我们想表现出头尾比较的过程,其实就在这些if条件中,也就是要在每个if条件中停留一段时间,那么可以直接这样吗:

const isSameNode = async () => {handles.updateCompareNodes()await wait()if (await isSameNode(oldStartVNode, newStartVNode))

很遗憾,我尝试了不行,那么只能改写成其他形式了:

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {let stop = falselet _isSameNode = falseif (oldStartVNode === null) {callbacks.updateInfo('')oldStartVNode = oldChildren[++oldStartIdx]stop = trueif (!stop) {callbacks.updateInfo('头-头比较')callbacks.updateCompareNodes(oldStartIdx, newStartIdx)_isSameNode = isSameNode(oldStartVNode, newStartVNode)if (_isSameNode) {callbacks.updateInfo('key值相同,可以复用,进行patch打补丁操作。新旧节点位置相同,不需要移动对应的真实DOM节点'await wait()if (!stop && _isSameNode) {oldStartVNode = oldChildren[++oldStartIdx]newStartVNode = newChildren[++newStartIdx]stop = true

我们使用一个变量来表示是否进入到了某个分支,然后把检查节点是否能复用的结果也保存到一个变量上,这样就可以通过不断检查这两个变量的值来判断是否需要进入到后续的比较分支中,这样比较的逻辑就不在if条件中了,就可以使用await了,同时我们还使用updateInfo增加了提示语:

const handles = {// 更新提示信息updateInfo(tip) {info.value = tip


 

接下来看一下节点的移动操作,当头(oldStartIdx对应的oldStartVNode节点)尾(newEndIdx对应的newEndVNode节点)比较发现可以复用时,在打完补丁后需要将oldStartVNode对应的真实DOM元素移动到oldEndVNode对应的真实DOM元素的位置,也就是插入到oldEndVNode对应的真实DOM的后面一个节点的前面:

if (!stop && _isSameNode) {// 头-尾patchVNode(oldStartVNode, newEndVNode)// 把oldStartVNode节点移动到最后el.insertBefore(oldStartVNode.el, oldEndVNode.el.nextSibling)// 更新指针oldStartVNode = oldChildren[++oldStartIdx]newEndVNode = newChildren[--newEndIdx]stop = true

那么我们可以在insertBefore方法移动完真实的DOM元素后紧接着调用一下我们模拟列表的移动节点的方法:

if (!stop && _isSameNode) {el.insertBefore(oldStartVNode.el, oldEndVNode.el.nextSibling)callbacks.moveNode(oldStartIdx, oldEndIdx + 1)

我们要操作的实际上是代表真实DOM节点的actNodeList列表,那么关键是要找到具体是哪个,首先头尾的四个节点指针它们表示的是在新旧VNode列表中的位置,所以我们可以根据oldStartIdx和oldEndIdx获取到oldVNodeList中对应位置的VNode,然后通过key值在actNodeList列表中找到对应的节点,进行移动、删除、插入等操作:

const handles = {// 移动节点moveNode(oldIndex, newIndex) {let oldVNode = oldVNodeList.value[oldIndex]let newVNode = oldVNodeList.value[newIndex]let fromIndex = findIndex(oldVNode)let toIndex = findIndex(newVNode)actNodeList.value[fromIndex] = '#'actNodeList.value.splice(toIndex, 0, oldVNode)actNodeList.value = actNodeList.value.filter(item => {return item !== '#'const findIndex = (vnode) => {return !vnode: actNodeList.value.findIndex(item => {return item && item.data.key === vnode.data.key

其他的插入节点和删除节点也是类似的:

插入节点:

const handles = {// 插入节点insertNode(newVNode, index, inNewVNode) {let node = {data: newVNode.data,children: newVNode.textlet targetIndex = 0if (index === -1) {actNodeList.value.push(node)} else {if (inNewVNode) {let vNode = newVNodeList.value[index]targetIndex = findIndex(vNode)} else {let vNode = oldVNodeList.value[index]targetIndex = findIndex(vNode)actNodeList.value.splice(targetIndex, 0, node)

删除节点:

const handles = {// 删除节点removeChild(index) {let vNode = oldVNodeList.value[index]let targetIndex = findIndex(vNode)actNodeList.value.splice(targetIndex, 1)

这些方法在diff函数中的执行位置其实就是执行insertBefore、removeChild方法的地方,具体可以本文源码,这里就不在具体介绍了。

另外还可以凸显一下已经结束比较的元素、即将被添加的元素、即将被删除的元素等等,最终效果:


 

时间原因,目前只实现了双端diff算法的效果,后续会增加上快速diff算法的动画过程,有兴趣的可以点个关注哟~

仓库:https://github.com/wanglin2/VNode_visualization。



Tags:算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
对 TikTok 算法的工作原理感到好奇吗?什么是 TikTok 算法?TikTok 算法是一个复杂的系统,旨在为应用主页上的用户内容提供服务 - 为您提供页面 (FYP)。就像Instagram 的探索页面...【详细内容】
2022-11-03  Tags: 算法  点击:(13)  评论:(0)  加入收藏
去年写了一篇文章手写一个虚拟DOM库,彻底让你理解diff算法介绍虚拟DOM的patch过程和diff算法过程,当时使用的是双端diff算法,今年看到了Vue3使用的已经是快速diff算法,所以也想...【详细内容】
2022-10-30  Tags: 算法  点击:(9)  评论:(0)  加入收藏
前言CPU (Central Processing Unit)作为整个冯&middot;诺依曼架构的控制与运算中心,终其一生都在执行没有边界的指令,用无差别的计算支撑起智能时代“算力取之不尽用之不竭”的...【详细内容】
2022-10-28  Tags: 算法  点击:(16)  评论:(0)  加入收藏
什么是散列表散列表又被称为哈希表,包含一个键key、一个值value它们之间的对应关系是一对一,散列表就提供了键key和值value的对应关系,基本结构如下。 键值不会重复所以通过键...【详细内容】
2022-10-25  Tags: 算法  点击:(7)  评论:(0)  加入收藏
算法交易已经存在了一段时间,它不会消失。事实上,它只会越来越受欢迎。随着对快速交易的需求上升,算法交易的使用也在增长。在股票市场上使用算法,使交易者能够以更快的速度进...【详细内容】
2022-10-24  Tags: 算法  点击:(12)  评论:(0)  加入收藏
摘要深度学习在科学计算领域得到了广泛的应用,其算法被解决复杂问题的行业广泛使用。所有的深度学习算法都使用不同类型的神经网络来执行特定的任务。本文为大家带来基本的人...【详细内容】
2022-10-22  Tags: 算法  点击:(7)  评论:(0)  加入收藏
简介前面在密码学入门一文中讲解了各种常见的密码学概念、算法与运用场景,但没有介绍过代码,因此,为作补充,这一篇将会介绍使用Java语言如何实现使用这些算法,并介绍一下使用过程...【详细内容】
2022-10-22  Tags: 算法  点击:(5)  评论:(0)  加入收藏
抖音的发展如今可谓是如日中天,上到明星大咖,下到村口大妈都在玩抖音,不玩不知道,一玩吓一跳,不是流量低迷就是各种违规,发现处处都是门门道道。对于真正想玩抖音的新人来说,肯定会...【详细内容】
2022-10-10  Tags: 算法  点击:(14)  评论:(0)  加入收藏
一、什么是递归?自己调用自己,当业务逻辑符合以下三个条件的时候,就可以考虑使用递归来实现。 一个问题可以分解为多个子问题; 当前问题与其子问题除了数据规模不同外,求解思路...【详细内容】
2022-10-07  Tags: 算法  点击:(21)  评论:(0)  加入收藏
相信大家都知道,在短视频中,抖音和tiktok流量最大.使用用户最多的平台之一就是所谓的国内抖音,国外抖音。tiktok,虽然这两个平台的实现方式几乎是一样的,但算法是人们比较纠结,不...【详细内容】
2022-10-06  Tags: 算法  点击:(12)  评论:(0)  加入收藏
▌简易百科推荐
去年写了一篇文章手写一个虚拟DOM库,彻底让你理解diff算法介绍虚拟DOM的patch过程和diff算法过程,当时使用的是双端diff算法,今年看到了Vue3使用的已经是快速diff算法,所以也想...【详细内容】
2022-10-30  街角小林  今日头条  Tags:算法   点击:(9)  评论:(0)  加入收藏
前言CPU (Central Processing Unit)作为整个冯&middot;诺依曼架构的控制与运算中心,终其一生都在执行没有边界的指令,用无差别的计算支撑起智能时代“算力取之不尽用之不竭”的...【详细内容】
2022-10-28  码洞  CSDN  Tags:算法   点击:(16)  评论:(0)  加入收藏
什么是散列表散列表又被称为哈希表,包含一个键key、一个值value它们之间的对应关系是一对一,散列表就提供了键key和值value的对应关系,基本结构如下。 键值不会重复所以通过键...【详细内容】
2022-10-25  Java面试365  今日头条  Tags:散列表   点击:(7)  评论:(0)  加入收藏
摘要深度学习在科学计算领域得到了广泛的应用,其算法被解决复杂问题的行业广泛使用。所有的深度学习算法都使用不同类型的神经网络来执行特定的任务。本文为大家带来基本的人...【详细内容】
2022-10-22  BigQuant  今日头条  Tags:算法   点击:(7)  评论:(0)  加入收藏
作者:小傅哥 博客:https://bugstack.cn沉淀、分享、成长,让自己和他人都能有所收获!一、前言:挂在树上!不知道你经历过HashMap的夺命连环问!为啥,面试官那么喜欢让你聊聊 HashMap?因...【详细内容】
2022-10-10  小傅哥    Tags:红黑树   点击:(20)  评论:(0)  加入收藏
前言在头条创作了一个月左右的时间,收获了50+粉丝,很是开心,我会把数据结构与算法的文章更新到底,第一次看我文章的同仁如果觉得不错的话就关注一下我哦,你的支持就是我创作的动...【详细内容】
2022-10-10  掂掂三生有幸  今日头条  Tags:数据结构   点击:(13)  评论:(0)  加入收藏
一:链表是什么 1、链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,有一系列结点(地址)组成,结点可动态的生成。 2、结点包括两个部...【详细内容】
2022-10-07  legendarykk  CSDN  Tags:链表   点击:(26)  评论:(0)  加入收藏
一、什么是递归?自己调用自己,当业务逻辑符合以下三个条件的时候,就可以考虑使用递归来实现。 一个问题可以分解为多个子问题; 当前问题与其子问题除了数据规模不同外,求解思路...【详细内容】
2022-10-07  掂掂三生有幸    Tags:递归算法   点击:(21)  评论:(0)  加入收藏
✨最近有一些粉丝问了我个问题,我平时是怎样学习一门新的技术的,文章开始之前我先来分享一下我的制胜法宝。✨博主学习方法“三刷”官方文档或源码是我高效学习一门新的技能的...【详细内容】
2022-10-04  掂掂三生有幸  今日头条  Tags:链表   点击:(15)  评论:(0)  加入收藏
最经典最常用的排序算法有:冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序和桶排序。这些排序算法可以按照时间复杂度分为三类: O(n^2)&mdash;&mdash...【详细内容】
2022-10-01  掂掂三生有幸  今日头条  Tags:排序算法   点击:(23)  评论:(0)  加入收藏
站内最新
站内热门
站内头条