一. Tree Diff
樹的 diff 是個相對複雜的問題，先考慮一個簡單場景：
A A'
/ \ ? / | \
B C -> G B C
/ \ | | |
D E F D E
diff(treeA, treeA') 結果應該是：
1.insert G before B
2.move E to F
3.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 4
target 1 4 5 3 7 6
remove 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 的影響，有額外的空間開銷，想辦法去掉這部分
優化空間消耗
去掉模擬位置的操作，直接計算 index changes：
// 1.把模拟位置的操作改用记录index change代替，先遍历新的，再遍历旧的
var diff = function(oldList, newList) {
var changes = [];
// 计算change对oldList未比较元素index的影响，是个区间
// 因为移动我前面的元素到更前面，并不影响我的index
// move时，只影响<=lastIndex的index
// 用<=index: delta表示
var maxLength = Math.max(oldList.length, newList.length);
var oldIndexChanges = new Array(maxLength).fill(0);
// 修正前的index
var _index;
// 遍历新的，找出 增/移
newList.forEach(function(item, i) {
var index = oldList.indexOf(item);
if (index === -1) {
// 增
changes.push({
type: 'insert',
index: i,
item: item
});
// insert影响oldList中后面所有元素的index
oldIndexChanges[maxLength - 1]++;
}
else {
_index = index;
// 修正old index
// 从index数到头，求sum delta
index += oldIndexChanges.reduce(function(acc, delta, idx) {
if (idx >= index)
return acc + delta;
else
return acc;
});
// 移
if (index !== i) {
var step = {
type: 'move',
from: index,
to: i
};
changes.push(step);
if (index > i) {
// move影响oldList中<=from的元素
oldIndexChanges[_index]++;
}
else {
// from 不可能小于 to
// 因为是从前往后扫过来的，[0, to-1]位置确定，不会从前面取元素
console.error('impossible');
}
}
}
});
// 遍历旧的，找出 删
// 计算总delta
// 经过insert和move之后，将被删除的元素一定在最后面，受所有index change影响
var indexDelta = oldIndexChanges.reduce(function(acc, delta) {
return acc + delta;
});
oldList.forEach(function(item, i) {
if (newList.indexOf(item) === -1) {
// 修正old index
i += indexDelta;
changes.push({
type: 'remove',
index: i
});
}
});
return changes;
};
// 2.模拟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 4
target 1 4 5 3 7 6
move 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
與我們的思路類似，也是先遍歷新的，再遍歷舊的：
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 < 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 4
target 1 4 5 3 7 6
insert 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
遇到 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
參考資料
-
reactjs 原始碼分析-下篇（更新機制實現原理）：非常漂亮的原始碼分析
暫無評論，快來發表你的看法吧