Vue3 如何通過虛擬DOM更新頁面詳解

2022-09-20 22:01:21

引言

上一講我們主要介紹了 Vue 專案的首次渲染流程，在 mountComponent 中註冊了effect 函數，這樣，在元件資料有更新的時候，就會通知到元件的 update 方法進行更新

Vue 中元件更新的方式也是使用了響應式 + 虛擬 DOM 的方式，這個我們在第一講中有介紹過 Vue 1、Vue 2 和 Vue 3 中更新方式的變化，今天我們就來詳細剖析一下 Vue 元件內部如何通過虛擬 DOM 更新頁面的程式碼細節

Vue 虛擬 DOM 執行流程

我們從虛擬 DOM 在 Vue 的執行流程開始講起。在 Vue 中，我們使用虛擬 DOM 來描述頁面的元件，比如下面的 template 雖然格式和 HTML 很像，但是在 Vue 的內部會解析成 JavaScript 函數，這個函數就是用來返回虛擬 DOM：

<div id="app">
    <p>hello world</p>
    <Rate :value="4"></Rate>
</div>

上面的 template 會解析成下面的函數，最終返回一個 JavaScript 的物件能夠描述這段HTML：

function render(){
    return h('div',{id:"app"},children:[
        h('p',{},'hello world'),
        h(Rate,{value:4}),
    ])
}

知道虛擬 DOM 是什麼之後，那麼它是怎麼建立的呢？

DOM 的建立

我們簡單回憶上一講介紹的 mount 函數，在程式碼中，我們使用 createVNode 函數建立專案的虛擬 DOM，可以看到 Vue 內部的虛擬 DOM，也就是 vnode，就是一個物件，通過 type、props、children 等屬性描述整個節點：

const vnode = createVNode( (
    rootComponent as ConcreteComponent,
    rootProps
)
function _createVNode() {
    // 處理屬性和 class
    if (props) {
    ...
    }
    // 標記vnode資訊
    const shapeFlag = isString(type)
        ? ShapeFlags.ELEMENT
        : __FEATURE_SUSPENSE__ && isSuspense(type)
        ? ShapeFlags.SUSPENSE
        : isTeleport(type)
        ? ShapeFlags.TELEPORT
        : isObject(type)
        ? ShapeFlags.STATEFUL_COMPONENT
        : isFunction(type)
        ? ShapeFlags.FUNCTIONAL_COMPONENT
        : 0
     return createBaseVNode(
        type,
        props,
        children,
        patchFlag,
        dynamicProps,
        shapeFlag,
        isBlockNode,
        true
    )
}
function createBaseVNode(type,props,children,...){
    const vnode = {
    type,
    props,
    key: props && normalizeKey(props),
    ref: props && normalizeRef(props),
    children,
    shapeFlag,
    patchFlag,
    dynamicProps,
    ...
} as VNode
// 標準化子節點
if (needFullChildrenNormalization) {
    normalizeChildren(vnode, children)
} else if (children) {
    vnode.shapeFlag |= isString(children)
        ? ShapeFlags.TEXT_CHILDREN
        : ShapeFlags.ARRAY_CHILDREN
    }
    return vnode
}componentUpdateFn

createVNode 負責建立 Vue 中的虛擬 DOM，而上一講中我們講過 mount 函數的核心邏輯就是使用 setupComponent 執行我們寫的 <script setup>，使用 setupRenderEffect 監聽元件的資料變化;所以我們來到 setupRenderEffect 函數中，去完整地剖析 Vue 中虛擬 DOM 的更新邏輯

我們給元件註冊了 update 方法，這個方法使用 effect 包裹後，當元件內的 ref、reactive 包裹的響應式資料變化的時候就會執行 update 方法，觸發元件內部的更新機制

看下面的程式碼，在 setupRenderEffect 內部的 componentUpdateFn 中，updateComponentPreRenderer 更新了屬性和 slots，並且呼叫 renderComponentRoot 函數建立新的子樹物件 nextTree，然後內部依然是呼叫 patch 函數

可以看到，Vue 原始碼中的實現首次渲染和更新的邏輯都寫在一起，我們在遞迴的時候如果對一個標籤實現更新和渲染，就可以用一個函數實現

const componentUpdateFn = ()=>{
    if (!instance.isMounted) {
    //首次渲染
    instance,
    parentSuspense,
    isSVG
    )
    。。。
}else{
    let { next, bu, u, parent, vnode } = instance
    if (next) {
        next.el = vnode.el
        updateComponentPreRender(instance, next, optimized)
    } else {
        next = vnode
    }
    const nextTree = renderComponentRoot(instance)
    patch(
        prevTree,
        nextTree,
        // parent may have changed if it's in a teleport
        hostParentNode(prevTree.el!)!,
        // anchor may have changed if it's in a fragment
        getNextHostNode(prevTree),
        instance,
        parentSuspense,
        isSVG
        )
    }
}
// 註冊effect函數
const effect = new ReactiveEffect(
    componentUpdateFn,
    () => queueJob(instance.update),
    instance.scope // track it in component's effect scope
)
const update = (instance.update = effect.run.bind(effect) as S chedulerJo
update()
const updateComponentPreRender = (
    instance: ComponentInternalInstance,
    nextVNode: VNode,
    optimized: boolean
) => {
nextVNode.component = instance
    const prevProps = instance.vnode.props
    instance.vnode = nextVNode
    instance.next = null
    updateProps(instance, nextVNode.props, prevProps, optimized)
    updateSlots(instance, nextVNode.children, optimized)
    pauseTracking()
    // props update may have triggered pre-flush watchers.
    // flush them before the render update.
    flushPreFlushCbs(undefined, instance.update)
    resetTracking()
}

比較關鍵的就是上面程式碼中 32-39 行的 effect 函數，負責註冊元件，這個函數也是 Vue 元件更新的入口函數

patch 函數

資料更新之後就會執行 patch 函數，下圖就是 patch 函數執行的邏輯圖：

在 patch 函數中，會針對不同的元件型別執行不同的函數，元件我們會執行 processComponent，HTML 標籤我們會執行 processElement：

function path(n1, n2, container){
    const { type, shapeFlag } = n2
        switch (type) {
            case Text:
            processText(n1, n2, container)
            break
            // 還有註釋，fragment之類的可以處理，這裡忽略
            default:
            // 通過shapeFlag判斷型別
            if (shapeFlag & ShapeFlags.ELEMENT) {
                processElement(n1, n2, container, anchor)
            } else if (shapeFlag & ShapeFlags.STATEFUL_COMPONENT) {
                processComponent(n1, n2, container)
            }
       }
}
function processComponent(n1, n2, container) {
    // 老規矩，沒有n1就是mount
    if (!n1) {
        // 初始化 component
        mountComponent(n2, container)
    } else {
        updateComponent(n1, n2, container)
    }
}

由於更新之後不是首次渲染了，patch 函數內部會執行 updateComponent，看下面的 updateComponent 函數內部，shouldUpdateComponent 會判斷元件是否需要更新，實際執行的是 instance.update：

const instance = (n2.component = n1.component)!
if (shouldUpdateComponent(n1, n2, optimized)) {
    // normal update
    instance.next = n2
    // in case the child component is also queued, remove it to avoid
    // double updating the same child component in the same flush.
    invalidateJob(instance.update)
    // instance.update is the reactive effect.
    instance.update()
} else {
    // no update needed. just copy over properties
    n2.component = n1.component
    n2.el = n1.el
    instance.vnode = n2
}

元件的子元素是由 HTML 標籤和元件構成，元件內部的遞迴處理最終也是對 HTML 標籤的處理，所以，最後元件的更新都會進入到 processElement 內部的 patchElement 函數中

patchElement 函數

在函數 patchElement 中我們主要就做兩件事，更新節點自己的屬性和更新子元素

節點自身屬性的更新

先看自身屬性的更新，這裡就能體現出 Vue 3 中效能優化的思想，通過 patchFlag 可以做到按需更新：

如果標記了 FULL_PROPS，就直接呼叫 patchProps;如果標記了 CLASS，說明節點只有 class 屬性是動態的，其他的 style 等屬性都不需要進行判斷和 DOM 操作

這樣就極大的優化了屬性操作的效能

內部執行 hostPatchProp 進行實際的 DOM 操作，你還記得上一講中 hostPatchProp 是從 nodeOps 中定義的嗎，其他動態屬性 STYLE、TEXT 等等也都是一樣的邏輯;Vue 3 的虛擬 DOM 真正做到了按需更新，這也是相比於 React 的一個優勢

const patchElement = (
    n1: VNode,
    n2: VNode,
    parentComponent: ComponentInternalInstance | null,
    parentSuspense: SuspenseBoundary | null,
    isSVG: boolean,
    slotScopeIds: string[] | null,
    optimized: boolean
) => {
    const el = (n2.el = n1.el!)
    let { patchFlag, dynamicChildren, dirs } = n2
    patchFlag |= n1.patchFlag & PatchFlags.FULL_PROPS
    const oldProps = n1.props || EMPTY_OBJ
    const newProps = n2.props || EMPTY_OBJ
    // full diff
    patchChildren(
        n1,
        n2,
        el,
        null,
        parentComponent,
        parentSuspense,
        areChildrenSVG,
        slotScopeIds,
        false
    )
    if (patchFlag > 0) {
        if (patchFlag & PatchFlags.FULL_PROPS) {
            patchProps(
                el,
                n2,
                oldProps,
                newProps,
                parentComponent,
                parentSuspense,
                isSVG
            )
        } else {
            // class是動態的
            if (patchFlag & PatchFlags.CLASS) {
                if (oldProps.class !== newProps.class) {
                    hostPatchProp(el, 'class', null, newProps.class, isSVG)
                }
            }
            // style樣式是動態的
            if (patchFlag & PatchFlags.STYLE) {
                hostPatchProp(el, 'style', oldProps.style, newProps.style, isSVG)
            }
            // 屬性需要diff
            if (patchFlag & PatchFlags.PROPS) {
                //
                const propsToUpdate = n2.dynamicProps!
                for (let i = 0; i < propsToUpdate.length; i++) {
                    const key = propsToUpdate[i]
                    const prev = oldProps[key]
                    const next = newProps[key]
                    // #1471 force patch value
                    if (next !== prev || key === 'value') {
                        hostPatchProp(
                            el,
                            key,
                            prev,
                            next,
                            isSVG,
                            n1.children as VNode[],
                            parentComponent,
                            parentSuspense,
                            unmountChildren
                        )
                    }
                }
            }
        }
        //文字是動態的
        if (patchFlag & PatchFlags.TEXT) {
            if (n1.children !== n2.children) {
                hostSetElementText(el, n2.children as string)
            }
        }
    }
}

子元素的更新

而子元素的更新是 patchChildren 函數負責的，這個函數也是虛擬 DOM 中難度最高的一個函數，搞懂它還需要我們下一講中介紹的演演算法知識，今天我們就先理解它主要的實現思路

首先我們把子元素分成了文字、陣列和空三個狀態，新老子元素分別是這三種狀態的一個，構成了不同的執行邏輯;這樣 patchChildren 內部大致有五種情況需要處理：

如果新的子元素是空，老的子元素不為空，直接解除安裝 unmount 即可
如果新的子元素不為空，老的子元素是空，直接建立載入即可
如果新的子元素是文字，老的子元素如果是陣列就需要全部 unmount，是文字的話就需要執行 hostSetElementText
如果新的子元素是陣列，比如是使用 v-for 渲染出來的列表，老的子元素如果是空或者文字，直接 unmout 後，渲染新的陣列即可

最複雜的情況就是新的子元素和老的子元素都是陣列

最樸實無華的思路就是把老的子元素全部 unmount，新的子元素全部 mount，這樣雖然可以實現功能，但是沒法複用已經存在的 DOM 元素，比如我們只是在陣列中間新增了一個資料，全部 DOM 都銷燬就有點太可惜了

所以，我們需要判斷出可以複用的 DOM 元素，如果一個虛擬 DOM 沒有改動或者屬性變了，不需要完全銷燬重建，而是更新一下屬性，最大化減少 DOM 的操作，這個任務就會交給 patchKeyedChildren 函數去完成

patchKeyedChildren 函數，做的事情就是儘可能高效地把老的子元素更新成新的子元素，如何高效複用老的子元素中的 DOM 元素是 patchKeyedChildren 函數的難點：

const patchChildren: PatchChildrenFn = (
    n1,
    n2,
    container,
    anchor,
    parentComponent,
    parentSuspense,
    isSVG,
    slotScopeIds,
    optimized = false
) => {
    const c1 = n1 && n1.children
    const prevShapeFlag = n1 ? n1.shapeFlag : 0
    const c2 = n2.children
    const { patchFlag, shapeFlag } = n2
    // fast path
    if (patchFlag > 0) {
        if (patchFlag & PatchFlags.KEYED_FRAGMENT) {
            // this could be either fully-keyed or mixed (some keyed some not)
            // presence of patchFlag means children are guaranteed to be arrays
            patchKeyedChildren(
                c1 as VNode[],
                c2 as VNodeArrayChildren,
                container,
                anchor,
                parentComponent,
                parentSuspense,
                isSVG,
                slotScopeIds,
                optimized
            )
            return
        } else if (patchFlag & PatchFlags.UNKEYED_FRAGMENT) {
            // unkeyed
            patchUnkeyedChildren(
                c1 as VNode[],
                c2 as VNodeArrayChildren,
                container,
                anchor,
                parentComponent,
                parentSuspense,
                isSVG,
                slotScopeIds,
                optimized
            )
            return
        }
    }
    // children has 3 possibilities: text, array or no children.
    if (shapeFlag & ShapeFlags.TEXT_CHILDREN) {
        // text children fast path
        if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) {
            unmountChildren(c1 as VNode[], parentComponent, parentSuspense)
        }
        if (c2 !== c1) {
            hostSetElementText(container, c2 as string)
        }
    } else {
        if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) {
            // prev children was array
            if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {
                // two arrays, cannot assume anything, do full diff
                patchKeyedChildren(
                    c1 as VNode[],
                    c2 as VNodeArrayChildren,
                    container,
                    anchor,
                    parentComponent,
                    parentSuspense,
                    isSVG,
                    slotScopeIds,
                    optimized
                )
            } else {
                // no new children, just unmount old
                unmountChildren(c1 as VNode[], parentComponent, parentSuspense, true
    }
        } else {
            // prev children was text OR null
            // new children is array OR null
            if (prevShapeFlag & ShapeFlags.TEXT_CHILDREN) {
                hostSetElementText(container, '')
            }
            // mount new if array
            if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {
                mountChildren(
                    c2 as VNodeArrayChildren,
                    container,
                    anchor,
                    parentComponent,
                    parentSuspense,
                    isSVG,
                    slotScopeIds,
                    optimized
                )
            }
        }
    }
}

上面的程式碼執行邏輯如下圖所示，根據 flags 判斷子元素的型別後，執行不同的操作函數：

patchChildren

最後就剩下 patchChildren 的實現了，這也是各類虛擬 DOM 框架中最難實現的函數，我們需要實現一個高效的更新演演算法，能夠使用盡可能少的更新次數，來實現從老的子元素到新的子元素的更新;

舉個例子，類似體育課站隊的時候，大家一開始站一排，但是順序是亂的，我們需要儘快把隊伍按照個頭左低右高排列

在 React 中，這種場景的處理邏輯是先進行迴圈，使用的是單側插入的演演算法，我們在排隊的時候挨個對比，如果你站我右邊，並且個頭比我高一點，說明咱倆的相對位置和最終隊伍的位置是一致的，暫時不需要變化，如果你比我個頭矮，就需要去我左邊找到一個正確的位置插隊進去

由於都只向單側插入，最後我們就會把所有的節點移動到正確的位置之上，這就是 React15 框架內虛擬節點 diff 的邏輯，初步實現了 DOM 的複用；而 Vue 2 借鑑了 snabbdom 的演演算法，在此基礎上做了第一層雙端對比的優化

首先 Web 場景之下對一個陣列元素的操作，很少有直接全部替換的，比如我們操作一個表格，大概率是更關心表格某一行的一個欄位、新增一行、刪除一行，或者是對錶格某個欄位進行排序，所以我們可以從純演演算法的場景之中加入實際應用的場景

如果我們只是在表格裡新增一行，那麼可以不要一開始就開始迴圈，而是可以先進行節點的預判

比如，在下面的例子中，新的節點就是在老的節點中新增和刪除了幾個元素，我們在迴圈之前，先進行頭部元素的判斷;在這個例子裡，可以預判出頭部元素的 a、b、c、d 是一樣的節點，說明節點不需要重新建立，我們只需要進行屬性的更新，然後進行隊尾元素的預判，可以判斷出 g 和元素也是一樣的：

a b c d e f g h
a b c d i f j g h

這樣我們虛擬 DOM diff 的邏輯就變成了下面的結構, 現在只需要比較 ef 和 ifg 的區別：

(a b c d) e f (g h)
(a b c) d) i f j (g h)

相比於之前的對比場景，我們需要遍歷的運算量就大大減小了

而且，有很多場景比如新增一行或者刪除一行的簡單場景，預判完畢之後，新老元素有一個處於沒有元素的狀態，我們就可以直接執行 mount 或者 unmout 完成對比的全過程，不需要再進行復雜的遍歷：

(a b c d)
(a b c d) e
(a b c) d
(a b c

雙端對比的原理大致就是這樣；最後雙端對比之後的執行邏輯這一部分需要一些演演算法知識，下面會我詳細介紹，這裡你只需要掌握大概的思路

想讓一個隊伍儘快按照個頭排好序，如果能夠計算出，在隊伍中，個頭從低到高依次遞增的最多的佇列，讓這些人站在原地不動，其餘人穿插到他們中間，就可以最大化減少人員的移動，這就是一個最長底層子序列的演演算法問題

位運算

前面也說了，在執行 diff 之前，要根據需要判斷每個虛擬 DOM 節點有哪些屬性需要計算，因為無論響應式資料怎麼變化，靜態的屬性和節點都不會發生變化

所以我們看每個節點 diff 的時候會做什麼，在 renderer.ts 程式碼檔案中就可以看到程式碼，主要就是通過虛擬 DOM 節點的 patchFlag 樹形判斷是否需要更新節點

方法就是使用 & 操作符來判斷操作的型別，比如 patchFlag & PatchFlags.CLASS 來判斷當前元素的 class 是否需要計算 diff；shapeFlag & ShapeFlags.ELEMENT 來判斷當前虛擬 DOM 是 HTML 元素還是 Component 元件；這個“&”其實就是位運算的按位元與

// class
// this flag is matched when the element has dynamic class bindings.
if (patchFlag & PatchFlags.CLASS) {
    if (oldProps.class !== newProps.class) {
        hostPatchProp(el, 'class', null, newProps.class, isSVG)
    }
}
// style
// this flag is matched when the element has dynamic style bindings
if (patchFlag & PatchFlags.STYLE) {
    hostPatchProp(el, 'style', oldProps.style, newProps.style, isSVG)
}
if (shapeFlag & ShapeFlags.ELEMENT) {
    processElement(
        n1,
        n2,
        container,
        anchor,
        parentComponent,
        parentSuspense,
        isSVG,
        slotScopeIds,
        optimized
    )
} else if (shapeFlag & ShapeFlags.COMPONENT) {
    processComponent(
        n1,
        n2,
        container,
        anchor,
        parentComponent,
        parentSuspense,
        isSVG,
        slotScopeIds,
        optimized
    )
}

上面的程式碼中 & 就是按位元與的操作符，這其實是二進位制上的計算符號，所以我們首先要了解一下什麼是二進位制

我們日常使用的數位都是十進位制數位，比如數位 13 就是 110+3 的運算結果，每個位置都是代表 10 的 n 次方；13 也可以使用二進位制表達，因為二進位制每個位置只能是 0 和 1 兩個數位，每個位置代表的是 2 的 n 次方，13 在二進位制裡是 1101，就是 18+14+02+1*1

而在 JavaScript 中我們可以很方便地使用 toString(2) 的方式，把十進位制數位轉換成二進位制；運算的概念很簡單，就是在二進位制上的“與”和“或”運算：

(13).toString(2) // 1101
0 & 0 // 0
0 & 1 // 0
1 & 0 // 0
1 & 1 // 1
0 | 0 // 0
0 | 1 // 1
1 | 0 // 1
1 | 1 // 1
1 << 2 // 1左移動兩位，就是100 就是1*2平方 = 4

二進位制中，我們每個位置只能是 0 或者 1 這兩個值，& 和 | 的概念和 JavaScript 中的 && 和 || 保持一致；兩個二進位制的 & 運算就是隻有兩個二進位制位置都是 1 的時候，結果是 1，其餘情況運算結果都是 0；| 是按位元置進行“或”運算，只有兩個二進位制位置都是 0 的時候，結果是 0，其餘情況運算結果都是 1；並且，還可以通過左移 << 和右移 >> 操作符，實現乘以 2 和除以 2 的效果

由於這些都是在二進位制上的計算，運算的效能通常會比字串和數位的計算效能要好，這也是很多框架內部使用位運算的原因

這麼說估計你不是很理解，我們結合一個 LeetCode 題看看為什麼說二進位制的位運算效能更好

為什麼位運算效能更好

我們來做一下 LeetCode231 題，題目描述很簡單，判斷數位 n 是不是 2 的冪次方，也就是說，判斷數位 n 是不是 2 的整次方，比如 2、4、8；我們可以很輕鬆地寫出 JavaScript 的解答，n 一直除以 2，如果有餘數就是 false，否則就是 true：

var isPowerOfTwo = function (n) {
    if (n === 1) return true
    while (n > 2) {
        n = n / 2
        if (n % 2 !== 0) return false
    }
    return n === 2
};

不過上面的解答我們可以用位運算來優化

先來分析一下 2 的冪次方的特點

2 的冪次方就是數位 1 左移動若干次，其餘位置全部都是 0，所以 n-1 就是最高位變成0，其餘位置都變成 1，就像十進位制裡的 10000-1 = 9999。這樣，n 和 n-1 每個二進位制位的數位都不一樣，我們可以很輕鬆地用按位元“與”來判斷這個題的答案，如果 n&n-1 是 0 的話，數位 n 就符合 2 的整次冪的特點：

16
10000
16-1 = 15
01111
16&15 == 0
var isPowerOfTwo = function(n) {
    return n>0 && (n & (n - 1)) === 0
};

所以我們使用位運算提高了程式碼的整體效能

如何運用位運算

好，搞清楚為什麼用位運算，我們回來看 diff 判斷，如何根據位運算的特點，設計出許可權的組合認證方案

比如 Vue 中的動態屬性，有文字、class、style、props 幾個屬性，我們可以使用二進位制中的一個位置來表示許可權，看下面的程式碼，我們使用左移的方式分別在四個二進位制上標記了 1，代表四種不同的許可權，使用按位元或的方式去實現許可權授予

比如，一個節點如果 TEXT 和 STYLE 都需要修改，我們只需要使用 | 運運算元就可以得到 flag1 的許可權表示，這就是為什麼 Vue 3 中針對虛擬 DOM 型別以及虛擬 DOM 需要動態計算 diff 的樹形都做了標記，你可以在 Vue 3 的原始碼中看到下面的設定：

const PatchFlags = {
    TEXT:1, // 0001
    CLASS: 1<<1, // 0010
    STYLE:1<<2, // 0100
    PROPS:1<<3 // 1000
}
const flag1 = PatchFlags.TEXT | PatchFlags.STYLE // 0101
// 許可權校驗
flag1 & PatchFlags.TEXT // 有許可權，結果大於1
flag1 & PatchFlags.CLASS //沒有許可權 是0

最長遞增子系列

然後就到了虛擬 DOM 計算 diff 中的演演算法了

上面我們詳細介紹了在虛擬 diff 計算中，如果新老子元素都是陣列的時候，需要先做首尾的預判，如果新的子元素和老的子元素在預判完畢後，未處理的元素依然是陣列，那麼就需要對兩個陣列計算 diff，最終找到最短的操作路徑，能夠讓老的子元素通過儘可能少的操作，更新成為新的子元素

Vue 3 借鑑了 infero 的演演算法邏輯，就像操場上需要按照個頭從低到高站好一樣，我們採用的思路是先尋找一個現有佇列中由低到高的佇列，讓這個佇列儘可能的長，它們的相對位置不需要變化，而其他元素進行插入和移動位置，這樣就可以做到儘可能少的操作DOM

所以如何尋找這個最長遞增的序列呢？這就是今天的重點演演算法知識了，我們看 LeetCode 第 300 題，題目描述如下, 需要在陣列中找到最長底層的自序列長度：

給你一個整數陣列 nums，找到其中最長嚴格遞增子序列的長度
子序列是由陣列派生而來的序列，刪除（或不刪除）陣列中的元素而不改變其餘元素的順序
例如，[3,6,2,7] 是陣列 [0,3,1,6,2,2,7] 的子序列
=
輸入：nums = [10,9,2,5,3,7,101,18]
輸出：4
解釋：最長遞增子序列是 [2,3,7,101]，因此長度為 4

首先我們可以使用動態規劃的思路，通過每一步的遞推，使用 dp 陣列，記錄出每一步操作的最優解，最後得到全域性最優解

在這個例子中，我們可以把 dp[i] 定義成 nums[0] 到 nums[i] 這個區間內，陣列的最長遞增子序列的長度，並且 dp 陣列的初始值設為 1

從左邊向右遞推，如果 nums[i+1] > nums[i]，dp[i+1]就等於 dp[i]+1；如果 nums[i+1] < nums[i]，就什麼都不需要幹，這樣我們在遍歷的過程中，就能根據陣列當前位置之前的最長遞增子序列長度推匯出 i+1 位置的最長遞增子序列長度

所以可以得到如下解法：

/**
* @param {number[]} nums
* @return {number}
*/
const lengthOfLIS = function (nums) {
    let n = nums.length;
    if (n == 0) {
        return 0;
    }
    let dp = new Array(n).fill(1);
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    return Math.max(...dp)
}

由於我們需要兩層迴圈，所以這個解法的時間複雜度是 n 的平方，這個解法其實已經不錯了，但是還有更優秀的解法，也就是 Vue 3 中用到的演演算法：貪心 + 二分

貪心 + 二分

我們再看一下這個題，貪心的思路就是在尋找最長遞增的序列，所以，[1,3]要比[1,5]好，也就是說，在這個上升的序列中，我們要讓上升速度儘可能變得慢，這樣才有可能讓後面的元素儘可能也遞增

我們可以建立一個 arr 陣列，用來儲存這種策略下的最長遞增子序列

如果當前遍歷的 nums[i] 大於 arr 的最後一個元素，也就是大於 arr 的最大值時，我們把nums[i] 追加到後面即可，否則我們就在 arr 中尋找一個第一個大於 num[i] 的數位並替換它；因為是 arr 是遞增的數列，所以在尋找插入位置的時候，我們可以使用二分查詢的方式，把整個演演算法的複雜度變成 O(nlgn)

下面的程式碼就是貪心 + 二分的解法，我們可以得到正確的最長遞增子序列的長度：

/**
* @param {number[]} nums
* @return {number}
*/
const lengthOfLIS = function (nums) {
    let len = nums.length
    if (len <= 1) {
        return len
    }
    let arr = [nums[0]]
    for (let i = 0; i < len; i++) {
        // nums[i] 大於 arr 尾元素時，直接追加到後面，遞增序列長度+1
        if (nums[i] > arr[arr.length - 1]) {
            arr.push(nums[i])
        } else {
            // 否則，查詢遞增子序列中第一個大於numsp[i]的元素 替換它
            // 遞增序列，可以使用二分查詢
            let left = 0
            let right = arr.length - 1
            while (left < right) {
                let mid = (left + right) >> 1
                if (arr[mid] < nums[i]) {
                    left = mid + 1
                } else {
                    right = mid
                }
            }
            arr[left] = nums[i]
        }
    }
    return arr.length
};

但是貪心 + 二分的這種解法，現在只能得到最長遞增子序列的長度，但是最後得到的 arr 並不一定是最長遞增子序列，因為我們移動的 num[i] 位置可能會不正確，只是得到的陣列長度是正確的，所以我們需要對這個演演算法改造一下，把整個陣列複製一份之後，最後也能得到正確的最長遞增子序列

具體程式碼怎麼寫呢？我們來到 Vue 3 的 renderer.ts 檔案中，函數 getSquenece 就是用來生成最長遞增子序列，看下面的程式碼：

// https://en.wikipedia.org/wiki/Longest_increasing_subsequence
function getSequence(arr: number[]): number[] {
    const p = arr.slice() //賦值一份arr
    const result = [0]
    let i, j, u, v, c
    const len = arr.length
    for (i = 0; i < len; i++) {
        const arrI = arr[i]
        if (arrI !== 0) {
            j = result[result.length - 1]
            if (arr[j] < arrI) {
                p[i] = j // 儲存在result最後一個索引的值
                result.push(i)
                continue
            }
            u = 0
            v = result.length - 1
            // 二分查詢，查詢比arrI小的節點，更新result的值
            while (u < v) {
                c = (u + v) >> 1
                if (arr[result[c]] < arrI) {
                    u = c + 1
                } else {
                    v = c
                }
            }
            if (arrI < arr[result[u]]) {
                if (u > 0) {
                    p[i] = result[u - 1]
                }
                result[u] = i
            }
        }
    }
    u = result.length
    v = result[u - 1]
    // 查詢陣列p 找到最終的索引
    while (u-- > 0) {
        result[u] = v
        v = p[v]
    }
    return result
}

這段程式碼就是 Vue 3 裡的實現，result 儲存的就是長度是 i 的遞增子序列最小末位置的索引，最後計算出最長遞增子序列

我們得到 increasingNewIndexSequence 佇列後，再去遍歷陣列進行 patch 操作就可以實現完整的 diff 流程了：

for (i = toBePatched - 1; i >= 0; i--) {
    const nextIndex = s2 + i
    const nextChild = c2[nextIndex] as VNode
    const anchor =
        nextIndex + 1 < l2 ? (c2[nextIndex + 1] as VNode).el : parentAnchor
    if (newIndexToOldIndexMap[i] === 0) {
        // mount new
        patch(
            null,
            nextChild,
            container,
            anchor,
            parentComponent,
            parentSuspense,
            isSVG,
            slotScopeIds,
            optimized
        )
    } else if (moved) {
        // move if:
        // There is no stable subsequence (e.g. a reverse)
        // OR current node is not among the stable sequence
        if (j < 0 || i !== increasingNewIndexSequence[j]) {
            move(nextChild, container, anchor, MoveType.REORDER)
        } else {
            j--
        }
    }
}

上面程式碼的思路，我們用下圖演示。做完雙端對比之後，a 和 g 已經計算出可以直接複用 DOM，剩下的佇列中我們需要把 hbfdc 更新成 abdef

首先我們需要使用 keyToNewIndexMap 儲存新節點中每個 key 對應的索引，比如下圖中 key 是 c 的元素的索引就是 2；然後計算出 newIndexOldIndexMap 儲存這個 key 在老的子元素中的位置，我們可以根據 c 的索引是 2，在 newIndexOldIndexMap 中查詢到在老的子元素的位置是 6，關於 newIndexOldIndexMap 的具體邏輯你可以在上面的程式碼中看到：