virtual-dom内对children进行比较的list-diff的详解

WelliJhon 发布于2019-08-23 12:32 / 2679人阅读

摘要：不清楚的可以查看此文章的源代码前言在或者内，每一个都有一个唯一来标识，通常是框架自动处理，但是在循环内必须由开发者指定。所以以下解读我就是用这个来代表内的对象。

不清楚virtual-dom的可以查看此文章

list-diff的源代码

前言：

在vue或者react内，每一个VNode都有一个唯一key来标识，通常是框架自动处理，但是在循环内必须由开发者指定。所以以下解读我就是用这个key来代表list内的对象。

我们并不需要真的达到最小的操作，我们只需要优化一些比较常见的移动情况，牺牲一定DOM操作，让算法时间复杂度达到线性的（O(max(M, N))

方法入口

let diff = (oldList, newList) => {
    let moves = [];
    // 逻辑处理
    return moves;
}

由上可以看出，diff函数返回的是将旧数组转换成新数组的步骤
下面我会详细说明中间的逻辑处理步骤

我们传入两个数组

oldList = [ A, B, C, D];
newList = [ E ,C, D, B];

第一步，两个数组取交集，找到需要删除的item

var simulateList = [];
oldList.forEach((item, index) => {
    // 此item存在于newList内
    if (newList.indexOf(item) !== -1) {
        simulateList.push(item)
    } else {
        moves.push({
            type: "remove",
            index: index
        })
    }
});

// 程序运行结束，此时simulateList 就是oldList与newList的交集，并且是按oldList的顺序进行排序的
// 此时simulateList的值为[ B, C, D]
// 此时moves的值为[{type:"remove",index:0}],标识将下标为0的item从oldList内删除，即删除A

第二步，同步遍历newList和simulateList

newList = [E,C,D,B];
simulateList= [B,C,D];

// i与j分别是newList与simulateList的下标

// newList E 与 simulateList B 比较，E 不等于 B 且 E 不存在于simulateList中，则insert E 
// 此时i=0;j=0;
moves = [
    {type:"remove",index:0},
    {type:"insert",index:0,item:E}
];
i++;

// newList C 与 simulateList B 比较，C 不等于 B 且 simulateList B 的下一个为 C，则remove B
// i=1;j=0;

moves = [
    {type:"remove",index:0},
    {type:"insert",index:0,item:E},
    {type:"remove",index:1}
]
i++;
j++;


// 4. newList D 与 simulateList D 比较，相等则进入下一步比较
i++;
j++;

// 5. newList B，此时simulateList 已经比较完了，则 insert B
// i=3;j=2;

moves = [
    {type:"remove",index:0},
    {type:"insert",index:0,item:E},
    {type:"remove",index:1},
    {type:"inser", item: B, index: 3}
]

最终返回的数据如上所示，按照这个步骤，可以将oldList转变为newList,通常情况下对于list的改变主要集中在，删除数据，或者新增数据，将list数据全部打乱的情况极少，所以以上算法基本满足我们的需要。

由上可以看出唯一key的重要性，在用vue或者react写list的时候，务必要使用唯一的固定值作为可以，杜绝用数组下标作为key的写法。

第一次写文章，不足之处还请海涵

云服务器 GPU云服务器你的账号无法进行指令的交互详解安装目录的详解小程序的开发如何进行

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/98704.html

React系列 --- virtualdom diff算法实现分析(三)

摘要：所以只针对同层级节点做比较，将复杂度的问题转换成复杂度的问题。 React系列 React系列 --- 简单模拟语法(一)React系列 --- Jsx, 合成事件与Refs(二)React系列 --- virtualdom diff算法实现分析(三)React系列 --- 从Mixin到HOC再到HOOKS(四)React系列 --- createElement, ReactElem...

sunsmell 2019-08-26 10:37 评论0 收藏0
浅析虚拟dom原理并实现

摘要：虚拟原理流程简单概括有三点用模拟树，并渲染这个树比较新老树，得到比较的差异对象把差异对象应用到渲染的树。下面是流程图下面我们用代码一步步去实现一个流程图用模拟树并渲染到页面上其实虚拟，就是用对象结构的一种映射，下面我们一步步实现这个过程。背景大家都知道，在网页中浏览器资源开销最大便是DOM节点了，DOM很慢并且非常庞大，网页性能问题大多数都是有JavaScript修改DOM所引起的...

charles_paul 2019-08-23 12:18 评论0 收藏0
如何实现 virtual-dom

摘要：但是实际开发中，整个文档树中和标签基本不会有太大的改动。在测试中，不难发现其实已经很快了，但是速度会比较慢，所以这里留下了一个待优化的点就是。如何实现 virtual-dom 0. 什么是 vnode 相信大部分前端同学之前早已无数次听过或了解过 vnode（虚拟节点），那么什么是 vnode? vnode 应该是什么样的？如果不使用前端框架，我们可能会写出这样的页面： ...

rickchen 2019-08-23 14:06 评论0 收藏0
如何实现一个虚拟 DOM——virtual-dom 源码分析

摘要：具体代码如下，，下面，我们来简单介绍下这个排序算法检查和中的是否拥有字段，如果没有，直接返回的数组。通过上面这个排序算法，我们可以得到一个新的的数组。概述本文通过对virtual-dom的源码进行阅读和分析，针对Virtual DOM的结构和相关的Diff算法进行讲解，让读者能够对整个数据结构以及相关的Diff算法有一定的了解。 Virtual DOM中Diff算法得到的结果如何映...

qieangel2013 2019-08-26 13:37 评论0 收藏0