React系列 --- virtualdom diff算法實(shí)現(xiàn)分析(三)

sunsmell 發(fā)布于2019-08-26 10:37 / 1958人閱讀

摘要：所以只針對(duì)同層級(jí)節(jié)點(diǎn)做比較，將復(fù)雜度的問(wèn)題轉(zhuǎn)換成復(fù)雜度的問(wèn)題。

React系列

React系列 --- 簡(jiǎn)單模擬語(yǔ)法(一)
React系列 --- Jsx, 合成事件與Refs(二)
React系列 --- virtualdom diff算法實(shí)現(xiàn)分析(三)
React系列 --- 從Mixin到HOC再到HOOKS(四)
React系列 --- createElement, ReactElement與Component部分源碼解析(五)
React系列 --- 從使用React了解Css的各種使用方案(六)

完整代碼可查看virtualdom-diff

渲染DOM

經(jīng)歷過(guò)PHP模板開(kāi)發(fā)或者JQuery的洗禮的人都知道,它們實(shí)現(xiàn)重新渲染采用最簡(jiǎn)單粗暴的辦法就是重新構(gòu)建DOM替換舊DOM,問(wèn)題也很明顯

性能消耗高

無(wú)法保存狀態(tài)(聚焦,滾動(dòng)等)

我們先看看創(chuàng)建一個(gè)元素所包含的實(shí)例屬性有多少個(gè)

const div = document.createElement("div");
let num = 0;
for (let k in div) {
  num++;
}
console.log(num); // 241

然后瀏覽器根據(jù)CSS規(guī)則查找匹配節(jié)點(diǎn),計(jì)算合并樣式布局,為了避免重新計(jì)算一般瀏覽器會(huì)保存這些數(shù)據(jù).但這是整個(gè)過(guò)程下來(lái)依然會(huì)耗費(fèi)大量的內(nèi)存和 CPU 資源.

Virtual DOM

實(shí)際也是操作Dom樹(shù)進(jìn)行渲染更新,但是它只是針對(duì)修改部分進(jìn)行局部渲染,將影響降到最低,雖然實(shí)現(xiàn)方式各有不同,但是大體步驟如下:

用Javascript對(duì)象結(jié)構(gòu)描述Dom樹(shù)結(jié)構(gòu),然后用它來(lái)構(gòu)建真正的Dom樹(shù)插入文檔

當(dāng)狀態(tài)發(fā)生改變之后,重新構(gòu)造新的Javascript對(duì)象結(jié)構(gòu)和舊的作對(duì)比得出差異

針對(duì)差異之處進(jìn)行重新構(gòu)建更新視圖

無(wú)非就是利用Js做一層映射比較,操作簡(jiǎn)單并且速度遠(yuǎn)遠(yuǎn)高于直接比較Dom樹(shù)

基礎(chǔ)工具函數(shù)

無(wú)非就是一些類型判斷,循環(huán)遍歷的簡(jiǎn)化函數(shù)

function type(obj) {
  return Object.prototype.toString.call(obj).replace(/[objects|]/g, "");
}

function isArray(list) {
  return type(list) === "Array";
}

function isObject(obj) {
  return type(obj) === "Object";
}

function isString(str) {
  return type(str) === "String";
}

function isNotEmptyObj(obj) {
  return isObject(obj) && JSON.stringify(obj) != "{}";
}

function objForEach(obj, fn) {
  isNotEmptyObj(obj) && Object.keys(obj).forEach(fn);
}

function aryForEach(ary, fn) {
  ary.length && ary.forEach(fn);
}

function setAttr(node, key, value) {
  switch (key) {
    case "style":
      node.style.cssText = value;
      break;
    case "value":
      var tagName = node.tagName || "";
      tagName = tagName.toLowerCase();
      if (tagName === "input" || tagName === "textarea") {
        node.value = value;
      } else {
        // if it is not a input or textarea, use `setAttribute` to set
        node.setAttribute(key, value);
      }
      break;
    default:
      node.setAttribute(key, value);
      break;
  }
}

function toArray(data) {
  if (!data) {
    return [];
  }
  const ary = [];
  aryForEach(data, item => {
    ary.push(item);
  });

  return ary;
}

export {
  isArray,
  isObject,
  isString,
  isNotEmptyObj,
  objForEach,
  aryForEach,
  setAttr,
  toArray
};

相關(guān)代碼可以查看util.js

Javascript對(duì)象結(jié)構(gòu)描述

我之前講JSX的時(shí)候舉過(guò)這么個(gè)例子,然后我們就以這個(gè)來(lái)實(shí)現(xiàn)效果吧

"use strict";

React.createElement("div", {
  className: "num",
  index: 1
}, React.createElement("span", null, "123456"));

創(chuàng)建一個(gè)Element類負(fù)責(zé)將Javascript對(duì)象結(jié)構(gòu)轉(zhuǎn)換為Dom樹(shù)結(jié)構(gòu)

import {
  isObject,
  isString,
  isArray,
  isNotEmptyObj,
  objForEach,
  aryForEach
} from "./util";
import { NOKEY } from "./common";

class Element {
  constructor(tagName, props, children) {
    // 解析參數(shù)
    this.tagName = tagName;
    // 字段處理,可省略參數(shù)
    this.props = isObject(props) ? props : {};
    this.children =
      children ||
      (!isNotEmptyObj(this.props) &&
        ((isString(props) && [props]) || (isArray(props) && props))) ||
      [];
    // 無(wú)論void后的表達(dá)式是什么，void操作符都會(huì)返回undefined
    this.key = props ? props.key : void NOKEY;

    // 計(jì)算節(jié)點(diǎn)數(shù)
    let count = 0;
    aryForEach(this.children, (item, index) => {
      if (item instanceof Element) {
        count += item.count;
      } else {
        this.children[index] = "" + item;
      }
      count++;
    });
    this.count = count;
  }

  render() {
    // 根據(jù)tagName構(gòu)建
    const dom = document.createElement(this.tagName);

    // 設(shè)置props
    objForEach(this.props, propName =>
      dom.setAttribute(propName, this.props[propName])
    );

    // 渲染children
    aryForEach(this.children, child => {
      const childDom =
        child instanceof Element
          ? child.render() // 如果子節(jié)點(diǎn)也是虛擬DOM，遞歸構(gòu)建DOM節(jié)點(diǎn)
          : document.createTextNode(child); // 如果字符串，只構(gòu)建文本節(jié)點(diǎn)
      dom.appendChild(childDom);
    });
    return dom;
  }
}

// 改變傳參方式,免去手動(dòng)實(shí)例化
export default function CreateElement(tagName, props, children) {
  return new Element( tagName, props, children );
}

新建示例,調(diào)用方式如下

// 1. 構(gòu)建虛擬DOM
const tree = createElement("div", { id: "root" }, [
  createElement("h1", { style: "color: blue" }, ["Tittle1"]),
  createElement("p", ["Hello, virtual-dom"]),
  createElement("ul", [
    createElement("li", { key: 1 }, ["li1"]),
    createElement("li", { key: 2 }, ["li2"]),
    createElement("li", { key: 3 }, ["li3"]),
    createElement("li", { key: 4 }, ["li4"])
  ])
]);

// 2. 通過(guò)虛擬DOM構(gòu)建真正的DOM
const root = tree.render();
document.body.appendChild(root);

運(yùn)行之后能正常得出結(jié)果了,那么第一步驟算是完成了,具體還有更多不同類型標(biāo)簽,對(duì)應(yīng)事件狀態(tài)先略過(guò).

界面如圖

Javascript結(jié)構(gòu)如圖

結(jié)構(gòu)原型如下

相關(guān)代碼可以查看element.js

diff算法

這是整個(gè)實(shí)現(xiàn)里面最關(guān)鍵的一步,因?yàn)檫@決定了計(jì)算的速度和操作Dom的數(shù)量

我們創(chuàng)建新的Dom樹(shù)作對(duì)比

// 3. 生成新的虛擬DOM
const newTree = createElement("div", { id: "container" }, [
  createElement("h1", { style: "color: red" }, ["Title2"]),
  createElement("h3", ["Hello, virtual-dom"]),
  createElement("ul", [
    createElement("li", { key: 3 }, ["li3"]),
    createElement("li", { key: 1 }, ["li1"]),
    createElement("li", { key: 2 }, ["li2"]),
    createElement("li", { key: 5 }, ["li5"])
  ])
]);

Javascript結(jié)構(gòu)如圖

tree diff

傳統(tǒng) diff 算法的復(fù)雜度為 O(n^3)，但是一般Dom跨層級(jí)的情況是非常少見(jiàn)的。所以React 只針對(duì)同層級(jí)Dom節(jié)點(diǎn)做比較，將 O(n^3) 復(fù)雜度的問(wèn)題轉(zhuǎn)換成 O(n) 復(fù)雜度的問(wèn)題。

比較大的問(wèn)題就是當(dāng)節(jié)點(diǎn)跨層級(jí)移動(dòng)并不會(huì)進(jìn)行移動(dòng)而是直接替換整個(gè)節(jié)點(diǎn),所以切記這點(diǎn)性能問(wèn)題

component diff

某個(gè)組件發(fā)生變化,會(huì)導(dǎo)致自其從上往下整體替換

同一類型組件會(huì)進(jìn)行Virtual DOM進(jìn)行比較

React提供了一個(gè)shouldComponentUpdate決定是否更新

盡可能將動(dòng)態(tài)組件往底層節(jié)點(diǎn)遷移,有利于提高性能

element diff

元素操作無(wú)非就是幾種,我們定義幾個(gè)類型做狀態(tài)標(biāo)記

const REPLACE = "replace";
const REORDER = "reorder";
const PROPS = "props";
const TEXT = "text";
const NOKEY = "no_key"

export {
  REPLACE,
  REORDER,
  PROPS,
  TEXT,
  NOKEY
}

其中NOKEY就是專門給那些沒(méi)有定義key的組件做默認(rèn),React對(duì)同一層級(jí)的同組子節(jié)點(diǎn)，添加唯一 key 進(jìn)行區(qū)分進(jìn)行位移而不是直接替換,這點(diǎn)對(duì)于整體性能尤為關(guān)鍵

我們首先針對(duì)不同類型做些區(qū)分處理

import { isString, objForEach, aryForEach, isNotEmptyObj } from "./util";
import { REPLACE, REORDER, PROPS, TEXT } from "./common";
import listDiff from "list-diff2";

/**
 *
 * @param {舊Dom樹(shù)} oTree
 * @param {新Dom樹(shù)} nTree
 * 返回差異記錄
 */
function diff(oTree, nTree) {
  // 節(jié)點(diǎn)位置
  let index = 0;
  // 差異記錄
  const patches = {};
  dfsWalk(oTree, nTree, index, patches);
  return patches;
}

function dfsWalk(oNode, nNode, index, patches) {
  const currentPatch = [];

  // 首次渲染
  if (nNode === null) return;

  // 都是字符串形式并且不相同直接替換文字
  if (isString(oNode) && isString(nNode)) {
    oNode !== nNode &&
      currentPatch.push({
        type: TEXT,
        content: nNode
      });
    // 同種標(biāo)簽并且key相同
  } else if (oNode.tagName === nNode.tagName && oNode.key === nNode.key) {
    // 至少一方有值
    if (isNotEmptyObj(oNode.props) || isNotEmptyObj(nNode.props)) {
      // 計(jì)算props結(jié)果
      const propsPatches = diffProps(oNode, nNode);
      // 有差異則重新排序
      propsPatches &&
        currentPatch.push({
          type: PROPS,
          props: propsPatches
        });
    }
    // children對(duì)比
    if (
      !(!isNotEmptyObj(nNode.props) && nNode.props.hasOwnProperty("ignore"))
    ) {
      (oNode.children.length || nNode.children.length) &&
        diffChildren(
          oNode.children,
          nNode.children,
          index,
          patches,
          currentPatch
        );
    }
  } else {
    // 都不符合上面情況就直接替換
    currentPatch.push({ type: REPLACE, node: nNode });
  }

  // 最終對(duì)比結(jié)果
  currentPatch.length && (patches[index] = currentPatch);
}

新舊節(jié)點(diǎn)的props屬性比較

/**
 *
 * @param {舊節(jié)點(diǎn)} oNode
 * @param {新節(jié)點(diǎn)} nNode
 */
function diffProps(oNode, nNode) {
  let isChange = false;
  const oProps = oNode.props;
  const nProps = nNode.props;
  // 節(jié)點(diǎn)屬性記錄
  const propsPatched = {};

  // 替換/新增屬性
  objForEach(oProps, key => {
    if (nProps[key] !== oProps[key] || !oProps.hasOwnProperty(key)) {
      !isChange && (isChange = true);
      propsPatched[key] = nProps[key];
    }
  });

  return !isChange ? null : propsPatched;
}

新舊節(jié)點(diǎn)的子元素對(duì)比

/**
 *  同級(jí)對(duì)比
 * @param {*} oChildren
 * @param {*} nChildren
 * @param {*} index
 * @param {*} patches
 * @param {*} currentPatch
 */
function diffChildren(oChildren, nChildren, index, patches, currentPatch) {
  // 得出相對(duì)簡(jiǎn)化移動(dòng)路徑
  const diffs = listDiff(oChildren, nChildren, "key");

  // 保留元素
  nChildren = diffs.children;

  // 記錄排序位移
  diffs.moves.length &&
    currentPatch.push({ type: REORDER, moves: diffs.moves });

  // 深度遍歷
  let leftNode = null;
  let currentNodeIndex = index;
  aryForEach(oChildren, (_item, _index) => {
    const nChild = nChildren[_index];
    currentNodeIndex =
      leftNode && leftNode.count
        ? currentNodeIndex + leftNode.count + 1
        : currentNodeIndex + 1;
    _item !== nChild && dfsWalk(_item, nChild, currentNodeIndex, patches);
    leftNode = _item;
  });
}

深度遍歷的原型圖如下

其中的listDiff來(lái)自于list-diff,能通過(guò)關(guān)鍵屬性獲得最小移動(dòng)量,moves就是給第三步更新視圖做鋪墊指示,官方介紹如下

Diff two lists in time O(n). I The algorithm finding the minimal amount of moves is Levenshtein distance which is O(n*m). This algorithm is not the best but is enougth for front-end DOM list manipulation.

This project is mostly influenced by virtual-dom algorithm.

調(diào)用對(duì)比方式

// 4. 比較兩棵虛擬DOM樹(shù)的不同
const patches = diff(tree, newTree);

得出差異如下

相關(guān)代碼可以查看diff.js

更新視圖

進(jìn)行深度遍歷

import {
  isString,
  isObject,
  objForEach,
  aryForEach,
  setAttr,
  toArray
} from "./util";
import { REPLACE, REORDER, PROPS, TEXT, NOKEY } from "./common";

function patch(node, patches) {
  const walker = { index: 0 };
  dfsWalk(node, walker, patches);
}

// 深度遍歷更新
function dfsWalk(node, walker, patches) {
  const currentPatches = patches[walker.index];

  node.childNodes &&
    aryForEach(node.childNodes, item => {
      walker.index++;
      dfsWalk(item, walker, patches);
    });

  currentPatches && applyPatches(node, currentPatches);
}

針對(duì)不同標(biāo)志做對(duì)應(yīng)處理

// 更新類型
function applyPatches(node, currentPatches) {
  aryForEach(currentPatches, item => {
    switch (item.type) {
      case REPLACE:
        const nNode = isString(item.node)
          ? document.createTextNode(item.node)
          : item.node.render();
        node.parentNode.replaceChild(nNode, node);
        break;
      case REORDER:
        reorderChildren(node, item.moves);
        break;
      case PROPS:
        setProps(node, item.props);
        break;
      case TEXT:
        if (node.textContent) {
          // 使用純文本
          node.textContent = item.content;
        } else {
          // 僅僅對(duì)CDATA片段，注釋comment，Processing Instruction節(jié)點(diǎn)或text節(jié)點(diǎn)有效
          node.nodeValue = item.content;
        }
        break;
      default:
        throw new Error("Unknown patch type " + item.type);
    }
  });
}

先說(shuō)簡(jiǎn)單的屬性替換

// 修改屬性
function setProps(node, props) {
  objForEach(props, key => {
    if (props[key] === void NOKEY) {
      node.removeAttribute(key);
    } else {
      setAttr(node, key, props[key]);
    }
  });
}

最后就是列表渲染

// 列表排序渲染
function reorderChildren(node, moves) {
  const staticNodeList = toArray(node.childNodes);
  const maps = {};

  aryForEach(staticNodeList, node => {
    // Element
    if (node.nodeType === 1) {
      const key = node.getAttribute("key");
      key && (maps[key] = node);
    }
  });

  aryForEach(moves, move => {
    const index = move.index;
    // 0:刪除 1:替換
    if (move.type === 0) {
      // 找到對(duì)應(yīng)節(jié)點(diǎn)刪除
      staticNodeList[index] === node.childNodes[index] &&
        node.removeChild(node.childNodes[index]);
      staticNodeList.splice(index, 1);
    } else if (move.type === 1) {
      let insertNode;
      if (maps[move.item.key]) {
        // 刪除并返回節(jié)點(diǎn)
        insertNode = node.removeChild(maps[move.item.key]);
        // 獲取刪除節(jié)點(diǎn)位置
        staticNodeList.splice(Array.prototype.indexOf.call(node.childNodes, maps[move.item.key]), 1);
      } else {
        // 創(chuàng)建節(jié)點(diǎn)
        insertNode = isObject(move.item)
          ? move.item.render()
          : document.createTextNode(move.item);
      }
      // 同步staticNodeList信息
      staticNodeList.splice(index, 0, insertNode);
      // 操作Dom
      node.insertBefore(insertNode, node.childNodes[index] || null);
    }
  });
}

export default patch;

當(dāng)這一步完成以后我們可以直接應(yīng)用查看效果

// 4. 比較兩棵虛擬DOM樹(shù)的不同
const patches = diff(tree, newTree);

// 5. 在真正的DOM元素上應(yīng)用變更
patch(root, patches);

結(jié)果如圖

相關(guān)代碼可以查看patch.js

參考

深度剖析：如何實(shí)現(xiàn)一個(gè) Virtual DOM 算法

云服務(wù)器 GPU云服務(wù)器系列三算法系列 react實(shí)現(xiàn)輪播圖超融合方案分析系列

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/106487.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

sunsmell

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

#雙11#傲游主機(jī)：充值111送111，全場(chǎng)VPS 7.5折促銷，可選中國(guó)香港/日本/歐洲等10個(gè)機(jī)

閱讀 3198·2021-11-10 11:35
HTML5 Canvas圓盤抽獎(jiǎng)應(yīng)用DEMO

閱讀 1305·2019-08-30 13:20
前端每日實(shí)戰(zhàn)：99# 視頻演示如何用純 CSS 創(chuàng)作一個(gè)過(guò)山車 loader

閱讀 1126·2019-08-29 16:18
優(yōu)秀博文收藏（不定期更新）

閱讀 2141·2019-08-26 13:54
javascript系列--Object.assign實(shí)現(xiàn)淺拷貝的原理以及實(shí)現(xiàn)

閱讀 2166·2019-08-26 13:50
精讀《編寫有彈性的組件》

閱讀 966·2019-08-26 13:39
循序漸進(jìn)教你實(shí)現(xiàn)一個(gè)完整的node的EventEmitter模塊

閱讀 2483·2019-08-26 12:08
React系列 --- virtualdom diff算法實(shí)現(xiàn)分析(三)

閱讀 1959·2019-08-26 10:37

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

React系列 --- virtualdom diff算法實(shí)現(xiàn)分析(三)

相關(guān)文章

React && VUE Virtual Dom的Diff算法統(tǒng)一之路 snabbd

**深入React知識(shí)點(diǎn)整理（一）**

React系列 --- 簡(jiǎn)單模擬語(yǔ)法(一)

**虛擬DOM與DIFF算法學(xué)習(xí)**

React系列 --- Jsx, 合成事件與Refs(二)

發(fā)表評(píng)論

0條評(píng)論

sunsmell

男|高級(jí)講師

TA的文章

#雙11#傲游主機(jī)：充值111送111，全場(chǎng)VPS 7.5折促銷，可選中國(guó)香港/日本/歐洲等10個(gè)機(jī)

HTML5 Canvas圓盤抽獎(jiǎng)應(yīng)用DEMO

前端每日實(shí)戰(zhàn)：99# 視頻演示如何用純 CSS 創(chuàng)作一個(gè)過(guò)山車 loader

優(yōu)秀博文收藏（不定期更新）

javascript系列--Object.assign實(shí)現(xiàn)淺拷貝的原理以及實(shí)現(xiàn)

精讀《編寫有彈性的組件》

循序漸進(jìn)教你實(shí)現(xiàn)一個(gè)完整的node的EventEmitter模塊