技術之路

站在代碼以外看技術

React Diff算法

關于virtual dom

我們曉得不論是vue照樣react傍邊,都是應用virtual dom(上面簡稱vd)來表現真實的dom,由於操作真實的dom的價值是昂貴的,即便是查找dom節點的操作都是昂貴的,所以在優化的辦法傍邊,就有緩存dom的查找成果的一個優化,那末既然真實dom的操作是昂貴的,所以假如我們在應用diff算法來比擬兩個dom之間的差別的時刻,就要遍曆壹切的dom來停止比較,假如是依照真實的dom來停止diff算法的比擬的話,那末就相當消費機能了,是以vd應運而生。那末怎樣將真實的dom和vd對應起來呢?我們曉得,dom不過乎三個特征:
1、標簽名
2、各類屬性
3、孩子節點
是以,假如要用vd來表現dom的話我們就能夠如許界說。

class VNode {
    constructor(tagName, attributes, children) {
        this.tagName = tagName
        this.attributes = attributes
        this.children = children
    }
}
複制代碼

好比有如許的dom

<div id="div" class="classVal">
    <span>child</span>
</div>
複制代碼

那末vd就是如許的

{
    tagName: 'div',
    attributes: {
        'id': 'div',
        'class': 'classVal'
    },
    children: [{
        tagName: 'span',
        attributes: null,
        children: ['child']
    }]
}
複制代碼

固然,這裏vd的界說少了TEXT節點,所以我們加上TEXT節點,TEXT節點直接前往外面的innerText/textContent,就像下面的children: ['child'],我們界說一個叫h的函數,用來創立vd,包含TEXT節點,它接收四個參數,分離以下:

tagName: 標簽名  
text: 假如是TEXT節點,那末就是TEXT的內容,即innerText/textContent
attributes: dom屬性的價值對  
children: dom的孩子vd
複制代碼
function h(tagName, text, attributes, children) {
    // 斷定到是TEXT節點,直接前往TEXT外面的內容
    if(text) {
        return text
    }
    return new VNode(tagName, attributes, children)
}
複制代碼

好了,VD也許就是如許子表現,那末我們假如依據vd復原成真實的dom呢,其實很簡略,就是依據逐個對應關系復原呗:

function createElement(vnode) {
    var el = null;
    // 文本元素
    if(typeof vnode === "string") {
        el = document.createTextNode(vnode);
        return el;
    }
    // 復原dom
    el = document.createElement(vnode.tagName);
    // 復原attribute
    for(var key in attributes) {
        el.setAttribute(key, attributes[key]);
    }
    // 復原孩子節點
    var children = vnode.children.map(createElement);
    children.forEach(function(child) {
        el.appendChild(child);
    });
    return el;
}
複制代碼

關于vd的懂得差不多就如許,假如有須要彌補的或許斧正的,望不惜賜教。

diff算法

有了vd後,我們要怎樣比擬兩個dom樹之間的分歧呢,固然不克不及無腦的應用innerHTML對整塊樹更新(backbone就是如許),而是針對更改的處所停止更新或許調換,那末我們就須要依附diff來找出兩棵樹之間的分歧。
傳統的diff算法,是須要跨級比較兩個樹之間的分歧,時光龐雜度爲O(n^3),如許的比較是沒法接收的,所以react提出了一個簡略粗魯的diff算法,只比較同級元素,如許算法龐雜度就釀成了O(n)了,固然不克不及做到最優的更新,然則時光龐雜度大大削減,是一種均衡的算法,上面會提到。

《React Diff算法》

那末怎樣懂得它是只比較同級和詳細它是怎樣比較的呢?
基于diff算法的同級比較,我們先講下比較的過程當中,它重要分爲四品種型的比較,分離爲:
1、新建create: 新的vd中有這個節點,舊的沒有
2、刪除remove: 新的vd中沒有這個節點,舊的有
3、調換replace: 新的vd的tagName和舊的tagName分歧
4、更新update: 除下面三點外的分歧,詳細是比擬attributes先,然後再比擬children
寫成代碼就是如許:

diff(newVnode, oldVNode) {
    
    if(!newVNode) {
        // 新節點中沒有,解釋是刪除舊節點的
        return {
            type: 'remove'
        }
    } else if(!oldVNode) {
        // 新節點中有舊節點沒有的,解釋是刪除
        return {
            type: 'create',
            newVNode
        }
    } else if(isDiff(newVNode, oldVNode)) {
        // 只需比較出兩個節點的tagName分歧,解釋是調換
        return {
            type: 'replace',
            newVNode
        }
    } else {
        // 其他情形是更新節點,要比較兩個節點的attributes和孩子節點
        return {
            type: 'update',
            attributes: diffAttributes(newVNode, oldVNode),
            children: diffChildren(newVNode, oldVNode)
        }
    }
}

// 比較孩子節點,其實就是遍曆壹切的孩子節點,然後挪用diff比較
function diffChildren(newVnode, oldVNode) {
    var patches = []
    // 這裏要獲得兩個節點中的最大孩子數,然後再停止比較 
    var len = Math.max(newVnode.children.length, oldVNode.children.length);
    for(let i = 0; i <len; i++) {
        patches[i] = diff(newVnode.children[i], oldVnode.children[i])
    }
    return patches
}

// 比較attribute,只要兩種情形,要不就是值轉變/新建,要不就是刪除值,比較dom只要setAttribute和removeAttribute就曉得了
function diffAttributes(newVnode, oldVNode) {
    var patches = []
    // 獲得新舊節點的壹切attributes
    var attrs = Object.assign({}, oldVNode.attributes, newVNode.attributes)
    for(let key in attrs) {
        let value = attrs[key]
        // 只需新節點的屬性值和久節點的屬性值分歧,就斷定爲新建,不論是更新和真實的新定都是挪用setAttribute來更新
        if(oldVNode.attributes[key] !== value) {
            patches.push({
                type: 'create',
                key,
                value: newVnode.attributes[key]
            })
        } else if(!newVNode.attributes[key]) {
            patches.push({
                key,
                type: 'remove'
            })
        }
    }
    return patches
}

// 斷定兩個節點能否分歧
function isDiff(newVNode, oldVNode) {
    // 正常情形下,只比較tagName,然則text節點比較沒有tagName,所以要斟酌text節點
    return (typeof newVNode === 'string' && newVNode !== oldVNode) 
    || (typeof oldVNode === 'string' && newVNode !== oldVNode) 
    || newVNode.tagName !== oldVNode.tagName
}
複制代碼

聯合代碼,人人比較上面的圖,圖外面remove沒有列出來,remove和create差不多緣由,信任人人曉得甚麽情形下是remove。

《React Diff算法》

上圖,按傳統的辦法只是在span和p直接拔出了一個div,然則diff算法不是這麽來更新的,它只比較統壹級其余,即會認為舊節點的p和新節點的div才是統壹級,他們的tagName分歧,所以界說爲replace,接著把舊節點的div算作和新節點的p是統壹級,照舊是replace,最初舊節點沒有div,所以create了。可以看到,其實這個更新價值照樣比擬大的,然則比對的進程卻簡略和疾速,是以是一種絕對均衡的算法。完全的代碼人人可以看下我的git地址:github.com/VikiLee/XLM…

總結

我們更新dom的時刻,盡可能不要整棵樹停止更新,須要做到細顆粒的更新,要做到細顆粒地更新就必需曉得兩棵樹直接的分歧,所以須要應用diff算法來停止比較,然則傳統的diff算法固然能做到細顆粒精確地更新,然則它須要花消大批的時光來停止比對,所以有來react的改版的diff算法,只比擬統壹級的元素,如許可以做到疾速的比對,爲O(n),即便如許,在比較兩棵樹的時刻,我們照樣須要遍曆壹切的節點,我們曉得dom的操作是昂貴的,即便是查找,也是昂貴的一個進程,特殊是在節點許多的donm樹下,所以虛擬dom應運而生,虛擬dom避開了直接操作dom的缺陷,而是直接比較內存中vd,使得比較速度進一步獲得質地晉升。

作者:大雄沒了哆啦A夢
鏈接:https://juejin.im/post/6844903762859917320
起源:掘金
著作權歸作者壹切。貿易轉載請聯系作者取得受權,非貿易轉載請注明出處。

點贊

揭櫫評論

電子郵件地址不會被公開。 必填項已用*標注