Vue3?如何通過虛擬DOM更新頁面詳解
引言
上一講我們主要介紹了 Vue 項目的首次渲染流程，在 mountComponent 中注冊了effect 函數(shù)，這樣，在組件數(shù)據(jù)有更新的時候，就會通知到組件的 update 方法進行更新
Vue 中組件更新的方式也是使用了響應式 + 虛擬 DOM 的方式，這個我們在第一講中有介紹過 Vue 1、Vue 2 和 Vue 3 中更新方式的變化，今天我們就來詳細剖析一下 Vue 組件內(nèi)部如何通過虛擬 DOM 更新頁面的代碼細節(jié)
Vue 虛擬 DOM 執(zhí)行流程
我們從虛擬 DOM 在 Vue 的執(zhí)行流程開始講起。在 Vue 中，我們使用虛擬 DOM 來描述頁面的組件，比如下面的 template 雖然格式和 HTML 很像，但是在 Vue 的內(nèi)部會解析成 JavaScript 函數(shù)，這個函數(shù)就是用來返回虛擬 DOM：
<div id="app">
<p>hello world</p>
<Rate :value="4"></Rate>
</div>
上面的 template 會解析成下面的函數(shù)，最終返回一個 JavaScript 的對象能夠描述這段HTML：
function render(){
return h('div',{id:"app"},children:[
h('p',{},'hello world'),
h(Rate,{value:4}),
])
}
知道虛擬 DOM 是什么之后，那么它是怎么創(chuàng)建的呢？
DOM 的創(chuàng)建
我們簡單回憶上一講介紹的 mount 函數(shù)，在代碼中，我們使用 createVNode 函數(shù)創(chuàng)建項目的虛擬 DOM，可以看到 Vue 內(nèi)部的虛擬 DOM，也就是 vnode，就是一個對象，通過 type、props、children 等屬性描述整個節(jié)點：
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
// 標準化子節(jié)點
if (needFullChildrenNormalization) {
normalizeChildren(vnode, children)
} else if (children) {
vnode.shapeFlag |= isString(children)
? ShapeFlags.TEXT_CHILDREN
: ShapeFlags.ARRAY_CHILDREN
}
return vnode
}componentUpdateFn
createVNode 負責創(chuàng)建 Vue 中的虛擬 DOM，而上一講中我們講過 mount 函數(shù)的核心邏輯就是使用 setupComponent 執(zhí)行我們寫的 <script setup>，使用 setupRenderEffect 監(jiān)聽組件的數(shù)據(jù)變化;所以我們來到 setupRenderEffect 函數(shù)中，去完整地剖析 Vue 中虛擬 DOM 的更新邏輯
我們給組件注冊了 update 方法，這個方法使用 effect 包裹后，當組件內(nèi)的 ref、reactive 包裹的響應式數(shù)據(jù)變化的時候就會執(zhí)行 update 方法，觸發(fā)組件內(nèi)部的更新機制
看下面的代碼，在 setupRenderEffect 內(nèi)部的 componentUpdateFn 中，updateComponentPreRenderer 更新了屬性和 slots，并且調(diào)用 renderComponentRoot 函數(shù)創(chuàng)建新的子樹對象 nextTree，然后內(nèi)部依然是調(diào)用 patch 函數(shù)
可以看到，Vue 源碼中的實現(xiàn)首次渲染和更新的邏輯都寫在一起，我們在遞歸的時候如果對一個標簽實現(xiàn)更新和渲染，就可以用一個函數(shù)實現(xiàn)
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函數(shù)
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 函數(shù)，負責注冊組件，這個函數(shù)也是 Vue 組件更新的入口函數(shù)
patch 函數(shù)
數(shù)據(jù)更新之后就會執(zhí)行 patch 函數(shù)，下圖就是 patch 函數(shù)執(zhí)行的邏輯圖：
在 patch 函數(shù)中，會針對不同的組件類型執(zhí)行不同的函數(shù)，組件我們會執(zhí)行 processComponent，HTML 標簽我們會執(zhí)行 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) {
// 老規(guī)矩，沒有n1就是mount
if (!n1) {
// 初始化 component
mountComponent(n2, container)
} else {
updateComponent(n1, n2, container)
}
}
由于更新之后不是首次渲染了，patch 函數(shù)內(nèi)部會執(zhí)行 updateComponent，看下面的 updateComponent 函數(shù)內(nèi)部，shouldUpdateComponent 會判斷組件是否需要更新，實際執(zhí)行的是 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 標簽和組件構成，組件內(nèi)部的遞歸處理最終也是對 HTML 標簽的處理，所以，最后組件的更新都會進入到 processElement 內(nèi)部的 patchElement 函數(shù)中
patchElement 函數(shù)
在函數(shù) patchElement 中我們主要就做兩件事，更新節(jié)點自己的屬性和更新子元素
節(jié)點自身屬性的更新
先看自身屬性的更新，這里就能體現(xiàn)出 Vue 3 中性能優(yōu)化的思想，通過 patchFlag 可以做到按需更新：
如果標記了 FULL_PROPS，就直接調(diào)用 patchProps;如果標記了 CLASS，說明節(jié)點只有 class 屬性是動態(tài)的，其他的 style 等屬性都不需要進行判斷和 DOM 操作
這樣就極大的優(yōu)化了屬性操作的性能
內(nèi)部執(zhí)行 hostPatchProp 進行實際的 DOM 操作，你還記得上一講中 hostPatchProp 是從 nodeOps 中定義的嗎，其他動態(tài)屬性 STYLE、TEXT 等等也都是一樣的邏輯;Vue 3 的虛擬 DOM 真正做到了按需更新，這也是相比于 React 的一個優(yōu)勢
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是動態(tài)的
if (patchFlag & PatchFlags.CLASS) {
if (oldProps.class !== newProps.class) {
hostPatchProp(el, 'class', null, newProps.class, isSVG)
}
}
// style樣式是動態(tài)的
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
)
}
}
}
}
//文本是動態(tài)的
if (patchFlag & PatchFlags.TEXT) {
if (n1.children !== n2.children) {
hostSetElementText(el, n2.children as string)
}
}
}
}
子元素的更新
而子元素的更新是 patchChildren 函數(shù)負責的，這個函數(shù)也是虛擬 DOM 中難度最高的一個函數(shù)，搞懂它還需要我們下一講中介紹的算法知識，今天我們就先理解它主要的實現(xiàn)思路
首先我們把子元素分成了文本、數(shù)組和空三個狀態(tài)，新老子元素分別是這三種狀態(tài)的一個，構成了不同的執(zhí)行邏輯;這樣 patchChildren 內(nèi)部大致有五種情況需要處理：
- 如果新的子元素是空， 老的子元素不為空，直接卸載 unmount 即可
- 如果新的子元素不為空，老的子元素是空，直接創(chuàng)建加載即可
- 如果新的子元素是文本，老的子元素如果是數(shù)組就需要全部 unmount，是文本的話就需要執(zhí)行 hostSetElementText
- 如果新的子元素是數(shù)組，比如是使用 v-for 渲染出來的列表，老的子元素如果是空或者文本，直接 unmout 后，渲染新的數(shù)組即可
最復雜的情況就是新的子元素和老的子元素都是數(shù)組
最樸實無華的思路就是把老的子元素全部 unmount，新的子元素全部 mount，這樣雖然可以實現(xiàn)功能，但是沒法復用已經(jīng)存在的 DOM 元素，比如我們只是在數(shù)組中間新增了一個數(shù)據(jù)，全部 DOM 都銷毀就有點太可惜了
所以，我們需要判斷出可以復用的 DOM 元素，如果一個虛擬 DOM 沒有改動或者屬性變了，不需要完全銷毀重建，而是更新一下屬性，最大化減少 DOM 的操作，這個任務就會交給 patchKeyedChildren 函數(shù)去完成
patchKeyedChildren 函數(shù)，做的事情就是盡可能高效地把老的子元素更新成新的子元素，如何高效復用老的子元素中的 DOM 元素是 patchKeyedChildren 函數(shù)的難點：
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
)
}
}
}
}
上面的代碼執(zhí)行邏輯如下圖所示，根據(jù) flags 判斷子元素的類型后，執(zhí)行不同的操作函數(shù)：
patchChildren
最后就剩下 patchChildren 的實現(xiàn)了，這也是各類虛擬 DOM 框架中最難實現(xiàn)的函數(shù)，我們需要實現(xiàn)一個高效的更新算法，能夠使用盡可能少的更新次數(shù)，來實現(xiàn)從老的子元素到新的子元素的更新;
舉個例子，類似體育課站隊的時候，大家一開始站一排，但是順序是亂的，我們需要盡快把隊伍按照個頭左低右高排列
在 React 中，這種場景的處理邏輯是先進行循環(huán)，使用的是單側(cè)插入的算法，我們在排隊的時候挨個對比，如果你站我右邊，并且個頭比我高一點，說明咱倆的相對位置和最終隊伍的位置是一致的，暫時不需要變化，如果你比我個頭矮，就需要去我左邊找到一個正確的位置插隊進去
由于都只向單側(cè)插入，最后我們就會把所有的節(jié)點移動到正確的位置之上，這就是 React15 框架內(nèi)虛擬節(jié)點 diff 的邏輯，初步實現(xiàn)了 DOM 的復用；而 Vue 2 借鑒了 snabbdom 的算法，在此基礎上做了第一層雙端對比的優(yōu)化
首先 Web 場景之下對一個數(shù)組元素的操作，很少有直接全部替換的，比如我們操作一個表格，大概率是更關心表格某一行的一個字段、新增一行、刪除一行，或者是對表格某個字段進行排序，所以我們可以從純算法的場景之中加入實際應用的場景
如果我們只是在表格里新增一行，那么可以不要一開始就開始循環(huán)，而是可以先進行節(jié)點的預判
比如，在下面的例子中，新的節(jié)點就是在老的節(jié)點中新增和刪除了幾個元素，我們在循環(huán)之前，先進行頭部元素的判斷;在這個例子里，可以預判出頭部元素的 a、b、c、d 是一樣的節(jié)點，說明節(jié)點不需要重新創(chuàng)建，我們只需要進行屬性的更新，然后進行隊尾元素的預判，可以判斷出 g 和元素也是一樣的：
a b c d e f g h
a b c d i f j g h
這樣我們虛擬 DOM diff 的邏輯就變成了下面的結(jié)構, 現(xiàn)在只需要比較 ef 和 ifg 的區(qū)別：
(a b c d) e f (g h)
(a b c) d) i f j (g h)
相比于之前的對比場景，我們需要遍歷的運算量就大大減小了
而且，有很多場景比如新增一行或者刪除一行的簡單場景，預判完畢之后，新老元素有一個處于沒有元素的狀態(tài)，我們就可以直接執(zhí)行 mount 或者 unmout 完成對比的全過程，不需要再進行復雜的遍歷：
(a b c d)
(a b c d) e
(a b c) d
(a b c
雙端對比的原理大致就是這樣；最后雙端對比之后的執(zhí)行邏輯這一部分需要一些算法知識，下面會我詳細介紹，這里你只需要掌握大概的思路
想讓一個隊伍盡快按照個頭排好序，如果能夠計算出，在隊伍中，個頭從低到高依次遞增的最多的隊列，讓這些人站在原地不動，其余人穿插到他們中間，就可以最大化減少人員的移動，這就是一個最長底層子序列的算法問題
位運算
前面也說了，在執(zhí)行 diff 之前，要根據(jù)需要判斷每個虛擬 DOM 節(jié)點有哪些屬性需要計算，因為無論響應式數(shù)據(jù)怎么變化，靜態(tài)的屬性和節(jié)點都不會發(fā)生變化
所以我們看每個節(jié)點 diff 的時候會做什么，在 renderer.ts 代碼文件中就可以看到代碼，主要就是通過虛擬 DOM 節(jié)點的 patchFlag 樹形判斷是否需要更新節(jié)點
方法就是使用 & 操作符來判斷操作的類型，比如 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
)
}
上面的代碼中 & 就是按位與的操作符，這其實是二進制上的計算符號，所以我們首先要了解一下什么是二進制
我們?nèi)粘Ｊ褂玫臄?shù)字都是十進制數(shù)字，比如數(shù)字 13 就是 110+3 的運算結(jié)果，每個位置都是代表 10 的 n 次方；13 也可以使用二進制表達，因為二進制每個位置只能是 0 和 1 兩個數(shù)字，每個位置代表的是 2 的 n 次方，13 在二進制里是 1101，就是 18+14+02+1*1
而在 JavaScript 中我們可以很方便地使用 toString(2) 的方式，把十進制數(shù)字轉(zhuǎn)換成二進制；運算的概念很簡單，就是在二進制上的“與”和“或”運算：
(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 的時候，結(jié)果是 1，其余情況運算結(jié)果都是 0；| 是按位置進行“或”運算，只有兩個二進制位置都是 0 的時候，結(jié)果是 0，其余情況運算結(jié)果都是 1；并且，還可以通過左移 << 和右移 >> 操作符，實現(xiàn)乘以 2 和除以 2 的效果
由于這些都是在二進制上的計算，運算的性能通常會比字符串和數(shù)字的計算性能要好，這也是很多框架內(nèi)部使用位運算的原因
這么說估計你不是很理解，我們結(jié)合一個 LeetCode 題看看為什么說二進制的位運算性能更好
為什么位運算性能更好
我們來做一下 LeetCode231 題，題目描述很簡單，判斷數(shù)字 n 是不是 2 的冪次方，也就是說，判斷數(shù)字 n 是不是 2 的整次方，比如 2、4、8；我們可以很輕松地寫出 JavaScript 的解答，n 一直除以 2，如果有余數(shù)就是 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
};
不過上面的解答我們可以用位運算來優(yōu)化
先來分析一下 2 的冪次方的特點
2 的冪次方就是數(shù)字 1 左移動若干次，其余位置全部都是 0，所以 n-1 就是最高位變成0，其余位置都變成 1，就像十進制里的 10000-1 = 9999。這樣，n 和 n-1 每個二進制位的數(shù)字都不一樣，我們可以很輕松地用按位“與”來判斷這個題的答案，如果 n&n-1 是 0 的話，數(shù)字 n 就符合 2 的整次冪的特點：
16
10000
16-1 = 15
01111
16&15 == 0
var isPowerOfTwo = function(n) {
return n>0 && (n & (n - 1)) === 0
};
所以我們使用位運算提高了代碼的整體性能
如何運用位運算
好，搞清楚為什么用位運算，我們回來看 diff 判斷，如何根據(jù)位運算的特點，設計出權限的組合認證方案
比如 Vue 中的動態(tài)屬性，有文本、class、style、props 幾個屬性，我們可以使用二進制中的一個位置來表示權限，看下面的代碼，我們使用左移的方式分別在四個二進制上標記了 1，代表四種不同的權限，使用按位或的方式去實現(xiàn)權限授予
比如，一個節(jié)點如果 TEXT 和 STYLE 都需要修改，我們只需要使用 | 運算符就可以得到 flag1 的權限表示，這就是為什么 Vue 3 中針對虛擬 DOM 類型以及虛擬 DOM 需要動態(tài)計算 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 // 有權限，結(jié)果大于1
flag1 & PatchFlags.CLASS //沒有權限 是0
最長遞增子系列
然后就到了虛擬 DOM 計算 diff 中的算法了
上面我們詳細介紹了在虛擬 diff 計算中，如果新老子元素都是數(shù)組的時候，需要先做首尾的預判，如果新的子元素和老的子元素在預判完畢后，未處理的元素依然是數(shù)組，那么就需要對兩個數(shù)組計算 diff，最終找到最短的操作路徑，能夠讓老的子元素通過盡可能少的操作，更新成為新的子元素
Vue 3 借鑒了 infero 的算法邏輯，就像操場上需要按照個頭從低到高站好一樣，我們采用的思路是先尋找一個現(xiàn)有隊列中由低到高的隊列，讓這個隊列盡可能的長，它們的相對位置不需要變化，而其他元素進行插入和移動位置，這樣就可以做到盡可能少的操作DOM
所以如何尋找這個最長遞增的序列呢？這就是今天的重點算法知識了，我們看 LeetCode 第 300 題，題目描述如下, 需要在數(shù)組中找到最長底層的自序列長度：
給你一個整數(shù)數(shù)組 nums，找到其中最長嚴格遞增子序列的長度
子序列是由數(shù)組派生而來的序列，刪除（或不刪除）數(shù)組中的元素而不改變其余元素的順序
例如，[3,6,2,7] 是數(shù)組 [0,3,1,6,2,2,7] 的子序列
=
輸入：nums = [10,9,2,5,3,7,101,18]
輸出：4
解釋：最長遞增子序列是 [2,3,7,101]，因此長度為 4
首先我們可以使用動態(tài)規(guī)劃的思路，通過每一步的遞推，使用 dp 數(shù)組，記錄出每一步操作的最優(yōu)解，最后得到全局最優(yōu)解
在這個例子中，我們可以把 dp[i] 定義成 nums[0] 到 nums[i] 這個區(qū)間內(nèi)，數(shù)組的最長遞增子序列的長度，并且 dp 數(shù)組的初始值設為 1
從左邊向右遞推，如果 nums[i+1] > nums[i]，dp[i+1]就等于 dp[i]+1；如果 nums[i+1] < nums[i]，就什么都不需要干，這樣我們在遍歷的過程中，就能根據(jù)數(shù)組當前位置之前的最長遞增子序列長度推導出 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)
}
由于我們需要兩層循環(huán)，所以這個解法的時間復雜度是 n 的平方，這個解法其實已經(jīng)不錯了，但是還有更優(yōu)秀的解法，也就是 Vue 3 中用到的算法：貪心 + 二分
貪心 + 二分
我們再看一下這個題，貪心的思路就是在尋找最長遞增的序列，所以，[1,3]要比[1,5]好，也就是說，在這個上升的序列中，我們要讓上升速度盡可能變得慢，這樣才有可能讓后面的元素盡可能也遞增
我們可以創(chuàng)建一個 arr 數(shù)組，用來保存這種策略下的最長遞增子序列
如果當前遍歷的 nums[i] 大于 arr 的最后一個元素，也就是大于 arr 的最大值時，我們把nums[i] 追加到后面即可，否則我們就在 arr 中尋找一個第一個大于 num[i] 的數(shù)字并替換它；因為是 arr 是遞增的數(shù)列，所以在尋找插入位置的時候，我們可以使用二分查找的方式，把整個算法的復雜度變成 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
};
但是貪心 + 二分的這種解法，現(xiàn)在只能得到最長遞增子序列的長度，但是最后得到的 arr 并不一定是最長遞增子序列，因為我們移動的 num[i] 位置可能會不正確，只是得到的數(shù)組長度是正確的，所以我們需要對這個算法改造一下，把整個數(shù)組復制一份之后，最后也能得到正確的最長遞增子序列
具體代碼怎么寫呢？我們來到 Vue 3 的 renderer.ts 文件中，函數(shù) 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小的節(jié)點，更新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]
// 查找數(shù)組p 找到最終的索引
while (u-- > 0) {
result[u] = v
v = p[v]
}
return result
}
這段代碼就是 Vue 3 里的實現(xiàn)，result 存儲的就是長度是 i 的遞增子序列最小末位置的索引，最后計算出最長遞增子序列
我們得到 increasingNewIndexSequence 隊列后，再去遍歷數(shù)組進行 patch 操作就可以實現(xiàn)完整的 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 已經(jīng)計算出可以直接復用 DOM，剩下的隊列中我們需要把 hbfdc 更新成 abdef
首先我們需要使用 keyToNewIndexMap 存儲新節(jié)點中每個 key 對應的索引，比如下圖中 key 是 c 的元素的索引就是 2；然后計算出 newIndexOldIndexMap 存儲這個 key 在老的子元素中的位置，我們可以根據(jù) c 的索引是 2，在 newIndexOldIndexMap 中查詢到在老的子元素的位置是 6， 關于 newIndexOldIndexMap 的具體邏輯你可以在上面的代碼中看到：
以上就是Vue3 如何通過虛擬DOM更新頁面詳解的詳細內(nèi)容，更多關于Vue3虛擬DOM更新頁面的資料請關注腳本之家其它相關文章！
相關文章
vue動態(tài)路由加載時出現(xiàn)Cannot?find?module?xxx問題
這篇文章主要介紹了vue動態(tài)路由加載時出現(xiàn)Cannot?find?module?xxx問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-01-01
ref 加在子組件上，用this.$refs.（ref值） 獲取到的是組件實例，可以使用組件的所有方法，?在使用方法的時候直接this.$refs.（ref值）.方法（） 就可以使用了，這篇文章主要介紹了VUE中$refs的基本用法,需要的朋友可以參考下2022-12-12
vue 生成gzip壓縮包部署到nginx服務器，如果我們把web網(wǎng)站資源進行gzip壓縮后進行傳輸給瀏覽器，這樣就能加快網(wǎng)站資源的加載速度，這篇文章主要介紹了vue生成gzip壓縮包部署到nginx,需要的朋友可以參考下2022-12-12
這篇文章主要介紹了vue-cli3添加模式配置多環(huán)境變量的方法，本文通過實例代碼給大家介紹的非常詳細，具有一定的參考借鑒價值,需要的朋友可以參考下2019-06-06
這篇文章主要為大家介紹了Vue的data為啥只能是函數(shù)原理詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-10-10
這篇文章給大家介紹了使用vue-cli導入Element UI組件的方法，非常不錯，具有一定的參考借鑒價值，需要的朋友一起看看吧2018-05-05
這篇文章主要介紹了vue中巧用三元表達式解析，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-04-04
這篇文章主要介紹了 vue3.0 CLI - 2.6 - 組件的復用，非常不錯，具有一定的參考借鑒價值 ,需要的朋友可以參考下2018-09-09
解決vue-quill-editor上傳內(nèi)容由于圖片是base64的導致字符太長的問題
vue-quill-editor默認插入圖片是直接將圖片轉(zhuǎn)為base64再放入內(nèi)容中，如果圖片較多，篇幅太長，就會比較煩惱，接下來通過本文給大家介紹vue-quill-editor上傳內(nèi)容由于圖片是base64的導致字符太長的問題及解決方法,需要的朋友可以參考下2018-08-08
這篇文章主要介紹了vue（2.x，3.0）配置跨域代理，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-11-11