前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >React List Diff

React List Diff

作者头像
ayqy贾杰
发布2019-06-12 15:21:02
7080
发布2019-06-12 15:21:02
举报
文章被收录于专栏:黯羽轻扬

一.Tree Diff

树的diff是个相对复杂的问题,先考虑一个简单场景:

代码语言:javascript
复制
    A           A'
  / \   ?    / | \
 B   C  ->  G  B   C
/ \  |         |   |
D   E F         D   E

diff(treeA, treeA')结果应该是:

代码语言:javascript
复制
1.insert G before B
2.move   E to     F
3.remove F

treeA做以上3步,就能得到treeA',树的规模较小时,一眼就能看出来,回想下是怎么做到的:

代码语言:javascript
复制
1.自顶向下观察,完全不一样就不用找了
2.对比当前层节点,找出 增(新的有旧的没有)、删(旧的有新的没有)
3.向下看子树结构是否相似,判断是不是 移(把原有节点移动位置)

如果要计算机来做的话,好找,的判定就比较复杂了,首先要把树的相似程度量化(比如加权编辑距离),并确定相似度为多少时,删+增划算(操作步骤更少)

P.S.对Tree Diff算法感兴趣的话,可以参考Matching, diffing and merging XML,文章比较老(08年),但挺有意思

二.React假设

React内部维护的虚拟DOM树也面临如何diff的问题,DOM树频繁更新(频繁交互的话),过于复杂的tree diff方案会带来性能困扰,考虑DOM操作场景的特点:

  • 局部小改动多,大片的改动少(性能考虑,用显示隐藏来规避)
  • 跨层级的移动少,同层节点移动多(比如表格排序)

如果大片改动多的话,diff基本上是没有意义的,纯粹的性能损耗。如果跨层级移动多的话,精确的move判定就很必要,对算法要求就很高。DOM操作场景恰好不需要太高要求,据此提出了几点假设

1.Two elements of different types will produce different trees. 2.The developer can hint at which child elements may be stable across different renders with a key prop.

也就是说:

  • 假设不同类型的元素对应不同子树(不考虑“向下看子树结构是否相似”,的判断就没难度了
  • 前后结构都会带有唯一的key,作为diff依据,假定同key表示同元素(降低比较成本)

另外,保险起见,React还提供了shouldComponentUpdate钩子,允许人工干预diff过程,避免误判

三.虚拟DOM树 Diff与List Diff

要直接比较树形结构的话,无从下手(肉眼很容易比较形状结构差异,但计算机不擅长这个),例如:

代码语言:javascript
复制
Page
 Header
   div
     img
     p
 List
   Item1
     img
     p
     button
   Item2...

diff(Page, newPage)似乎很难直接得到结果,那么想办法缩小问题规模,立竿见影的好办法就是递归

代码语言:javascript
复制
1.每个节点检查自己是否需要更新
2.需要的话diff直接孩子,找出 增 删 移 改
3.对需要 改 的递归向下检查,直到叶子

这样,树的diff被拆解成了list diff,实际需要实现的只是list diff部分,问题变得很明朗了

四.List Diff

考虑两个一维整数数组:

代码语言:javascript
复制
var oldList = [1, 2, 3, 7, 4];
var newList = [1, 4, 5, 3, 7, 6];

怎样通过diff找出增/删/移

代码语言:javascript
复制
1.遍历旧的,找出 删
2.遍历新的,找出 增 移

简单方案

先不考虑性能和复杂度,尝试实现一个最简单粗暴list diff

代码语言:javascript
复制
var diff = function(oldList, newList) {
   var changes = [];
   // 镜像,模拟位置
   var _oldList = oldList.slice();
   // 遍历旧的,找出 删
   oldList.forEach(function(item, i) {
       if (newList.indexOf(item) === -1) {
           changes.push({
               type: 'remove',
               index: i
           });
           _oldList.splice(i, 1);
       }
   });   // 遍历新的,找出 增/移
   newList.forEach(function(item, i) {
       var index = _oldList.indexOf(item);
       if (index === -1) {
           // 增
           changes.push({
               type: 'insert',
               index: i,
               item: item
           });
           _oldList.splice(i, 0, item);
       }
       else {
           // 移
           if (index !== i) {
               var step = {
                   type: 'move',
                   from: index,
                   to: i
               };
               changes.push(step);
               move(_oldList, step.from, step.to);
           }
       }
   });   return changes;
};
var move = function(list, from, to) {
   var item = list.splice(from, 1);
   if (from > to)
       list.splice(to, 0, item[0]);
   else
       list.splice(to - 1, 0, item[0]);
};

模拟patch

代码语言:javascript
复制
var showSteps = function(changes) {
   changes.forEach(function(change) {
       switch (change.type) {
           case 'insert':
               console.log('insert ' + change.item + ' before ' + oldList[change.index]);
               oldList.splice(change.index, 0, change.item);
               break;
           case 'remove':
               console.log('remove ' + oldList[change.index]);
               oldList.splice(change.index, 1);
               break;
           case 'check':
               console.log('check ' + oldList[change.index] + ' for update');
               break;
           case 'move':
               console.log('move ' + oldList[change.from] + ' to ' + oldList[change.to]);
               move(oldList, change.from, change.to);
               break;
           default:
               cosole.error('not here');
               break;
       }
       console.log(oldList);
   });
};

执行得到操作步骤:

代码语言:javascript
复制
source  1 2 3 7 4
target  1 4 5 3 7 6remove 2
 1 3 7 4
move 4 to 3
 1 4 3 7
insert 5 before 3
 1 4 5 3 7
insert 6 before undefined
 1 4 5 3 7 6

偷懒操作_oldList镜像来模拟位置,避免计算增/删/移index的影响,有额外的空间开销,想办法去掉这部分

优化空间消耗

去掉模拟位置的东西,直接计算changes

代码语言:javascript
复制
// 1.直接交换遍历新旧的部分,先遍历新的,其它不变
var diff = function(oldList, newList) {
   var changes = [];   // 遍历新的,找出 增/移...
   // 遍历旧的,找出 删...   return changes;
};// 2.做patch时需要查原位置
var showSteps = function(changes) {
   // 留一份,针对 移 和 删 用来查以前的位置
   var _oldList = oldList.slice();
   // 针对移 和 删,模拟DOM操作需要知道patching中,旧元素的当前index
   // 实际做DOM patch的时候不需要,因为找到元素后DOM API不需要index就能 移 删
   var patchingIndex = -1;
   changes.forEach(function(change) {
       switch (change.type) {
           //...
           case 'remove':
               console.log('remove ' + _oldList[change.index]);
               patchingIndex = oldList.indexOf(_oldList[change.index]);
               oldList.splice(patchingIndex, 1);
               break;
           case 'move':
               console.log('move ' + _oldList[change.from] + ' to ' + oldList[change.to]);
               patchingIndex = oldList.indexOf(_oldList[change.from]);
               move(oldList, patchingIndex, change.to);
               break;
           //...
       }
   });
};

执行得到操作步骤:

代码语言:javascript
复制
source  1 2 3 7 4
target  1 4 5 3 7 6move 4 to 2
 1 4 2 3 7
insert 5 before 2
 1 4 5 2 3 7
move 3 to 2
 1 4 5 3 2 7
move 7 to 2
 1 4 5 3 7 2
insert 6 before 2
 1 4 5 3 7 6 2
remove 2
 1 4 5 3 7 6

操作步骤多了2步,因为先做了,后做的(后做的话,做增移时不用考虑引起的index变动),其中相对要被删除的2做的两步move没有意义,要想办法规避掉,这里不再展开,直接看React的原版实现

五.React List Diff

与我们的思路类似,也是先遍历新的,再遍历旧的:

代码语言:javascript
复制
var diff = function(oldList, newList) {
   var changes = [];
   // 访问过的之前children表最大的index
   var lastIndex = 0;
   // 上一个放好的节点,用来做 增/移
   var lastPlacedNode = null;   // 遍历新的,找出 增/移
   newList.forEach(function(item, i) {
       var index = oldList.indexOf(item);
       if (index === -1) {
           // 增
           changes.push({
               type: 'insert',
               item: item,
               afterNode: lastPlacedNode
           });
       }
       else {
           // lastIndex滤掉相对位置没变的 移
           if (index !== i && index < lastIndex) {
               // 移
               var step = {
                   type: 'move',
                   item: item,
                   afterNode: lastPlacedNode
               };
               changes.push(step);
           }
           lastIndex = Math.max(index, lastIndex);
       }
       lastPlacedNode = item;
   });   // 遍历旧的,找出 删
   oldList.forEach(function(item, i) {
       if (newList.indexOf(item) === -1) {
           changes.push({
               type: 'remove',
               index: i
           });
       }
   });   return changes;
};

其中很机智的一个优化lastIndex,记录摸过的源list最右元素的index,直到原相对位置无法满足需要了(不不行了),才做,这样来最大限度地利用原相对位置,避免不必要的移动

模拟patch

代码语言:javascript
复制
var showSteps = function(changes) {
   // 留一份,针对 移 用来查以前的位置
   var _oldList = oldList.slice();
   // 针对 增 移 和 删,模拟DOM操作需要知道patching中,旧元素的当前index
   // 实际做DOM patch的时候不需要,因为找到元素后DOM API不需要index就能 增 移 删
   var patchingIndex = -1;
   changes.forEach(function(change) {
       switch (change.type) {
           case 'insert':
               console.log('insert ' + change.item + ' after ' + change.afterNode);
               patchingIndex = oldList.indexOf(change.afterNode);
               insertAfter(oldList, change.item, patchingIndex);
               break;
           case 'remove':
               console.log('remove ' + _oldList[change.index]);
               patchingIndex = oldList.indexOf(_oldList[change.index]);
               oldList.splice(patchingIndex, 1);
               break;
           case 'move':
               console.log('move ' + change.item + ' to pos after ' + change.afterNode);
               patchingIndex = oldList.indexOf(change.afterNode);
               move(oldList, oldList.indexOf(change.item), patchingIndex);
               break;
           default:
               cosole.error('not here');
               break;
       }
       console.log(oldList);
   });
};
var move = function(list, from, to) {
   var item = list.splice(from, 1);
   if (from > to)
       list.splice(to + 1, 0, item[0]);
   else
       list.splice(to, 0, item[0]);
};
var insertAfter = function(list, item, index) {
   list.splice(index + 1, 0, item);
};

执行得到操作步骤:

代码语言:javascript
复制
source  1 2 3 7 4
target  1 4 5 3 7 6insert 5 after 4
 1 2 3 7 4 5
move 3 to pos after 5
 1 2 7 4 5 3
move 7 to pos after 3
 1 2 4 5 3 7
insert 6 after 7
 1 2 4 5 3 7 6
remove 2
 1 4 5 3 7 6

遇到14都不动,因为原相对顺序正确,遇到3时,不移不行了(无法继续保持原相对位置了),才

就本例来看,React的实现并不是最高效的,我们最初写的简单版本(先增移)只需要4步就能完成

六.在线Demo

示例场景下的React实现及文中各例diff方法:http://www.ayqy.net/temp/react/demo/list-diff.html

打开浏览器Console,点“更新List”,看diff结果

P.S.React版本为15.5.4

参考资料

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-05-14,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 前端向后 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一.Tree Diff
  • 二.React假设
  • 三.虚拟DOM树 Diff与List Diff
  • 四.List Diff
    • 简单方案
      • 优化空间消耗
      • 五.React List Diff
      • 六.在线Demo
        • 参考资料
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档