摘要:原文地址此篇結合我最近造的小輪子進行分析,其中的算法主要參考庫。如果其中一方?jīng)]有子節(jié)點,那么進行刪除或添加。判斷是否一方已遍歷完,對真實進行相應的刪減或添加。
原文地址:https://github.com/HolyZheng/...virtual dom 什么是virtual dom
此篇結合我最近造的小輪子hoz進行分析,其中的virtual dom算法主要參考snabbdom庫。
virtual dom的本質(zhì)是一個用來映射真實dom的JavaScript對象,比如
// hoz庫中的 src/vdom/vnode.js class VNode { constructor (sel, tagName, id, className, el, children, data, text, key) { this.tagName = tagName // DIV this.sel = sel // div#id.class this.id = id // id this.className = className // [] this.children = children // [] this.el = el // node this.data = data // {} this.key = key this.text = text } }
通過一個vnode對象去對應一個dom元素,vnode的屬性對應反映dom元素的屬性。然后我們可以定義一個toVnode方法,把一個dom tree轉為virtual dom tree。
// hoz庫中 src/vdom/toVnode.js import VNode from "./vnode" import * as utils from "./is" function toVnode (node, utilsTool) { const api = (utilsTool === undefined ? utils : utilsTool) // 自定義的一些工具 let text // 判斷是否為node節(jié)點,不是拋出錯誤 if (!node) { throw new Error("Please make sure you have pass the argument "node" in to function toVnode") } // 如果是element類型節(jié)點 if (api.isElement(node)) { // 收集該節(jié)點各屬性信息,這里實現(xiàn)方式比較多,只要獲取到需要的足夠的信息就行了 // 這里獲取了id,類名cn,類名數(shù)組ca,類字符串如 .classA.classB,sel 等等 const id = node.id ? node.id : "" const cn = node.getAttribute("class") const ca = cn ? cn.split(" ") : null // classArray const c = cn ? "." + cn.split(" ").join(".") : "" // .classA.classB const sel = node.tagName.toLowerCase() + "#" + id + c const attrs = {} const elmAttrs = node.attributes const elmChildren = node.childNodes const children = elmChildren.length ? [] : null const tag = node.tagName let i, n for (i = 0, n = elmAttrs.length; i < n; i++) { if (elmAttrs[i].nodeName !== "class" && elmAttrs[i].nodeName !== "id") { // id 和 class例外處理 attrs[elmAttrs[i].nodeName] = elmAttrs[i].nodeValue } } // 如果給節(jié)點指定了key屬性,則獲取key的值 const key = attrs.key ? attrs.key : undefined // 如果有子節(jié)點,對子節(jié)點遞歸調(diào)用toVnode方法 for (i = 0, n = elmChildren.length; i < n; i++) { children.push(toVnode(elmChildren[i], api)) } return new VNode(sel, tag, id, ca, node, children, attrs, undefined, key) // 文本節(jié)點 } else if (api.isText(node)) { text = node.textContent return new VNode(undefined, undefined, undefined, undefined, node, undefined, undefined, text, undefined) // 注釋節(jié)點 } else if (api.isComment(node)) { text = node.textContent return new VNode("commont", undefined, undefined, undefined, node, undefined, undefined, text, undefined) } else { return new VNode("", undefined, undefined, undefined, node, undefined, undefined, undefined, undefined) } } export default toVnode
toVnode方法說白了就是,判斷當前節(jié)點類型,創(chuàng)建對應類型的vnode,然后如果有子節(jié)點的話,對子節(jié)點遞歸調(diào)用toVnode方法,將子節(jié)點也轉為vnode,執(zhí)行結束后,我們就可以得到一棵以傳入節(jié)點為根節(jié)點的virtual dom tree了。
到這里我們已經(jīng)有了一個映射真實dom的virtual dom類(vnode),以及一個將dom轉為virtual dom方法(toVnode)
diff算法接下來到了關鍵的diff算法,diff算法就是用來對比新舊兩個vnode,計算出最小的修改單位,去操作更新真實的dom。下面是一張解釋diff流程的經(jīng)典圖,我相信你不是第一次看到
diff會算法會在同一層比較新舊兩個vnode,從而將算法復雜度降低到O(n)。hoz庫中diff算法的實現(xiàn)在patch.js文件中,這里面有幾個關鍵的函數(shù)
/** * 比較新老節(jié)點,相同則進行patchVnode,不同的話在真實dom上 * 用新的節(jié)點,取代舊的節(jié)點。 */ export default function patch (oldVnode, vnode) { if (sameVnode(oldVnode, vnode)) { patchVnode(oldVnode, vnode) } else { const oldElement = oldVnode.el let parentElement = api.parentNode(oldElement) createElm(vnode) if (parentElement !== null) { api.insertBefore(parentElement, vnode.el, api.nextSibling(oldElement)) api.removeChild(parentElement, oldVnode.el) } } return vnode }
第一個關鍵函數(shù)就是我們diff算法的入口函數(shù)patch方法,該方法負責,判斷oldVnode,和vnode是否為同一節(jié)點,如果是,調(diào)用patchVnode方法,進一步比較處理,不是的話,用新節(jié)點代替就節(jié)點。
ps:通過sameVnode進行判斷
function sameVnode (oldVnode, vnode) { return vnode.key === oldVnode.key && vnode.tagName === oldVnode.tagName // 這里可按自己需要進行比較 }patchVnode
上面提到,如果是同一節(jié)點的話,就會進入到patchVnode方法中
function patchVnode (oldVnode, vnode) { const element = vnode.el = oldVnode.el let oldCh = oldVnode.children let ch = vnode.children // 如果相同,不需要比較 if (oldVnode === vnode) { console.log("oldVnode === vnode") return } if (oldVnode.text !== null && vnode.text !== null && oldVnode.text !== vnode.text) { api.setTextContent(element, vnode.text) } else { // 更新element的className, id, 和其他屬性 updateElm(element, vnode) if (oldCh && ch && oldCh !== ch) { updateChildren(element, oldCh, ch) } else if (ch) { // 新vnode有子節(jié)點,oldvnode沒有子節(jié)點,給element添加子節(jié)點 addVnodes(element, null, ch, 0, ch.length - 1) } else if (oldCh) { // 新vnode沒有子節(jié)點,oldvnode有子節(jié)點,給element刪除子節(jié)點 removeVnodes(element, oldCh, 0, oldCh.length - 1) } } }
patchVnode方法的任務就是
比較oldVnode與vnode,如果兩者完全相同,沒有變化的話,直接return。不同的話,用新的vnode去更新oldVnode。
比較它們的子節(jié)點,如果都由子節(jié)點,調(diào)用updateChildren去比較它們的子節(jié)點。
如果其中一方?jīng)]有子節(jié)點,那么進行dom刪除或添加。
添加節(jié)點:通過addVnode,遍歷vnode子節(jié)點,調(diào)用createElm創(chuàng)建真實dom,插入到真實dom中。
刪除節(jié)點:通過removeVnode,遍歷oldvnode,并從真實dom中刪除。
updateChildren剛剛說到,如果它們都有子節(jié)點,那么會調(diào)用updateChildren去繼續(xù)比較它們的子節(jié)點,updateChildren是這里的難點,可以說,最復雜的操作就是這一步,代碼
function updateChildren (parentElm, oldCh, newCh) { let oldStartIdx = 0 let newStartIdx = 0 let oldEndIdx = oldCh.length - 1 let newEndIdx = newCh.length - 1 let oldStartVnode = oldCh[0] let newStartVnode = newCh[0] let oldEndVnode = oldCh[oldEndIdx] let newEndVnode = newCh[newEndIdx] let oldKeyToIdx let idxInOld let emlToMove let before while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { // oldStartIdx 與 oldEndIdx 與 newStartIdx 與 newEndIdx 之間四中比較 // 簡單的判斷子節(jié)點的移位 if (oldStartVnode == null) { oldStartVnode = oldCh[++oldStartIdx] } else if (oldEndVnode == null) { oldEndVnode = oldCh[--oldEndIdx] } else if (newStartVnode == null) { newStartVnode = newCh[++newStartIdx] } else if (newEndVnode == null) { newEndVnode = newCh[--newEndIdx] } else if (sameVnode(oldStartVnode, newStartVnode)) { patchVnode(oldStartVnode, newStartVnode) oldStartVnode = oldCh[++oldStartIdx] newStartVnode = newCh[++newStartIdx] } else if (sameVnode(oldEndVnode, newEndVnode)) { patchVnode(oldEndVnode, newEndVnode) oldEndVnode = oldCh[--oldEndIdx] newEndVnode = newCh[--newEndIdx] } else if (sameVnode(oldStartVnode, newEndVnode)) { patchVnode(oldStartVnode, newEndVnode) api.insertBefore(parentElm, oldStartVnode.el, api.nextSibling(oldEndVnode.el)) oldStartVnode = oldCh[++oldStartIdx] newEndVnode = newCh[--newEndIdx] } else if (sameVnode(oldEndVnode, newStartVnode)) { patchVnode(oldEndVnode, newStartVnode) api.insertBefore(parentElm, oldEndVnode.el, oldStartVnode.el) oldEndVnode = oldCh[--oldEndIdx] newStartVnode = newCh[++newStartIdx] } else { if (oldKeyToIdx === undefined) { oldKeyToIdx = createKeyToOldIndex(oldCh, oldStartIdx, oldEndIdx) } idxInOld = oldKeyToIdx[newStartVnode.key] // idx 不存在,說明該節(jié)點是新增的,原來沒有的,故創(chuàng)建一個新節(jié)點,并插入 if (!idxInOld) { api.insertBefore(parentElm, createElm(newStartVnode), oldStartVnode.el) newStartVnode = newCh[++newStartIdx] } else { emlToMove = oldCh[idxInOld] // sel 不同的話,證明也是一個原來沒有的節(jié)點,所以創(chuàng)建并插入 if (emlToMove.sel !== newStartVnode.sel) { api.insertBefore(parentElm, createElm(newStartVnode), oldStartVnode.el) } else { patchVnode(emlToMove, newStartVnode) oldCh[idxInOld] = null api.insertBefore(parentElm, emlToMove.el, oldStartVnode.el) } newStartVnode = newCh[++newStartIdx] } } } // 這是oldVnode已經(jīng)遍歷完,vnode還沒有,說明vnode比oldVnode節(jié)點多,所以將多出的節(jié)點創(chuàng)建并插入 if (oldStartIdx > oldEndIdx) { before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].el addVnodes(parentElm, before, newCh, newStartIdx, oldEndIdx) } else { removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx) } }
下面圖反映了updateChildren的運作方式
將oldStartIdx,oldEndIdx,newStartIdx,newEndIdx分別指向同層新舊vnode的首尾,然后隨著比較而逐漸往中間移動,對4個節(jié)點進行比較,會有4種比較結果,(oldStartIdx和newStartIdx或newEndIdx指向同一節(jié)點,oldEndIdx和newStartIdx或newEndIdx指向同一節(jié)點這四種),根據(jù)4個節(jié)點的的4種比較結果做相應的操作,比如當出現(xiàn)oldStartIdx和newStartIdx指向同一節(jié)點這個結果時,表示這個節(jié)點不需要進行移位操作,直接調(diào)用patchVnode進行進一步比較,又比如出現(xiàn)oldStartIdx和newEndIdx指向同一節(jié)點這一結果,那么表示oldStartIdx指向的節(jié)點需要移動到oldEndIdx后面去,然后再對他們調(diào)用patchVnode進行進一步比較。
如果4種結果都不是,調(diào)用createKeyToOldIndex 方法,創(chuàng)建一個key與oldIndex之間的映射的map,查看newStartVnode.key是否有對應的oldVnode,如果有,說明oldvnode移動到了oldStartVnode前面,然后將對應的oldVnode插入到oldStartVnode前面,如果沒有,說明在當前newStartVnode是新創(chuàng)建得節(jié)點,在oldStartVnode前面插入該節(jié)點。
判斷是否一方已遍歷完,對真實dom進行相應的刪減或添加。
這就是diff得大致流程了。
文章版權歸作者所有,未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/95821.html
摘要:算法的本質(zhì)是對傳統(tǒng)遍歷算法的優(yōu)化策略用三大策略將復雜度轉化為復雜度策略一中節(jié)點跨層級的移動操作特別少,可以忽略不計。當節(jié)點處于同一層級時,提供三種節(jié)點操作刪除插入移動。在舊的節(jié)點中的,它的,不滿足的條件,因此不做移動操作。 一、react diff算法 diff算法的作用 計算出Virtual DOM中真正變化的部分,并只針對該部分進行原生DOM操作,而非重新渲染整個頁面。 傳統(tǒng)di...
摘要:對同一層級的子節(jié)點進行處理時,會根據(jù)進行簡要的復用。二性能優(yōu)化方案由于中性能主要耗費在于階段的算法,因此性能優(yōu)化也主要針對算法。此時最常用的優(yōu)化方案即為方法。或者直接使用,原理一致。 一、從React原理談起 react是什么? showImg(https://segmentfault.com/img/bVbcYvf?w=1140&h=384); react是用于構建用戶界面的JS框架...
摘要:對同一層級的子節(jié)點進行處理時,會根據(jù)進行簡要的復用。或者直接使用,原理一致。 一、從React原理談起 react是什么? showImg(https://segmentfault.com/img/bVbcYvf?w=1140&h=384); react是用于構建用戶界面的JS框架。因此react只負責解決view層的渲染。 react做了什么? Virtual Dom模型 生命周期...
摘要:毫無疑問的是算法的復雜度與效率是決定能夠帶來性能提升效果的關鍵因素。速度略有損失,但可讀性大大提高。因此目前的主流算法趨向一致,在主要思路上,與的方式基本相同。在里面實現(xiàn)了的算法與支持。是唯一添加的方法所以只發(fā)生在中。 VirtualDOM是react在組件化開發(fā)場景下,針對DOM重排重繪性能瓶頸作出的重要優(yōu)化方案,而他最具價值的核心功能是如何識別并保存新舊節(jié)點數(shù)據(jù)結構之間差異的方法,...
摘要:傳統(tǒng)算法通過循環(huán)遞歸對節(jié)點進行依次對比,效率低下,算法復雜度達到,其中是樹中節(jié)點的總數(shù)。對于同一層級的一組子節(jié)點,它們可以通過唯一進行區(qū)分。當發(fā)現(xiàn)節(jié)點已經(jīng)不存在,則該節(jié)點及其子節(jié)點會被完全刪除掉,不會用于進一步的比較。 https://zhuanlan.zhihu.com/p/... React diff 會幫助我們計算出 Virtual DOM 中真正變化的部分,并只針對該部分進行實...
閱讀 1076·2021-11-22 14:56
閱讀 1520·2019-08-30 15:55
閱讀 3359·2019-08-30 15:45
閱讀 1655·2019-08-30 13:03
閱讀 2868·2019-08-29 18:47
閱讀 3334·2019-08-29 11:09
閱讀 2641·2019-08-26 18:36
閱讀 2615·2019-08-26 13:55