React List Diff
一.Tree Diff
树的diff是个相对复杂的问题，先考虑一个简单场景：
A A' / \ ? / | \ B C -> G B C / \ | | |D E F D Ediff(treeA, treeA')结果应该是：
1.insert G before B2.move E to F3.remove F对treeA做以上3步，就能得到treeA'，树的规模较小时，一眼就能看出来，回想下是怎么做到的：
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
要直接比较树形结构的话，无从下手（肉眼很容易比较形状结构差异，但计算机不擅长这个），例如：
Page Header div img p List Item1 img p button Item2...diff(Page, newPage)似乎很难直接得到结果，那么想办法缩小问题规模，立竿见影的好办法就是递归：
1.每个节点检查自己是否需要更新2.需要的话diff直接孩子，找出 增 删 移 改3.对需要 改 的递归向下检查，直到叶子这样，树的diff被拆解成了list diff，实际需要实现的只是list diff部分，问题变得很明朗了
四.List Diff
考虑两个一维整数数组：
var oldList = [1, 2, 3, 7, 4];var newList = [1, 4, 5, 3, 7, 6];怎样通过diff找出增/删/移？
1.遍历旧的，找出 删2.遍历新的，找出 增 移简单方案
先不考虑性能和复杂度，尝试实现一个最简单粗暴的list diff：
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：
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); });};执行得到操作步骤：
source 1 2 3 7 4target 1 4 5 3 7 6remove 2 1 3 7 4move 4 to 3 1 4 3 7insert 5 before 3 1 4 5 3 7insert 6 before undefined 1 4 5 3 7 6偷懒操作_oldList镜像来模拟位置，避免计算增/删/移对index的影响，有额外的空间开销，想办法去掉这部分
优化空间消耗
去掉模拟位置的东西，直接计算changes：
// 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; //... } });};执行得到操作步骤：
source 1 2 3 7 4target 1 4 5 3 7 6move 4 to 2 1 4 2 3 7insert 5 before 2 1 4 5 2 3 7move 3 to 2 1 4 5 3 2 7move 7 to 2 1 4 5 3 7 2insert 6 before 2 1 4 5 3 7 6 2remove 2 1 4 5 3 7 6操作步骤多了2步，因为先做了移，后做的删（后做删的话，做增移时不用考虑删引起的index变动），其中相对要被删除的2做的两步move没有意义，要想办法规避掉，这里不再展开，直接看React的原版实现
五.React List Diff
与我们的思路类似，也是先遍历新的，再遍历旧的：
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：
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);};执行得到操作步骤：
source 1 2 3 7 4target 1 4 5 3 7 6insert 5 after 4 1 2 3 7 4 5move 3 to pos after 5 1 2 7 4 5 3move 7 to pos after 3 1 2 4 5 3 7insert 6 after 7 1 2 4 5 3 7 6remove 2 1 4 5 3 7 6遇到1和4都不动，因为原相对顺序正确，遇到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
参考资料
Reconciliation – React
reactjs源码分析-下篇（更新机制实现原理）：非常漂亮的源码分析
更多相关文章
- 博客网站显示框相对浏览器固定位置显示
- jQuery遍历祖先元素：parentsUntil
- jQuery在点击按钮上迭代/循环遍历数据表
- 更改粘性标题航点或偏移的位置。
- 在某个点停止固定位置滚动?
- jQuery遍历----------(遍历、祖先、后代、同胞、过滤)
- jQuery遍历Table tr td td中包含标签
- jquery的css位置positon
- 是否有更快的方法来遍历HTMLDocument中的每一个元素呢？