react 的virtual Dom是建立在js和dom之间的一个“缓存”,有了virtual Dom,可以在每次更新真实Dom之前通过diff算法,比较前后两棵virtual Dom树的差异,然后只记录需要更改的dom操作,因此大大减少了操作真实dom的开销
两颗树的最小差异比较需要o(n3)
首先virtualDom的本质是JavaScript对象
- 创建virtualDom
function Element(tagName, props, children) {
this.tagName = tagName;
this.props = props || {};
this.children = children || [];
this.key = props ? props.key : void 0;
}定义节点类型、props、子节点
- render
Element.prototype.render = function () {
var el = document.createElement(this.tagName);
var props = this.props;
for (var propsKey in props) {
var propsValue = props[propsKey];
el.setAttribute(propsKey, propsValue);
}
var children = this.children || [];
children.forEach(function (child) {
var childEl = (child instanceof Element)
? child.render() // 如果子节点也是Element对象，递归构建DOM节点
: document.createTextNode(child); // 如果字符串，只构建文本节点
el.appendChild(childEl);
});
return el;
};render返回真实dom 元素,直接挂载到body上面即可
document.body.appendChild(new Element(tagName, props, children));
- diff
react diff的原则是:不考虑跨层级dom操作,并且需要考虑四种情况
- 该节点是text类型节点,且值发生改变,例如“张三”->“李四”
- 该节点类型发生改变,例如<h1> -> <p>
- 该节点props发生改变,例如{name:”张三”}->{name:“李四”}
- 该节点自身没发生变化,但是子节点有增、删、改等操作
初级版diff
function dfsWalk(oldNode, newNode, patches) {
var currentPatch = [];
if (newNode === null || newNode === undefined) {
currentPatch.push({type: REMOVE});
} else if (oldNode === null || oldNode === undefined) {
currentPatch.push({type: CREATE, newNode});
} else if (typeof oldNode === "string" && typeof newNode === "string") { //如果是textNode节点
if (oldNode !== newNode) {
currentPatch.push({type: TEXT, newNode});
}
} else if (oldNode.tagName === newNode.tagName && oldNode.key === newNode.key) { //如果节点名称和key都未发生改变则比较props
var propsPatches = diffProps(oldNode, newNode);
if (propsPatches) {
currentPatch.push({type: PROPS, props: propsPatches});
}
diffChildren(oldNode.children, newNode.children, patches, currentPatch);
} else { //如果名字不同，说明节点发生变化，则记录替换操作
currentPatch.push({type: REPLACE, newNode});
}
patches.push(currentPatch);
}
function diffChildren(oldChildren, newChildren, patches) {
console.log(newChildren);
for (var index = 0; index < Math.max(oldChildren.length, newChildren.length); index++) {
var oldChild = oldChildren[index];
var newChild = newChildren[index];
dfsWalk(oldChild, newChild, patches);
}
}初级版diff的算法效率很高,仅O(max(N,M)),但是缺陷也很严重,dom开销太大,该版本对节点的处理是,对新旧节点进行比较,若旧节点不存在则执行create操作,若新节点不存在,则执行remove操作
如果有一组列表顺序为 [1,2,3,4,5],先将最后一个移动至头部[5,1,2,3,4] ,按照初级diff的比较,因为每次新旧节点都不一样,会执行5次replace操作,但实际上只需要执行一次insert操作即可
进阶版diff
function dfsWalk(oldNode, newNode, index, patches) {
var currentPatch = [];
if (newNode === null) {
} else if (typeof oldNode === 'string' && typeof newNode === 'string') {
if (newNode !== oldNode) {
currentPatch.push({type: TEXT, content: newNode});
}
} else if (
oldNode.tagName === newNode.tagName && oldNode.key === newNode.key
) {
var propsPatches = diffProps(oldNode, newNode);
if (propsPatches) {
currentPatch.push({type: PROPS, props: propsPatches});
}
diffChildren(oldNode.children, newNode.children, index, patches, currentPatch);
} else {
currentPatch.push({type: REPLACE, node: newNode});
}
if (currentPatch.length) {
patches[index] = currentPatch;
}
}
function diffChildren(oldChildren, newChildren, index, patches, currentPatch) {
var diffs = diffLi(oldChildren, newChildren, 'key');
newChildren = diffs.children;
if (diffs.moves.length) {
var reorderPatch = {type: REORDER, moves: diffs.moves};
currentPatch.push(reorderPatch);
}
var leftNode = null;
var currentNodeIndex = index;
oldChildren.forEach(function (child, i) {
var newChild = newChildren[i];
currentNodeIndex = (leftNode && leftNode.count)
? currentNodeIndex + leftNode.count + 1
: currentNodeIndex + 1;
dfsWalk(child, newChild, currentNodeIndex, patches);
leftNode = child;
});
}进阶版diff在做children循环时,只在原children上遍历,以它为参考,在递归时不考虑所有节点插入和卸载的情况(因为当前节点已经作为父节点的子节点参与了移动),当两个节点相同,再单独考虑子节点的移动情况
这里就分成三种diffList了,前两种是牺牲一定的dom开销,这里的实现是只进行remove和insert,去除了replace,这样子时间效率依然是O(max(N,M))
具体实现算法我比较了二者的思路,做了部分优化操作
https://github.com/livoras/list-diff/blob/master/lib/diff.js
和https://zhuanlan.zhihu.com/p/20346379?refer=purerender
第一种的写法有点繁琐,将每次操作过程做了存储,然后调用paches执行更新
第二种直接边记录边更新dom,也是我采用的方案
function T(t1, t2) {
var path = [];
var lastIndex = 0;
//先将不存在的remove
for (var index = 0; index < t1.length; index++) {
if (t1.hasOwnProperty(index)) {
index = Number(index);
if (t2Map[t1[index].key] === undefined) {
//path.push({type: "卸载", node: t1[index]});
path.push({type: "卸载", node: t1.splice(index, 1)});
index--;
}
}
}
//移动
for (var i in t2) {
if (t2.hasOwnProperty(i)) {
i = Number(i);
var child = t2[i];
var newKey = child.key;
if (t1Map[newKey] !== undefined) {//旧的有
var old = t1.getObjIndex((cur) => cur.key === newKey);
if (old < lastIndex) {
//移动
t1.splice(lastIndex, 0, t1.splice(old, 1)[0]);
path.push({type: "移动", old, new: lastIndex});
console.log(path[path.length - 1], JSON.parse(JSON.stringify(t1)));
}
lastIndex = Math.max(old, lastIndex);
// t1Map[newKey].index = i;
} else {//旧的没有
t1.splice(lastIndex + 1, 0, child);
path.push({type: "创建", node: child, index: lastIndex + 1});
lastIndex++;
console.log(path[path.length - 1], JSON.parse(JSON.stringify(t1)));
}
}
}
return path;
}最后一种实现diffList就是最小编辑距离的问题了,可以通过动态规划求解最小操作,如果要求路径的话,还需要回溯,算法效率比较低
function diffList(oldChildren, newChildren, key) {
function listDiff(a, b, key) {
var map = [];
for (var i = 0; i < a.length; i++) {
map[i] = [];
for (var j = 0; j < b.length; j++) {
map[i][j] = {};
}
}
for (var i = 0; i < a.length; i++) {
for (var j = 0; j < b.length; j++) {
var Dmin = [];
if (i === 0 && j === 0) {
Dmin.push(0);
} else {
if (a[i - 1] && a[i - 1][key] !== undefined && b[j] && b[j][key] !== undefined || a[i-1] && !a[i-1].hasOwnProperty('key')) { // 删除
var delV = map[i - 1][j].val + 1;
Dmin.push(delV);
}
if (a[i] && a[i][key] !== undefined && b[j - 1] && b[j - 1][key] !== undefined || b[j] && !b[j].hasOwnProperty('key')) { //插入
var insV = map[i][j - 1].val + 1;
Dmin.push(insV);
}
if (a[i - 1] && a[i - 1][key] !== undefined && b[j - 1] && b[j - 1][key] !== undefined) { //替换
var repV = a[i][key] === b[j][key] ? map[i - 1][j - 1].val : (map[i - 1][j - 1].val + 1);
Dmin.push(repV);
}
}
var minV = Math.min(...Dmin);
var type = [delV, insV, repV].indexOf(minV);
map[i][j].move = {
type: type === 0 ? "卸载" : type === 1 ? "创建" : a[i][key] === b[j][key] ? "不变" : "替换",
index: i,
item: type === 0 ? null : type === 1 ? b[j] : a[i][key] === b[j][key] ? null : {
old: a[i],
new: b[j]
},
};
map[i][j].val = minV;
}
}
return map;
}
function reDiff(map) {
var startX = map.length - 1, startY = map[0].length - 1;
var path = [map[startX][startY].val];
var i = startX;
var j = startY;
var max = startX * startY;
var moves = [map[startX][startY].move];
while (i >= 0 && j >= 0) {
if (i === 0 && j === 0) {
break;
}
var min = [max, max, max];
if (map[i - 1] !== undefined && map[j - 1] !== undefined) {
min[0] = map[i - 1][j - 1].val;
}
if (map[i - 1] !== undefined && map[j] !== undefined) {
min[1] = map[i - 1][j].val;
}
if (map[i] !== undefined && map[j - 1] !== undefined) {
min[2] = map[i][j - 1].val;
}
var minV = Math.min(...min);
var minIndex = min.indexOf(minV);
path.push(minV);
if (minIndex === 0) {
i = i - 1;
j = j - 1;
}
if (minIndex === 1) {
i = i - 1;
}
if (minIndex === 2) {
j = j - 1;
}
if (minIndex === -1) {
break;
} else {
moves.push(map[i][j].move);
}
}
return moves.reverse();
}
var map = listDiff(oldChildren, newChildren, key);
return reDiff(map);
}
值得一提的是,两种diff在没有key的情况下也都能进行最小操作,如果原来没有key,那么直接卸载,如果现在没有key,那么直接创建,在做完两种diff之后才深深明白在react中同级组件为什么要加入唯一标识符key.
时间效率O(n2),但是这样的dom开销最小
参考文章: