关于javascript:手写现代前端框架diff算法前端面试进阶

前言

在前端工程上，日益简单的明天，性能优化曾经成为必不可少的环境。前端须要从每一个细节的问题去优化。那么如何更优，当然与他的如何怎么实现的无关。比方 key 为什么不能应用 index 呢？为什么不应用随机数呢？答案当然是影响性能，那为什么？置信你看完本文的 diff 算法就能略懂一些。

diff 算法的概念

diff 算法, 是 Virtual DOM 产生的一个概念，作用是用来计算出 Virtual DOM 中被扭转的局部，而后依据算法算出 dom 的后果进行原生 DOM 操作，而不必从新渲染整个页面，从而进步了页面渲染效率，曾经成为当今框架（vue,react）必不可少的局部。

手写 diff 算法的过程

背景：dom 对性能的耗费特地高，因而前辈们提出用 js 对象模仿 dom 的操作，计算出最初须要更新的局部。而 dom 自身的算法的工夫复杂度是 O(n ^ 3)。这时 react 团队，提出了 diff 算法！（本案例提供外围代码，以及残缺案例）
简略了解版本的思路的外围，可分为三个步骤：

1. 模仿 ”dom 树 ”，将 dom 转换为 js 数组。

 定义 js 构造函数，可同步 dom 对象。通常对象可由下边组成：tag('string'): 标签的名称
  props('object'): 属性与属性的值 {class: 'a', type: 'hidden'}
  children('array'): 子属性
  key('string'): 示意元素的惟一标识 'nowKeys'

2. 获取两个 dom 数之间的差别（diff 算法）

 比照两个 dom 对应的实体，获取他们的不同点，依据程序数组。以后 demo 解决了以下办法：

  Change: 'Change',// 示意元素有变动
  Move: 'Move',// 示意挪动了地位
  Add: 'Add',// 示意元素是新增的
  Del: 'Del',// 示意元素给删除了
  DiffPropsList: 'DiffPropsList',// 示意元素对应的属性列表有变动
  DelProps: 'DelProps',// 示意该属性给删除
  ChangeProps: 'ChangeProps',// 示意该属性有变动
  AddProps: 'AddProps',// 示意该属性是新增的 

3. 将“差别”进行“渲染”

 依据步骤 2），将差别进行对应的解决

实例办法如下：

var a1 =new WzElement('div', { class: 'a1Class'}, ['a1'], "a1")；var a2 =new WzElement('div', { class: 'a2Class'}, ['a2'], "a2")
let root = a1.render();//js 模仿 dom 生成
步骤 2）let pathchs = diff(a1, a2); // 获取以后的两个 dom 的差别
步骤 3）reloadDom(root, pathchs);// 依据差别从新渲染 

外围的代码（步骤 1）：

  _createDom(tag, props, children, key){let dom = document.createElement( tag);
      for(let propKey in props){dom.setAttribute( propKey, props[propKey] );
      }
      if(!key){dom.setAttribute( "key", key);
      }
      children.forEach( item => {if( item instanceof WzElement){//
              var root = this._createDom(
                  item.tag,
                  item.props,
                  item.children,
                  item.key
              )
              dom.appendChild(root); 
          }else{var childNode = document.createTextNode( item);
              dom.appendChild(childNode); 
          }
      });
      return dom;
  }

外围的代码（步骤 2）：

// 判断以后对象
function dfs(oldElement, newElement, index, patches) {
    // 如果新的对象为空，无须要比照
    // 如果新的对象，key 跟 tag 都不同，阐明元素变了，间接替换。// 如果新的对象，key 跟 tag 都雷同，则遍历子集，察看子集是否不同, 察看元素属性是否不同
    var curPatches = [];
    if (!newElement) {} else if (oldElement.key != newElement.key || oldElement.tag != newElement.tag) {
        curPatches.push({
            type: stateType.Change,
            node: newElement
        });
    } else {var propsDiff = diffProps(oldElement.props, newElement.props);
        if (propsDiff.length > 0) {
            curPatches.push({
                type: stateType.DiffPropsList,
                node: newElement
            });
        }
        diffChildren(oldElement.children,  newElement.children,index, patches);// 比照子集是否不同
    }
    if (curPatches.length > 0) {if (!patches[index]) {patches[index] = []}
        patches[index] = patches[index].concat(curPatches);
    }
    return patches;
}


// 比照子集是否不同
function diffChildren(oldChild, newChild, index, patches) {let { changeList, resultList} = listDiff(oldChild, newChild, index, patches);
    if (changeList.length > 0) {if (!patches[index]) {patches[index] = []}
        patches[index] = patches[index].concat(changeList);
    }
    let last = null;
    oldChild && oldChild.forEach((item, i) => {
        let child = item && item.children;
        if (child) {if ( last && last.children != null) {// 有子节点
                index = index + last.children.length + 1;
            } else {index += 1;}
            let keyIndex = resultList.indexOf(item.key) ;
            let node = newChild[keyIndex]
            // 只遍历新旧中都存在的节点，其余新增或者删除的没必要遍历
            if (node) {dfs(item, node, index, patches)
            }
        } else {index += 1;}
        last = item
    });
}

参考 前端进阶面试题具体解答

外围的代码（步骤 3）：

var num = 0;
// 依据 virtDom 的后果渲染页面
function reloadDom(node, patchs){var changes = patchs[ num];
    let childNodes = node && node.childNodes;
    if (!childNodes) num += 1
    if(changes != null){changeDom( node, changes);
    }
    // 放弃更 diff 算法的 num 始终
    var last = null
    childNodes && childNodes.forEach((item, i) => {if( childNodes){if ( last && last.children != null) {// 有子节点
                num = num + last.children.length + 1;
            } else {num += 1;}
        }
        reloadDom(item, patchs);
        last = item;
    })
}

// 执行每个 dom 的变动
function changeDom(node, changes){
    changes && changes.forEach( change => {let {type} = change;
        switch(type){
            case stateType.Change:
                node.parentNode && node.parentNode.replaceChild(change.node.create() , node );
                break;
            case stateType.Move:
                let fromNode = node.childNodes[change.from];
                let toNode =  node.childNodes[change.to];
                let formClone = fromNode.cloneNode(true);
                let toClone = toNode.cloneNode(true);
                node.replaceChild(fromNode, toClone) ;
                node.replaceChild(toNode, formClone) ;
                break;
            case stateType.Add:
                node.insertBefore(change.node.create(),  node.childNodes[change.index]  )
                break;
            case stateType.Del:
                node.childNodes[change.index].remove();
                break;
            case stateType.DiffPropsList:
                let {props} = change.node;
                for(let key in props){if( key == stateType.DelProps){node.removeAttribute();
                    } else {node.setAttribute( key, props[key] );
                    }
                }
                break;
            default:
                break;
        }
    });
}