廢話不多說，為了記錄大前端的發(fā)展，研讀React的內(nèi)在，寫下記錄：
傳統(tǒng) diff 算法
計算一棵樹形結(jié)構(gòu)轉(zhuǎn)換成另一棵樹形結(jié)構(gòu)的最少操作，是一個復雜且值得研究的問題。傳統(tǒng) diff 算法通過循環(huán)遞歸對節(jié)點進行依次對比，效率低下，算法復雜度達到 O(n^3)，其中 n 是樹中節(jié)點的總數(shù)。O(n^3) 到底有多可怕，這意味著如果要展示1000個節(jié)點，就要依次執(zhí)行上十億次的比較。這種指數(shù)型的性能消耗對于前端渲染場景來說代價太高了！現(xiàn)今的 CPU 每秒鐘能執(zhí)行大約30億條指令，即便是最高效的實現(xiàn)，也不可能在一秒內(nèi)計算出差異情況。
因此，如果 React 只是單純的引入 diff 算法而沒有任何的優(yōu)化改進，那么其效率是遠遠無法滿足前端渲染所要求的性能。
通過下面的 demo 可以清晰的描述傳統(tǒng) diff 算法的實現(xiàn)過程。
var result = [];
var diff = function (beforeDom, afterDom) {
// 獲取較大節(jié)點樹的長度
var count = Math.max(beforeDom.children.length, afterDom.children.length);
//循環(huán)遍歷
for (var i=0; i<count; i++) {
var beforeTag = beforeDom.children[i];
var afterTag = afterDom.children[i];
// 添加 afterTag 節(jié)點
if (beforeTag === undefined) {
//beforeTag 不存在
//{type: type, elment: elment}
result.push({type: 'add', element: afterTag});
//刪除 beforeTag 節(jié)點
} else if (afterTag === undefined) {
result.push({type: 'remove', element: beforeTag});
//節(jié)點名改變時，刪除 beforeTag 節(jié)點，添加 afterTag 節(jié)點
} else if (beforeTag.tagName !== afterTag.tagName) {
result.push({type: 'remove', element: beforeTag});
result.push({type: 'add', element: afterTag});
// 節(jié)點不變而內(nèi)容改變時，改變節(jié)點
} else if (beforeTag.innerHTML !== afterTag.innerHTML) {
//如果之前DomTag的子元素個數(shù)為0
if (beforeTag.children.length === 0) {
result.push({type: 'changed', beforeElement: beforeTag, afterElement: afterTag, html: afterTag.innerHTML});
} else {
// 遞歸比較
diff(beforeTag, afterTag)
}
}
}
return result;
}
