一区A视频,少妇被猛操

diff算法作為Virtual DOM的加速器，其算法的改進(jìn)優(yōu)化是React整個(gè)界面渲染的基礎(chǔ)和性能的保障，同時(shí)也是React源碼中最神秘的，最不可思議的部分

1.傳統(tǒng)diff算法

計(jì)算一棵樹形結(jié)構(gòu)轉(zhuǎn)換為另一棵樹形結(jié)構(gòu)需要最少步驟，如果使用傳統(tǒng)的diff算法通過循環(huán)遞歸遍歷節(jié)點(diǎn)進(jìn)行對(duì)比，其復(fù)雜度要達(dá)到O(n^3)，其中n是節(jié)點(diǎn)總數(shù)，效率十分低下，假設(shè)我們要展示1000個(gè)節(jié)點(diǎn)，那么我們就要依次執(zhí)行上十億次的比較。

下面附上一則簡(jiǎn)單的傳統(tǒng)diff算法：

let result = [];
// 比較葉子節(jié)點(diǎn)
const diffLeafs = function (beforeLeaf, afterLeaf) {
    // 獲取較大節(jié)點(diǎn)樹的長(zhǎng)度
    let count = Math.max(beforeLeaf.children.length, afterLeaf.children.length);
    // 循環(huán)遍歷
    for (let i = 0; i < count; i++) {
        const beforeTag = beforeLeaf.children[i];
        const afterTag = afterLeaf.children[i];
        // 添加 afterTag 節(jié)點(diǎn)
        if (beforeTag === undefined) {
            result.push({ type: "add", element: afterTag });
            // 刪除 beforeTag 節(jié)點(diǎn)
        } else if (afterTag === undefined) {
            result.push({ type: "remove", element: beforeTag });
            // 節(jié)點(diǎn)名改變時(shí)，刪除 beforeTag 節(jié)點(diǎn)，添加 afterTag 節(jié)點(diǎn)
        } else if (beforeTag.tagName !== afterTag.tagName) {
            result.push({ type: "remove", element: beforeTag });
            result.push({ type: "add", element: afterTag });
            // 節(jié)點(diǎn)不變而內(nèi)容改變時(shí)，改變節(jié)點(diǎn)
        } else if (beforeTag.innerHTML !== afterTag.innerHTML) {
            if (beforeTag.children.length === 0) {
                result.push({
                    type: "changed",
                    beforeElement: beforeTag,
                    afterElement: afterTag,
                    html: afterTag.innerHTML
                });
            } else {
                // 遞歸比較
                diffLeafs(beforeTag, afterTag);
            }
        }
    }
    return result;
}

2.react diff算法

1. diff策略
下面介紹一下react diff算法的3個(gè)策略

Web UI 中DOM節(jié)點(diǎn)跨層級(jí)的移動(dòng)操作特別少，可以忽略不計(jì)

擁有相同類的兩個(gè)組件將會(huì)生成相似的樹形結(jié)構(gòu)，擁有不同類的兩個(gè)組件將會(huì)生成不同的樹形結(jié)構(gòu)。

對(duì)于同一層級(jí)的一組子節(jié)點(diǎn)，它們可以通過唯一id進(jìn)行區(qū)分。

對(duì)于以上三個(gè)策略，react分別對(duì)tree diff,component diff,element diff進(jìn)行算法優(yōu)化。

2.tree diff
基于策略一，WebUI中DOM節(jié)點(diǎn)跨層級(jí)的移動(dòng)操作少的可以忽略不計(jì)，React對(duì)Virtual DOM樹進(jìn)行層級(jí)控制，只會(huì)對(duì)相同層級(jí)的DOM節(jié)點(diǎn)進(jìn)行比較，即同一個(gè)父元素下的所有子節(jié)點(diǎn)，當(dāng)發(fā)現(xiàn)節(jié)點(diǎn)已經(jīng)不存在了，則會(huì)刪除掉該節(jié)點(diǎn)下所有的子節(jié)點(diǎn)，不會(huì)再進(jìn)行比較。這樣只需要對(duì)DOM樹進(jìn)行一次遍歷，就可以完成整個(gè)樹的比較。復(fù)雜度變?yōu)镺(n);

疑問：當(dāng)我們的DOM節(jié)點(diǎn)進(jìn)行跨層級(jí)操作時(shí)，diff會(huì)有怎么樣的表現(xiàn)呢？

如下圖所示，A節(jié)點(diǎn)及其子節(jié)點(diǎn)被整個(gè)移動(dòng)到D節(jié)點(diǎn)下面去，由于React只會(huì)簡(jiǎn)單的考慮同級(jí)節(jié)點(diǎn)的位置變換，而對(duì)于不同層級(jí)的節(jié)點(diǎn)，只有創(chuàng)建和刪除操作，所以當(dāng)根節(jié)點(diǎn)發(fā)現(xiàn)A節(jié)點(diǎn)消失了，就會(huì)刪除A節(jié)點(diǎn)及其子節(jié)點(diǎn)，當(dāng)D發(fā)現(xiàn)多了一個(gè)子節(jié)點(diǎn)A，就會(huì)創(chuàng)建新的A作為其子節(jié)點(diǎn)。
此時(shí)，diff的執(zhí)行情況是：

createA-->createB-->createC-->deleteA

由此可以發(fā)現(xiàn)，當(dāng)出現(xiàn)節(jié)點(diǎn)跨層級(jí)移動(dòng)時(shí)，并不會(huì)出現(xiàn)想象中的移動(dòng)操作，而是會(huì)進(jìn)行刪除，重新創(chuàng)建的動(dòng)作，這是一種很影響React性能的操作。因此官方也不建議進(jìn)行DOM節(jié)點(diǎn)跨層級(jí)的操作。

3.componnet diff
React是基于組件構(gòu)建應(yīng)用的，對(duì)于組件間的比較所采用的策略也是非常簡(jiǎn)潔和高效的。

如果是同一個(gè)類型的組件，則按照原策略進(jìn)行Virtual DOM比較。

如果不是同一類型的組件，則將其判斷為dirty component，從而替換整個(gè)組件下的所有子節(jié)點(diǎn)。

如果是同一個(gè)類型的組件，有可能經(jīng)過一輪Virtual DOM比較下來，并沒有發(fā)生變化。如果我們能夠提前確切知道這一點(diǎn)，那么就可以省下大量的diff運(yùn)算時(shí)間。因此，React允許用戶通過shouldComponentUpdate()來判斷該組件是否需要進(jìn)行diff算法分析。

如下圖所示，當(dāng)組件D變?yōu)榻M件G時(shí)，即使這兩個(gè)組件結(jié)構(gòu)相似，一旦React判斷D和G是不用類型的組件，就不會(huì)比較兩者的結(jié)構(gòu)，而是直接刪除組件D，重新創(chuàng)建組件G及其子節(jié)點(diǎn)。雖然當(dāng)兩個(gè)組件是不同類型但結(jié)構(gòu)相似時(shí)，進(jìn)行diff算法分析會(huì)影響性能，但是畢竟不同類型的組件存在相似DOM樹的情況在實(shí)際開發(fā)過程中很少出現(xiàn)，因此這種極端因素很難在實(shí)際開發(fā)過程中造成重大影響。

4.element diff
當(dāng)節(jié)點(diǎn)屬于同一層級(jí)時(shí)，diff提供了3種節(jié)點(diǎn)操作，分別為INSERT_MARKUP(插入)，MOVE_EXISTING(移動(dòng)),REMOVE_NODE(刪除)。

INSERT_MARKUP:新的組件類型不在舊集合中，即全新的節(jié)點(diǎn)，需要對(duì)新節(jié)點(diǎn)進(jìn)行插入操作。

MOVE_EXISTING:舊集合中有新組件類型，且element是可更新的類型，這時(shí)候就需要做移動(dòng)操作，可以復(fù)用以前的DOM節(jié)點(diǎn)。

REMOVE_NODE:舊組件類型，在新集合里也有，但對(duì)應(yīng)的element不同則不能直接復(fù)用和更新，需要執(zhí)行刪除操作，或者舊組件不在新集合里的，也需要執(zhí)行刪除操作。

以下這種情況：

我們希望可以在B和C之間加一個(gè)F，Diff算法默認(rèn)執(zhí)行起來是這樣的：

即把C更新成F，D更新成C，E更新成D，最后再插入E，是不是很沒有效率？

所以我們需要使用key來給每個(gè)節(jié)點(diǎn)做一個(gè)唯一標(biāo)識(shí)，Diff算法就可以正確的識(shí)別此節(jié)點(diǎn)，找到正確的位置區(qū)插入新的節(jié)點(diǎn)。

所以key的作用主要是為了高效的更新虛擬DOM（vue中在使用相同標(biāo)簽名元素的過渡切換時(shí)，也會(huì)使用到key屬性，其目的也是為了讓vue可以區(qū)分它們，否則vue只會(huì)替換其內(nèi)部屬性而不會(huì)觸發(fā)過渡效果）。

function enqueueInsertMarkup(parentInst, markup, toIndex) {
  updateQueue.push({
    parentInst: parentInst,
    parentNode: null,
    type: ReactMultiChildUpdateTypes.INSERT_MARKUP,
    markupIndex: markupQueue.push(markup) - 1,
    content: null,
    fromIndex: null,
    toIndex: toIndex,
  });
}

function enqueueMove(parentInst, fromIndex, toIndex) {
  updateQueue.push({
    parentInst: parentInst,
    parentNode: null,
    type: ReactMultiChildUpdateTypes.MOVE_EXISTING,
    markupIndex: null,
    content: null,
    fromIndex: fromIndex,
    toIndex: toIndex,
  });
}

function enqueueRemove(parentInst, fromIndex) {
  updateQueue.push({
    parentInst: parentInst,
    parentNode: null,
    type: ReactMultiChildUpdateTypes.REMOVE_NODE,
    markupIndex: null,
    content: null,
    fromIndex: fromIndex,
    toIndex: null,
  });
}

如下圖，老集合中包含節(jié)點(diǎn)：A、B、C、D，更新后的新集合中包含節(jié)點(diǎn)：B、A、D、C，此時(shí)新老集合進(jìn)行 diff 差異化對(duì)比，發(fā)現(xiàn) B != A，則創(chuàng)建并插入 B 至新集合，刪除老集合 A；以此類推，創(chuàng)建并插入 A、D 和 C，刪除 B、C 和 D。

React 發(fā)現(xiàn)這類操作繁瑣冗余，因?yàn)檫@些都是相同的節(jié)點(diǎn)，但由于位置發(fā)生變化，導(dǎo)致需要進(jìn)行繁雜低效的刪除、創(chuàng)建操作，其實(shí)只要對(duì)這些節(jié)點(diǎn)進(jìn)行位置移動(dòng)即可。

針對(duì)這一現(xiàn)象，React 提出優(yōu)化策略：允許開發(fā)者對(duì)同一層級(jí)的同組子節(jié)點(diǎn)，添加唯一 key 進(jìn)行區(qū)分，雖然只是小小的改動(dòng)，性能上卻發(fā)生了翻天覆地的變化！

新老集合所包含的節(jié)點(diǎn)，如下圖所示，新老集合進(jìn)行 diff 差異化對(duì)比，通過 key 發(fā)現(xiàn)新老集合中的節(jié)點(diǎn)都是相同的節(jié)點(diǎn)，因此無需進(jìn)行節(jié)點(diǎn)刪除和創(chuàng)建，只需要將老集合中節(jié)點(diǎn)的位置進(jìn)行移動(dòng)，更新為新集合中節(jié)點(diǎn)的位置，此時(shí) React 給出的 diff 結(jié)果為：B、D 不做任何操作，A、C 進(jìn)行移動(dòng)操作，即可。

那么，如此高效的 diff 到底是如何運(yùn)作的呢？讓我們通過源碼進(jìn)行詳細(xì)分析。

首先對(duì)新集合的節(jié)點(diǎn)進(jìn)行循環(huán)遍歷，for (name in nextChildren)，通過唯一 key 可以判斷新老集合中是否存在相同的節(jié)點(diǎn)，if (prevChild === nextChild)，如果存在相同節(jié)點(diǎn)，則進(jìn)行移動(dòng)操作，但在移動(dòng)前需要將當(dāng)前節(jié)點(diǎn)在老集合中的位置與 lastIndex 進(jìn)行比較，if (child._mountIndex < lastIndex)，則進(jìn)行節(jié)點(diǎn)移動(dòng)操作，否則不執(zhí)行該操作。這是一種順序優(yōu)化手段，lastIndex 一直在更新，表示訪問過的節(jié)點(diǎn)在老集合中最右的位置（即最大的位置），如果新集合中當(dāng)前訪問的節(jié)點(diǎn)比 lastIndex 大，說明當(dāng)前訪問節(jié)點(diǎn)在老集合中就比上一個(gè)節(jié)點(diǎn)位置靠后，則該節(jié)點(diǎn)不會(huì)影響其他節(jié)點(diǎn)的位置，因此不用添加到差異隊(duì)列中，即不執(zhí)行移動(dòng)操作，只有當(dāng)訪問的節(jié)點(diǎn)比 lastIndex 小時(shí)，才需要進(jìn)行移動(dòng)操作。

以上圖為例，可以更為清晰直觀的描述 diff 的差異對(duì)比過程：

從新集合中取得 B，判斷老集合中存在相同節(jié)點(diǎn) B，通過對(duì)比節(jié)點(diǎn)位置判斷是否進(jìn)行移動(dòng)操作，B 在老集合中的位置 B._mountIndex = 1，此時(shí) lastIndex = 0，不滿足 child._mountIndex < lastIndex 的條件，因此不對(duì) B 進(jìn)行移動(dòng)操作；更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex)，其中 prevChild._mountIndex 表示 B 在老集合中的位置，則 lastIndex ＝ 1，并將 B 的位置更新為新集合中的位置prevChild._mountIndex = nextIndex，此時(shí)新集合中 B._mountIndex = 0，nextIndex++ 進(jìn)入下一個(gè)節(jié)點(diǎn)的判斷。
從新集合中取得 A，判斷老集合中存在相同節(jié)點(diǎn) A，通過對(duì)比節(jié)點(diǎn)位置判斷是否進(jìn)行移動(dòng)操作，A 在老集合中的位置 A._mountIndex = 0，此時(shí) lastIndex = 1，滿足 child._mountIndex < lastIndex的條件，因此對(duì) A 進(jìn)行移動(dòng)操作enqueueMove(this, child._mountIndex, toIndex)，其中 toIndex 其實(shí)就是 nextIndex，表示 A 需要移動(dòng)到的位置；更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex)，則 lastIndex ＝ 1，并將 A 的位置更新為新集合中的位置 prevChild._mountIndex = nextIndex，此時(shí)新集合中A._mountIndex = 1，nextIndex++ 進(jìn)入下一個(gè)節(jié)點(diǎn)的判斷。
從新集合中取得 D，判斷老集合中存在相同節(jié)點(diǎn) D，通過對(duì)比節(jié)點(diǎn)位置判斷是否進(jìn)行移動(dòng)操作，D 在老集合中的位置 D._mountIndex = 3，此時(shí) lastIndex = 1，不滿足 child._mountIndex < lastIndex的條件，因此不對(duì) D 進(jìn)行移動(dòng)操作；更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex)，則 lastIndex ＝ 3，并將 D 的位置更新為新集合中的位置 prevChild._mountIndex = nextIndex，此時(shí)新集合中D._mountIndex = 2，nextIndex++ 進(jìn)入下一個(gè)節(jié)點(diǎn)的判斷。
從新集合中取得 C，判斷老集合中存在相同節(jié)點(diǎn) C，通過對(duì)比節(jié)點(diǎn)位置判斷是否進(jìn)行移動(dòng)操作，C 在老集合中的位置 C._mountIndex = 2，此時(shí) lastIndex = 3，滿足 child._mountIndex < lastIndex 的條件，因此對(duì) C 進(jìn)行移動(dòng)操作 enqueueMove(this, child._mountIndex, toIndex)；更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex)，則 lastIndex ＝ 3，并將 C 的位置更新為新集合中的位置 prevChild._mountIndex = nextIndex，此時(shí)新集合中 C._mountIndex = 3，nextIndex++ 進(jìn)入下一個(gè)節(jié)點(diǎn)的判斷，由于 C 已經(jīng)是最后一個(gè)節(jié)點(diǎn)，因此 diff 到此完成。

以上主要分析新老集合中存在相同節(jié)點(diǎn)但位置不同時(shí)，對(duì)節(jié)點(diǎn)進(jìn)行位置移動(dòng)的情況，如果新集合中有新加入的節(jié)點(diǎn)且老集合存在需要?jiǎng)h除的節(jié)點(diǎn)，那么 React diff 又是如何對(duì)比運(yùn)作的呢？

以下圖為例：

從新集合中取得 B，判斷老集合中存在相同節(jié)點(diǎn) B，由于 B 在老集合中的位置 B._mountIndex = 1，此時(shí)lastIndex = 0，因此不對(duì) B 進(jìn)行移動(dòng)操作；更新 lastIndex ＝ 1，并將 B 的位置更新為新集合中的位置B._mountIndex = 0，nextIndex++進(jìn)入下一個(gè)節(jié)點(diǎn)的判斷。
從新集合中取得 E，判斷老集合中不存在相同節(jié)點(diǎn) E，則創(chuàng)建新節(jié)點(diǎn) E；更新 lastIndex ＝ 1，并將 E 的位置更新為新集合中的位置，nextIndex++進(jìn)入下一個(gè)節(jié)點(diǎn)的判斷。
從新集合中取得 C，判斷老集合中存在相同節(jié)點(diǎn) C，由于 C 在老集合中的位置C._mountIndex = 2，lastIndex = 1，此時(shí) C._mountIndex > lastIndex，因此不對(duì) C 進(jìn)行移動(dòng)操作；更新 lastIndex ＝ 2，并將 C 的位置更新為新集合中的位置，nextIndex++ 進(jìn)入下一個(gè)節(jié)點(diǎn)的判斷。
從新集合中取得 A，判斷老集合中存在相同節(jié)點(diǎn) A，由于 A 在老集合中的位置A._mountIndex = 0，lastIndex = 2，此時(shí) A._mountIndex < lastIndex，因此對(duì) A 進(jìn)行移動(dòng)操作；更新 lastIndex ＝ 2，并將 A 的位置更新為新集合中的位置，nextIndex++ 進(jìn)入下一個(gè)節(jié)點(diǎn)的判斷。
當(dāng)完成新集合中所有節(jié)點(diǎn) diff 時(shí)，最后還需要對(duì)老集合進(jìn)行循環(huán)遍歷，判斷是否存在新集合中沒有但老集合中仍存在的節(jié)點(diǎn)，發(fā)現(xiàn)存在這樣的節(jié)點(diǎn) D，因此刪除節(jié)點(diǎn) D，到此 diff 全部完成。

_updateChildren: function(nextNestedChildrenElements, transaction, context) {
  var prevChildren = this._renderedChildren;
  var nextChildren = this._reconcilerUpdateChildren(
    prevChildren, nextNestedChildrenElements, transaction, context
  );
  if (!nextChildren && !prevChildren) {
    return;
  }
  var name;
  var lastIndex = 0;
  var nextIndex = 0;
  for (name in nextChildren) {
    if (!nextChildren.hasOwnProperty(name)) {
      continue;
    }
    var prevChild = prevChildren && prevChildren[name];
    var nextChild = nextChildren[name];
    if (prevChild === nextChild) {
      // 移動(dòng)節(jié)點(diǎn)
      this.moveChild(prevChild, nextIndex, lastIndex);
      lastIndex = Math.max(prevChild._mountIndex, lastIndex);
      prevChild._mountIndex = nextIndex;
    } else {
      if (prevChild) {
        lastIndex = Math.max(prevChild._mountIndex, lastIndex);
        // 刪除節(jié)點(diǎn)
        this._unmountChild(prevChild);
      }
      // 初始化并創(chuàng)建節(jié)點(diǎn)
      this._mountChildAtIndex(
        nextChild, nextIndex, transaction, context
      );
    }
    nextIndex++;
  }
  for (name in prevChildren) {
    if (prevChildren.hasOwnProperty(name) &&
        !(nextChildren && nextChildren.hasOwnProperty(name))) {
      this._unmountChild(prevChildren[name]);
    }
  }
  this._renderedChildren = nextChildren;
},
// 移動(dòng)節(jié)點(diǎn)
moveChild: function(child, toIndex, lastIndex) {
  if (child._mountIndex < lastIndex) {
    this.prepareToManageChildren();
    enqueueMove(this, child._mountIndex, toIndex);
  }
},
// 創(chuàng)建節(jié)點(diǎn)
createChild: function(child, mountImage) {
  this.prepareToManageChildren();
  enqueueInsertMarkup(this, mountImage, child._mountIndex);
},
// 刪除節(jié)點(diǎn)
removeChild: function(child) {
  this.prepareToManageChildren();
  enqueueRemove(this, child._mountIndex);
},

_unmountChild: function(child) {
  this.removeChild(child);
  child._mountIndex = null;
},

_mountChildAtIndex: function(
  child,
  index,
  transaction,
  context) {
  var mountImage = ReactReconciler.mountComponent(
    child,
    transaction,
    this,
    this._nativeContainerInfo,
    context
  );
  child._mountIndex = index;
  this.createChild(child, mountImage);
},

當(dāng)然，React diff 還是存在些許不足與待優(yōu)化的地方，如下圖所示，若新集合的節(jié)點(diǎn)更新為：D、A、B、C，與老集合對(duì)比只有 D 節(jié)點(diǎn)移動(dòng)，而 A、B、C 仍然保持原有的順序，理論上 diff 應(yīng)該只需對(duì) D 執(zhí)行移動(dòng)操作，然而由于 D 在老集合的位置是最大的，導(dǎo)致其他節(jié)點(diǎn)的 _mountIndex < lastIndex，造成 D 沒有執(zhí)行移動(dòng)操作，而是 A、B、C 全部移動(dòng)到 D 節(jié)點(diǎn)后面的現(xiàn)象。

總結(jié)

React 通過制定大膽的 diff 策略，將 O(n3) 復(fù)雜度的問題轉(zhuǎn)換成 O(n) 復(fù)雜度的問題；
React 通過分層求異的策略，對(duì) tree diff 進(jìn)行算法優(yōu)化；
React 通過相同類生成相似樹形結(jié)構(gòu)，不同類生成不同樹形結(jié)構(gòu)的策略，對(duì) component diff 進(jìn)行算法優(yōu)化；
React 通過設(shè)置唯一 key的策略，對(duì) element diff 進(jìn)行算法優(yōu)化；
建議，在開發(fā)組件時(shí)，保持穩(wěn)定的 DOM 結(jié)構(gòu)會(huì)有助于性能的提升；
建議，在開發(fā)過程中，盡量減少類似將最后一個(gè)節(jié)點(diǎn)移動(dòng)到列表首部的操作，當(dāng)節(jié)點(diǎn)數(shù)量過大或更新操作過于頻繁時(shí)，在一定程度上會(huì)影響 React 的渲染性能。

本文參考：https://blog.csdn.net/qq_26708777/article/details/78107577
https://calendar.perfplanet.com/2013/diff/
https://zhuanlan.zhihu.com/p/20346379?refer=purerender

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

react diff算法淺析

react diff算法淺析

1.傳統(tǒng)diff算法

2.react diff算法

總結(jié)

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

react diff算法淺析

1.傳統(tǒng)diff算法

2.react diff算法

總結(jié)

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av