Vue 3.0 diff 算法及原理

2021-02-19 前端大全 
// c1: a b [ c d e ] f g  
// c2: a b [ d e c h ] f g

假如有如上的 c1 和 c2 新舊 children，在 diff 的時候，會有一個預處理的過程。
先從前往後比較，當節點不同時，不再往後進行比較。接著又從後往前進行比較，當節點不同時，不再往前進行比較。
經過預處理之後，c1 和 c2 真正需要進行 diff 的部分如下所示：
// c1: c d e
// c2: d e c h

最後利用 「最長遞增子序列」，完成上述差異部分的比較，提高 diff 效率。
處理相同的前後節點
預處理過程代碼如下所示：
const patchKeyedChildren = (
    c1,
    c2,
    container,
    parentAnchor,
    parentComponent,
    parentSuspense,
    isSVG,
    optimized
) => {
    let i = 0;  
    const l2 = c2.length
    let e1 = c1.length - 1
    let e2 = c2.length - 1

    // 1. sync from start
    while (i <= e1 && i <= e2) {
      const n1 = c1[i]
      const n2 = c2[i]
      if (isSameVNodeType(n1, n2)) {
        patch(
          n1,
          n2,
          container,
          parentAnchor,
          parentComponent,
          parentSuspense,
          isSVG,
          optimized
        )
      } else {
        break
      }
      i++
    }

    // 2. sync from end
    while (i <= e1 && i <= e2) {
      const n1 = c1[e1]
      const n2 = c2[e2]
      if (isSameVNodeType(n1, n2)) {
        patch(
          n1,
          n2,
          container,
          parentAnchor,
          parentComponent,
          parentSuspense,
          isSVG,
          optimized
        )
      } else {
        break
      }
      e1--
      e2--
    }
}

僅有節點新增或移除
進行預處理還有一個好處，就是在某些情況下，我們可以明確的知道有節點的新增或者刪除。
i、e1、e2 滿足下述關係時，可以認為是有節點新增
// 3. common sequence + mount
// (a b)
// (a b) c
// i = 2, e1 = 1, e2 = 2
// (a b)
// c (a b)
// i = 0, e1 = -1, e2 = 0
if (i > e1) {
    if (i <= e2) {
        const nextPos = e2 + 1;
        const anchor = nextPos < l2 ? c2[nextPos] : parentAnchor

        while (i <= e2) {
            patch(
                null,
                c2[i],
                container,
                anchor,
                parentComponent,
                parentSuspense,
                isSVG
            )
            i++
        }
    }
} else if {
    //
} else {
    //
}

i、e1、e2 滿足下述關係時，可以認為是有節點被移除
// 4. common sequence + unmount
// (a b) c
// (a b)
// i = 2, e1 = 2, e2 = 1
// a (b c)
// (b c)
// i = 0, e1 = 0, e2 = -1
if (i > e1) {
  //
} else if (i > e2) {
    while (i <= e1) {
        unmount(c1[i], parentComponent, parentSuspense, true)
        i++
    }
} else {
    //
}

有節點移動、新增或刪除
有時候情況可能沒有上述那麼地簡單，即 i、e1、e2 並不滿足上述兩種情形時，我們就要尋找其中需要被移除、新增的節點，又或是判斷哪些節點需要進行移動。
為此，我們需要去遍歷 c1 中還沒有進行處理的節點，然後查看在 c2 中是否有對應的節點（key 相同）。沒有，則說明該節點已經被移除，那就執行 unmount 操作。
首先，為了快速確認 c1 的節點在 c2 中是否有對應的節點及所在的位置，對 c2 中的節點建立一個映射 （key: index）
// 5. unknown sequence
// [i ... e1 + 1]: a b [c d e] f g
// [i ... e2 + 1]: a b [d e c h] f g
// i = 2, e1 = 4, e2 = 5
if (i > e1) {
  //
} else if (i > e2) {
  //
} else {
    const s1 = i
    const s2 = i

    const keyToNewIndexMap = new Map()

    // 5.1 build key:index map for newChildren
    for (i = s2; i <= e2; i++) {
        const nextChild = c2[i]
        if (nextChild.key !== null) {
            keyToNewIndexMap.set(nextChild.key, i)
        }
    }
}

接著，定義以下幾個變量
let j 
let patched = 0
const toBePatched = e2 - s2 + 1  // c2 中待處理的節點數目
let moved = false

// used to track whether any node has moved
let maxNewIndexSoFar = 0  // 已遍歷的待處理的 c1 節點在 c2 中對應的索引最大值

// works as Map<newIndex, oldIndex>
// Note that oldIndex is offset by +1
// and oldIndex = 0 is a special value indicating the new node has
// no corresponding old node.
// used for determining longest stable subsequence
const newIndexToOldIndexMap = new Array(toBePatched) // 用於後面求最長遞增子序列

for (i = 0; i < toBePatched; i++) {
    newIndexToOldIndexMap[i] = 0
}

然後，遍歷 c1 中待處理的節點，判斷否 c2 中是有相同 key 的節點存在。
有，調用 patch 函數。並記錄節點在 c1 中的索引。同時，記錄節點在 c2 中的最大索引，假如節點在 c2 中的索引位置小於這個最大索引，那麼說明是有元素需要進行移動。
// 5.2 loop through old children left to be patched and try to patch
// matching nodes & remove nodes that are no longer present
for (i = s1; i <= e1; i++) {
    const prevChild = c1[i]

    // (A)

    let newIndex 
    if (prevChild.key !== null) {
        newIndex = keyToNewIndexMap.get(prevChild.key)
    } else {
        for (j = s2; i <= e2; j++) {
            if (
              newIndexToOldIndexMap[j - s2] === 0 &&
              isSameVNodeType(prevChild, c2[j])
            ) {
              newIndex = j
              break
            }
        }
    }

    if (newIndex === void 0) {
        unmount(prevChild, parentComponent, parentSuspense, true)
    } else {
        newIndexToOldIndexMap[newIndex  - s2] = i + 1  // (B)

        if (newIndex >= maxNewIndexSoFar) {
            maxNewIndexSoFar = newIndex
        } else {
            moved = true
        }
        patch(
            prevChild,
            c2[i],
            container,
            null,
            parentComponent,
            parentSuspense,
            isSVG,
            optimized
        )

        patched++  // (C)
    }
}

是不是 c1 中的所有節點都需要在 c2 中尋找對應節點，然後調用 patch 呢。
注意到上面的代碼 (C)，我們會更新已經 patched 的節點的數目，那麼當 patched > toBePatched，可以認為接下來遍歷的 c1 中的節點都是多餘的了，直接移除就好。
所以在上面的 (A) 處需要補充一下代碼
if (patched >= toBePatched) {
    // all new children have been patched so this can only be a removal
    unmount(prevChild, parentComponent, parentSuspense, true)
    continue
}

到這裡，就是較難理解的部分了。
開篇我們說過，預處理過後，剩下的節點會藉助最長遞增子序列來提高 diff 效率。
求解最長遞增子序列，主要的目的就是為了減少 dom 元素的移動，也可以理解為最少的 dom 操作。
首先，我們需要求解得到最長遞增子序列
// generate longest stable subsequence only when nodes have moved
const increasingNewIndexSequence = moved
    ? getSequence(newIndexToOldIndexMap)
    : EMPTY_ARR 

先看看這裡的 newIndexToOldIndexMap 的值是什麼。
結合一下具體的例子，假設 c1 、c2 如下圖所示
image
定義並初始化 newIndexToOldIndexMap
const newIndexToOldIndexMap = new Array(toBePatched)

for (i = 0; i < toBePatched; i++) {
    newIndexToOldIndexMap[i] = 0
}

toBePatched 即預處理後，c2 中待處理的節點數目。對應這裡的例子，會有
toBePatched = 4
newIndexToOldIndexMap = [0, 0, 0, 0]

注意到上面 5.2 遍歷 c1 中節點的代碼的 (B) 處，有
// 這裡是 i + 1，不是 i 
// 因為 0 是一個特殊值，表示這個是新增的節點
newIndexToOldIndexMap[newIndex  - s2] = i + 1  // (B)

所以處理完 c1 中的節點後，將有
moved = true
newIndexToOldIndexMap = [4, 5, 3, 0]

那麼，increasingNewIndexSequence 的值就是 getSequence(newIndexToOldIndexMap) 的返回值
// [4, 5, 3, 0]  --> 最長遞增子序列是 [4, 5] 
// 對應的索引是 [0, 1]
increasingNewIndexSequence = [0, 1]

在求解得到最長遞增子序列之後，剩下的就是遍歷 c2 中的待處理節點，判斷是否節點是否屬於新增，是否需要進行移動。
j = increasingNewIndexSequence.length - 1
// looping backwards so that we can use last patched node as anchor
// 注意：這裡是從後往前遍歷
for (i = toBePatched - 1; i >= 0; i--) {
    const nextIndex = s2 + i
    const nextChild = c2[nextIndex]
    const anchor =
        nextIndex + 1 < l2 ? (c2[nextIndex + 1]).el : parentAnchor

    // newIndexToOldIndexMap 裡的值默認初始化為 0 
    // 這裡 === 0 表示 c2 中的節點在 c1 中沒有對應的節點，屬於新增
    if (newIndexToOldIndexMap[i] === 0) {
        // mount new
        patch(
            null,
            nextChild,
            container,
            anchor,
            parentComponent,
            parentSuspense,
            isSVG
        )
    } else if (moved) {
        // move if:
        // There is no stable subsequence (e.g. a reverse)
        // OR current node is not among the stable sequence
        
        // j < 0  --> 最長遞增子序列為 [] 
        if (j < 0 || i !== increasingNewIndexSequence[j]) {
            move(nextChild, container, anchor, MoveType.REORDER)
        } else {
            j--
        }
    }
}

最長遞增子序列
在計算機科學中，最長遞增子序列（longest increasing subsequence）問題是指，在一個給定的數值序列中，找到一個子序列，使得這個子序列元素的數值依次遞增，並且這個子序列的長度儘可能地大。最長遞增子序列中的元素在原序列中不一定是連續的。-- 維基百科
對於以下的原始序列

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

最長遞增子序列為

0, 2, 6, 9, 11, 15.

值得注意的是原始序列的最長遞增子序列並不一定唯一，對於該原始序列，實際上還有以下兩個最長遞增子序列

0, 4, 6, 9, 11, 15
0, 4, 6, 9, 13, 15

最後
至此，Vue 3.0 的 diff 代碼就分析完了，歡迎一起討論。
具體的代碼：https://github.com/vuejs/vue-next/blob/master/packages/runtime-core/src/renderer.ts

相關焦點

  • Vue + webpack 學習(一)
    vue": "^2.1.0",    "vue-router": "^2.1.1",    "vuex": "^2.0.0"  },  "devDependencies": {    "autoprefixer": "^6.4.0",    "autoprefixer-loader": "^3.2.0",    "babel-core": "^
  • 前端娛樂圈大瓜:前端人因為 Vue3 的 Ref-sugar 提案打起來了!
    首先明確一件事情，想要吃這個前端娛樂圈的大瓜，各位看官姥爺得先用一下剛新鮮出爐、十分熱乎的 Vue3.0 版本，否則，這個瓜可能不太甜：）  咱們來捋一捋到底咋回事。 /Foo.vue' import { ref } from 'vue' const count = ref(0) const inc = () => { count.value++ } </script> <template> <Foo :count="count" @click="inc" /> </template>
  • 最速下降算法、牛頓算法、BFGS擬牛頓算法、共軛梯度算法無約束極值問題
    >        break    end    iter = iter+1;    syms SL    assume(SL>=0);x1=x0+SL*d_k;fx1=eval(f_sym1);d_x1=diff(fx1);    d_SL=double(solve(d_x1));fx1=matlabFunction
  • 貪心算法:加油站
    可以看一下公眾號左下角的「算法匯總」，「算法匯總」已經把題目順序編排好了，文章順序即刷題順序，這是全網最詳細的刷題順序了，方便錄友們從頭打卡學習，「算法匯總」會持續更新！❞134.此時油箱有 = 0 + 4 = 4 升汽油開往 4 號加油站，此時油箱有 4 - 1 + 5 = 8 升汽油開往 0 號加油站，此時油箱有 8 - 2 + 1 = 7 升汽油開往 1 號加油站，此時油箱有 7 - 3 + 2 = 6 升汽油開往 2 號加油站，此時油箱有 6 - 4 + 3 = 5 升汽油開往 3 號加油站，你需要消耗 5 升汽油，正好足夠你返回到
  • 益智遊戲剋星:BFS暴力搜索算法
    但是我們今天不來研究讓人頭禿的技巧，這些益智遊戲通通可以用暴力搜索算法解決，所以今天我們就學以致用，用 BFS 算法框架來秒殺這些遊戲。一、題目解析LeetCode 第 773 題就是滑動拼圖問題，題目的意思如下：給你一個 2x3 的滑動拼圖，用一個 2x3 的數組board表示。
  • 敲黑板:手把手教你 vue-cli 單頁到多頁應用
    中間 刪除(注釋)代碼部分在//del和//end中間，很多東西都寫在注釋裡第一步：cli一個vue項目新建一個vue項目，官網：vue init webpack democli默認使用webpack的dev-server服務，這個服務是做不了單頁的，需要手動建一個私服叫啥你隨意 一般叫dev.server或者dev.client。
  • 網易遊戲面試題:如何設計一個公平的洗牌算法
    ）。我記得在面試網易遊戲的時候，面試官當時是這樣問我的：「給你一副撲克牌，你能設計一個公平的洗牌算法嗎？」。我當時一懵，只想到了 rand() 函數，用來生成一個隨機數，就給面試官說：「我首先會 0 到 n-1 遍歷給定的數組元素，然後每次生成一個隨機數 rand() % (n - i) ，然後將第 i 個元素與下標為隨機數的元素交換，這樣是不是可以呢？」
  • 計算機視覺:從入門到精通,極限剖析圖像識別學習算法
    本次課程將圍繞著計算機視覺中最常見的RCNN圖像識別算法進行極限剖析，從數學理論， 模型框架到實踐實操，讓你在短時間內從理論到實踐，掌握深度學習的基本知識和學習方法。· 目的：掌握神經網絡的基本原理，知其然亦知其所以然（從數學實踐到代碼的熟練和精通）; · 手段：科學的方法。
  • 第 1 篇:很高興認識你 Vue.js
    charset="UTF-8"><title>Vue Todo Tutorial</title></head><body><div id="app">{{ message }}</div></body><script src="https://cdn.bootcss.com/vue
  • 想一個月搞定面試算法?來《九章算法班》!第一節免費試聽!
    想接受系統的面試算法培訓的同學，或想換工作的但是算法比較薄弱的工程師。0算法基礎即可參與學習。主講令狐衝老師，曾就職於超過2家矽谷頂尖IT企業,  北美和國內頂尖IT企業offer數10+，面試人數超過200人。課程大綱由易到難。只要你會任何一門計算機語言即可參加。尤其適合算法基礎相對薄弱的 or 轉專業的 or 想跳槽卻太久沒刷題的同學。分九個章節，系統的講授面試中涉及的算法知識。
  • 一文讀懂哈希和一致性哈希算法
    算法介紹哈希算法也叫散列算法, 不過英文單詞都是 Hash, 簡單一句話概括, 就是可以把任意長度的輸入信息通過算法變換成固定長度的輸出信息, 輸出信息也就是哈希值, 通常哈希值的格式是16進位或者是10進位, 比如下面的使用 md5 哈希算法的示例md5("123456") => "e10adc3949ba59abbe56e057f20f883e
  • 財務管理:成本計算--加權平均算法
    移動加權平均算法大多數的ERP使用的是加權平均算法，現在我們來舉個例子解釋一下加權平均算法步驟1：入庫2支鉛筆，每支
  • 經典算法題:猜數(360軟體測試工程師筆試題)
    又假設學生Ａ和Ｂ的結論是正確的，則這兩個數字是：（）經典算法題：《算法題 ：貪心算法（大眾點評筆試題）》《算法題 ：所有String2的字母在String1裡是否存在（大眾點評筆試題）》《算法題 ：順序表插入新元素（迅雷筆試題）》《算法題 ：迅雷2016研發工程師5道筆試題
  • 知其所以然之永不遺忘的算法
    我們當然希望自己掌握一個算法後，就永遠不會忘記，最好還能舉一反三，利用算法中的思想去解決新的問題。然而，現實與美好的願景往往是背道而馳，不要說舉一反三，我們甚至經常忘記那些算法本身。背算法與設計算法為什麼會這樣？
  • 一分鐘了解:指紋識別的技術、原理
    指紋識別主要根據人體指紋的紋路、細節特徵等信息對操作或**作者進行身份鑑定，得益於現代電子集成製造技術和快速而可靠的算法研究，已經開始走入我們的日常生活，成為目前生物檢測學中研究最深入，應用最廣泛，發展最成熟的技術。    二 什麼是指紋識別技術的原理     指紋其實是比較複雜的。
  • 【思源論壇】第95期:優秀學術人物洪永勝作學術報告: 分數階微分算法在土壤光譜領域中的應用
    12月29日晚19：00第95期思源論壇在資環院220學術報告廳如期開展，2017級土地資源管理專業博士生洪永勝同學向我們展示了分數階微分算法在土壤光譜領域中的應用。報告分為四個部分，第一部分介紹了分數階微分的研究背景；第二部分介紹了分數階微分（FOD）的方法原理；第三部分介紹了兩個研究案例，最後一部分為結論和討論。
  • 0.3+0.6+0.3+0.5+0.5,周末愉快!!
    1.新活動：0.1-50元，興旺集寶紅包，必中；   2.新活動：0.68元，民生保險紅包，大概率中；                                                   3.新活動：0.3元，佛山社保紅包，非必中；4.新活動：0.5元，鹽城消協紅包，非必中；
  • 十二地支講解:天幹地支最正確的算法
    那麼問題來了，天幹地支的真確算法是什麼樣的呢？　　本期的十二地支為你講解：天幹地支最正確的算法。　　天幹地支計算方法　　一、年幹支計算公元後年份的口訣是：　　「公元年數先減三，除10餘數是天幹，基數改用12除，餘數便是地支年」。
  • 圖解算法:摘取位運算的王冠「八皇后問題」!
    接下來我們看看位運算在算法題中的應用。現在，你只有 3 只小白鼠和一星期的時間，如何檢驗出哪個瓶子裡有毒藥？2、 將 0 到 7 編號中第一位為 1 的所有瓶子（即 1，3，5，7）的水混在一起給老鼠 1 吃，第二位值為 1 的所有瓶子（即2，3，6，7）的水混在一起給老鼠 2 吃， 第三位值為 1 的所有瓶子（4，5，6，7）的水混在一起給老鼠 3 吃，現在假設老鼠 1，3 死了，那麼有毒的瓶子編號中第 1，3 位肯定為 1，老鼠 2 沒死，則有毒的瓶子編號中第  2 位肯定為
  • 0.3+0.3+0.5+5,今天紅包趕緊拿!!
    1.新活動：0.3元，江西福彩紅包，大概率中； 2.新活動：0.3元，華碩轉盤紅包，大概率中；                                                   3.新活動：0.3元，平頂山捐書紅包，非必中；4.新活動：0.5元，消消樂遊戲紅包，非必中。