diff演算法是一種透過同層的樹節點進行比較的高效演算法,避免了對樹進行逐層搜尋遍歷。那麼大家對diff演算法嗎有多少了解呢?以下這篇文章就來帶大家深入解析下vue2的diff演算法,希望對大家有幫助!
因為之前看面試直播也常問到Diff 演算法,然後作者本人用Vue2 比較多,所以打算研究Vue2 的Diff 演算法,其實很早就想學的,但是可能因為感覺Diff 演算法比較深奧,就一直拖著沒學,但是最近在準備面試,就想著遲早都要學的,趁這個機會把Diff 算法搞懂吧?,作者就花了一天的時間研究了一下,可能沒有完全理解Diff 演算法的精髓,請各位見諒。
? 這個其實算作者的學習筆記,而且作者水平有限,改文章僅代表作者個人觀點,如果有錯誤可以評論區指出來,會不斷完善;同時本文很長,所以請讀者們有耐心的看完,看完後作者相信你們會對Diff 演算法有更深的了解。本人覺得本文比目前網路解Diff 演算法的大部分文章要更好,因為這篇文章從問題出發,教大家如何思考,而不是直接從答案出發,就像讀答案一樣,這樣感覺沒什麼意思,本文一步一步的引導大家去感受Diff 演算法的精妙,同時最後也做了一下小實驗,讓大家對Diff 演算法有更直覺的感受?。
因為Vue2 底層是用虛擬DOM 來表示頁面結構的,虛擬DOM其實就是一個對象,如果想知道怎麼生成的,其實大概流程就是:
#其實框架為了效能才使用的虛擬DOM,因為js 產生DOM 然後展示頁面是很消耗性能的,如果每一次的更新都把整個頁面重新生成一遍那體驗肯定不好,所以需要找到兩個頁面中變化的地方,然後只要把變化的地方用js 更新(可能是增加、刪除或更新) 一下就行了,也就是最小量更新。 那麼要怎麼實現最小量更新呢?那就要用 Diff 演算法了,那麼 Diff 演算法比較的到底是什麼呢?可能這是剛學Diff 演算法比較容易誤解的地方,其實比對的是新舊虛擬DOM,所以Diff 演算法就是找不同,找到兩次虛擬DOM 的不同之處,然後將不同反應到頁面上,這就實現了最小量更新,如果只更新變化的地方那麼性能肯定更好。
其實這個比較難解釋,作者也就大致說一下,學了Vue 的都知道這個框架的特點之一就有數據回應式,什麼是響應式,也就是資料更新頁面也更新,那麼頁面是怎麼知道自己要更新了呢?其實這就是這個框架比較高明的地方了,大致流程如下:
Object.defineProperty
的get
,那麼在這裡收集依賴,那麼是誰收集依賴呢?是每個元件,每個元件就是一個Watcher,會記錄這個元件內的所有變數(也就是依賴),當然每個依賴(Dep) 也會收集自己所在元件的Watcher;Object.defineProperty
的set
,在這個函數裡面資料就會通知每個Watcher 更新頁面,然後每個頁面就會呼叫更新方法,這個方法就是patch
;其實是邊找邊更新的,為了讓大家理解容易就將這兩個部分分開了
面試問到Diff 演算法是什麼,大家一定會說兩句,例如頭、尾尾、尾頭、頭尾
、深度優先遍歷(dfs)
、同層比較
類似這些話語,雖然能說一兩句其實也是淺嚐輒止。
其實作者看了CSDN 上發的關於Diff 演算法的文章,就是閱讀量很高的文章,作者覺得他也沒講明白,可能他自己沒明白,或者自己明白了但是沒講清楚,那麼作者會用自己的感悟和大家分享一下。
為了讓大家能夠了解清楚,這裡先說明一下函數呼叫流程:
前提 這個是很重要的,可能大家會問什麼是前提?不就是之前說的那些比較嘛?說的沒錯但也不對,因為Diff 演算法到達之前說的
頭頭、尾尾、尾頭、頭尾 這一步的前提就是兩次對比的節點是
相同的 ,這裡的相同不是大家想的完全相同,只是符合某些條件就是相同了,為了簡化說明,文章就只考慮一個標籤只包含
key 和
標籤名(tag),那麼之前說的相同就是
key 相同以及tag 相同,為了證明作者的說法是有點正確的,那麼這裡也貼上源碼:
// https://github.com/vuejs/vue/blob/main/src/core/vdom/patch.ts // 36行 function sameVnode(a, b) { return ( a.key === b.key && a.asyncFactory === b.asyncFactory && ((a.tag === b.tag && a.isComment === b.isComment && isDef(a.data) === isDef(b.data) && sameInputType(a, b)) || (isTrue(a.isAsyncPlaceholder) && isUndef(b.asyncFactory.error))) ) }如果怕亂了,下面的可以省略不看也沒事不影響整體了解,以下只是為了考慮所有情況才加的一個判斷: 那如果兩個虛擬DOM 不相同其實就不用繼續比較了,而且如果相同也不用比較了,這裡的相同是真的完全相同,也就是兩個虛擬DOM 的位址是一樣的,那麼也貼上原始碼:
function patchVnode(......) { if (oldVnode === vnode) { return } ...... }到目前為止大家可能會比較亂,現在總結一下:
函數裡比較的是新舊虛擬DOM 是否是
key 相同以及tag 相同,如果不相同那麼就直接替換,如果相同用
patchVnode
相同的 才會考慮Diff 演算法,如果不符合那直接把原來的刪除,替換新的DOM 就行了。
原始碼中核心程式碼在其實,目前介紹patchVnode 的都是直接對著源碼來介紹的,但是大家可能不清楚為啥要這麼分類,那麼作者在這裡就讓大家明白為什麼這麼分類,首先在這裡說一個結論:patch.ts 的 638 行至 655 行。
屬性和
children 屬性不可能同時存在,這個需要大家看模板解析原始碼部分
text 和
children 的情況,那麼會有以下九種情況
舊節點text | 老節點children | 新節點text | 新節點children | |
---|---|---|---|---|
❎ | ❎ | ❎ | ❎ | |
2 | ❎ | ✅ | ❎ | |
3 | ✅ | ❎ | ❎ | |
4 | ❎ | ❎ | ❎ | |
#5 | ❎ | ✅ | #❎ | |
6 | ✅ | ❎ | ❎ | |
7 | ❎ | ❎ | #✅ |
按照上面的表格,因为如果新节点有文本节点,其实老节点不管是什么都会被替换掉,那么就可以按照 新节点 text
是否存在来分类,其实 Vue 源码也是这么来分类的:
if (isUndef(vnode.text)) { // 新虚拟 DOM 有子节点 } else if (oldVnode.text !== vnode.text) { // 如果新虚拟 DOM 是文本节点,直接用 textContent 替换掉 nodeOps.setTextContent(elm, vnode.text) }
那么如果有子节点的话,那应该怎么分类呢?我们可以按照每种情况需要做什么来进行分类,比如说:
textContent
设置为 ''
textContent
设置为 ''
textContent
设置为 ''
后再加入新的子节点那么通过以上六种情况 (新虚拟 DOM 不含有 text,也就是不是文本节点的情况),我们可以很容易地进行归类:
第二种情况
和 第三种情况
。进行的是操作是:把原来 DOM 的 textContent
设置为 ''
第四种情况
和 第六种情况
。进行的是操作是:如果老虚拟 DOM 有 text
,就置空,然后加入新的子节点
第五种情况
。进行的是操作是:需要进行精细比较,即对比新老子节点的不同
其实源码也是这么来进行分类的,而且之前说的 同层比较
也就得出来了,因为每次比较都是比较的同一个父节点每一个子元素 (这里的子元素包括文本节点和子节点) 是否相同,而 深度优先遍历(dfs)
是因为每次比较中,如果该节点有子节点 (这里的子节点指的是有 children 属性,而不包括文本节点) 的话需要进行递归遍历,知道最后到文本节点结束。
⭕️ 这里需要搞清楚子节点和子元素的区别和联系
然后我们来看看源码是怎么写吧,只看新虚拟 DOM 不含有 text,也就是不是文本节点的情况:
if (isUndef(vnode.text)) { if (isDef(oldCh) && isDef(ch)) { if (oldCh !== ch) // 递归处理,精细比较 // 对应分类 3️⃣ updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly) } else if (isDef(ch)) { if (__DEV__) { checkDuplicateKeys(ch) // 可以忽略不看 } // 对应分类 2️⃣ if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '') addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue) } else if (isDef(oldCh)) { // 对应分类 1️⃣ removeVnodes(oldCh, 0, oldCh.length - 1) } else if (isDef(oldVnode.text)) { // 对应分类 1️⃣ nodeOps.setTextContent(elm, '') } }
❓我们可以看到源码把分类 1️⃣ 拆开来了,这是因为如果老虚拟 DOM 有子节,那么可能绑定了一些函数,需要进行解绑等一系列操作,作者也没自信看,大致瞄了一眼,但是如果我们要求不高,如果只是想自己手动实现 Diff 算法,那么没有拆开的必要。
作者觉得这么讲可能比网上其他介绍 Diff 算法的要好,其他的可能直接给你说源码是怎么写的,可能没有说明白为啥这么写,但是通过之前这么分析讲解后可能你对为什么这么写会有更深的理解和帮助吧。
同层比较
因为当都含有子节点,即都包含 children 属性后,需要精细比较不同,不能像之前那些情况一样进行简单处理就可以了
那么这个函数中就会介绍大家经常说的 头头、尾尾、尾头、头尾
比较了,其实这不是 Vue 提出来的,是很早就提出来的算法,就一直沿用至今,大家可以参考【snabbdom 库】
? 在这之前我们要定义四个指针 newStartIdx
、newEndIdx
、oldStartIdx
和 oldEndIdx
,分别指向 新头节点
、新尾节点
、旧头节点
与 旧尾节点
循环条件如下:
while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { ...... }
其实这个比较也就是按人类的习惯来进行比较的,比较顺序如下 :
新头节点
与旧头节点
:++newStartIdx
和 ++oldStartIdx
新尾节点
与旧尾节点
:--newEndIdx
和 --oldEndIdx
新尾节点
与旧头节点
:需要将 旧头节点
移动到 旧尾节点之前
,为什么要这么做,讲起来比较复杂,记住就好,然后 --newEndIdx
和 ++oldStartIdx
新头节点
与旧尾节点
:需要将 旧尾节点
移动到 旧头节点之前
,为什么要这么做,讲起来比较复杂,记住就好,然后 ++newStartIdx
和 --oldEndIdx
新头节点
在旧节点列表 (也就是 children 属性的值) 中进行查找,查找方式按照如下:key
就把 key
在 oldKeyToIdx
进行匹配,oldKeyToIdx
根据旧节点列表中元素的 key
生成对应的下标新头节点
添加到 旧头节点
之前即可旧头节点
之前undefined
根据循环条件我们可以得到两种剩余情况,如下:
oldStartIdx > oldEndIdx
说明老节点先遍历完成,那么新节点比老节点多,就要把 newStartIdx
与 newEndIdx
之间的元素添加newStartIdx > newEndIdx
说明新节点先遍历完成,那么老节点比新节点多,就要把 oldStartIdx
与 oldEndIdx
之间的元素删除其实我们上面还没有考虑如果节点为 undefined
的情况,因为在上面也提到过,如果四种都不匹配后会将该节点置为 undefined
,也只有旧节点列表中才有,因此要在开头考虑这两种情况:
oldStartVnode
为 undefined
:++oldStartIdx
oldEndVnode
为 undefined
:--oldEndIdx
那么我们来看源码怎么写的吧,其中用到的函数可以查看源码附录:
// https://github.com/vuejs/vue/blob/main/src/core/vdom/patch.ts // 439 行至 556 行 while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { if (isUndef(oldStartVnode)) { // 情况 8️⃣ oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left } else if (isUndef(oldEndVnode)) { // 情况 9️⃣ oldEndVnode = oldCh[--oldEndIdx] } else if (sameVnode(oldStartVnode, newStartVnode)) { // 情况 1️⃣ patchVnode(...) oldStartVnode = oldCh[++oldStartIdx] newStartVnode = newCh[++newStartIdx] } else if (sameVnode(oldEndVnode, newEndVnode)) { // 情况 2️⃣ patchVnode(...) oldEndVnode = oldCh[--oldEndIdx] newEndVnode = newCh[--newEndIdx] } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right // 情况 3️⃣ patchVnode(...) canMove && nodeOps.insertBefore( parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm) ) oldStartVnode = oldCh[++oldStartIdx] newEndVnode = newCh[--newEndIdx] } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left // 情况 4️⃣ patchVnode(...) canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm) oldEndVnode = oldCh[--oldEndIdx] newStartVnode = newCh[++newStartIdx] } else { // 情况 5️⃣ if (isUndef(oldKeyToIdx)) // 创建 key -> index 的 Map oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) // 找到 新头节点 的下标 idxInOld = isDef(newStartVnode.key) ? oldKeyToIdx[newStartVnode.key] : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx) if (isUndef(idxInOld)) { // New element // 如果没找到 createElm(...) } else { // 如果找到了 vnodeToMove = oldCh[idxInOld] if (sameVnode(vnodeToMove, newStartVnode)) { patchVnode(...) oldCh[idxInOld] = undefined canMove && nodeOps.insertBefore( parentElm, vnodeToMove.elm, oldStartVnode.elm ) } else { // same key but different element. treat as new element createElm(...) } } newStartVnode = newCh[++newStartIdx] } } if (oldStartIdx > oldEndIdx) { // 情况 6️⃣ refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm addVnodes(...) } else if (newStartIdx > newEndIdx) { // 情况 7️⃣ removeVnodes(...) }
如果问为什么这么比较,回答就是经过很多人很多年的讨论得出的,其实只要记住过程就行了,如果想要更深了解 Diff 算法,可以去 B 站看【尚硅谷】Vue源码解析之虚拟DOM和diff算法
这个问题面试很常见,但是可能大部分人也就只会背八股,没有完全理解,那么经过以上的介绍,我们可以得到自己的理解:
sameVnode
函数判断的,因此可能会有额外 DOM 操作为什么说可能有额外 DOM 操作呢?这个和插入的地方有关,之后会讨论,同理删除也一样
我们分为三个实验:没有 key、key 为 index、key 唯一,仅证明加了 key 可以进行最小化更新操作。
实验代码
有小伙伴评论说可以把代码贴上这样更好,那么作者就把代码附上 ?:
<!DOCTYPE html> <html> <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible" content="IE=edge"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <title>Document</title> <script src="https://cdn.jsdelivr.net/npm/vue@2/dist/vue.js"></script> <style> .box { display: flex; flex-direction: row; } .item { flex: 1; } </style> </head> <body> <div id="app"> <div> <div> <h3>没有 key</h3> <p v-for="(item, index) in list">{{ item }}</p> </div> <div> <h3>key 为 index</h3> <p v-for="(item, index) in list" :key="index">{{ item }}</p> </div> <div> <h3>key 唯一</h3> <p v-for="(item, index) in list" :key="item">{{ item }}</p> </div> </div> <button @click="click1">push(4)</button> <button @click="click2">splice(1, 0, 666)</button> <button @click="click3">unshift(999)</button> <br /><br /> <button @click="click4">pop()</button> <button @click="click5">splice(1, 1)</button> <button @click="click6">shift()</button> </div> <script> var app = new Vue({ el: '#app', data: { show: false, list: [1, 2, 3], }, methods: { click1() { this.list.push(4); }, click2() { this.list.splice(1, 0, 666); }, click3() { this.list.unshift(999); }, click4() { this.list.pop(); }, click5() { this.list.splice(1, 1); }, click6() { this.list.shift(); } }, }) </script> </body> </html>
实验如下所示,我们首先更改原文字,然后点击按钮**「观察节点发生变化的个数」**:
表格为每次实验中,每种情况的最小更新量,假设列表原来的长度为 n
实验 | 没有 key | key 为 index | key 唯一 |
---|---|---|---|
在队尾增加 | 1 | 1 | 1 |
在队中增加 | n - i + 1 | n - i + 1 | 1 |
在队首增加 | n + 1 | n + 1 | 1 |
表格为每次实验中,每种情况的最小更新量,假设列表原来的长度为 n
实验 | 没有 key | key 为 index | key 唯一 |
---|---|---|---|
在队尾删除 | 1 | 1 | 1 |
在队中删除 | n - i | n - i | 1 |
在队首删除 | n | n | 1 |
通过以上实验和表格可以得到加上 key 的性能和最小量更新的个数是最小的,虽然在 在队尾增加
和 在队尾删除
的最小更新量相同,但是之前也说了,如果没有 key 是要循环整个列表查找的,时间复杂度是 O(n),而加了 key 的查找时间复杂度为 O(1),因此总体来说加了 key 的性能要更好。
本文从源码和实验的角度介绍了 Diff 算法,相信大家对 Diff 算法有了更深的了解了,如果有问题可私信交流或者评论区交流,如果大家喜欢的话可以点赞 ➕ 收藏 ?
列举一些源码中出现的简单函数
setTextContent
function setTextContent(node: Node, text: string) { node.textContent = text }
isUndef
function isUndef(v: any): v is undefined | null { return v === undefined || v === null }
isDef
function isDef<T>(v: T): v is NonNullable<T> { return v !== undefined && v !== null }
insertBefore
function insertBefore( parentNode: Node, newNode: Node, referenceNode: Node ) { parentNode.insertBefore(newNode, referenceNode) }
nextSibling
function nextSibling(node: Node) { return node.nextSibling }
createKeyToOldIdx
function createKeyToOldIdx(children, beginIdx, endIdx) { let i, key const map = {} for (i = beginIdx; i <= endIdx; ++i) { key = children[i].key if (isDef(key)) map[key] = i } return map }
以上是深入淺析Vue2中的Diff演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章!