diff算法和react

react是一個(gè)高效的前端框架凰荚,它的高效體現(xiàn)在對(duì)于DOM元素的修改上面整吆,對(duì)比直接操作DOM的原生或者jquery方法牢裳,它的優(yōu)秀之處在于對(duì)DOM元素的查找上面着饥。

想象一下,如果讓你去查找老顏我在我們這個(gè)姓氏宗譜(祈求祖先們的原諒)從唐代到2018年我所在的位置龄广,你會(huì)怎么查硫眯,指不準(zhǔn)你會(huì)從我這個(gè)位置,去看我爸爸的位置择同,然后從我爸爸的位置再去看我爺爺?shù)奈恢昧饺搿!G貌拧裹纳!?/p>

但是,如果你只是知道有我這個(gè)人归斤,卻不知道我在我們家偉大的族譜中哪個(gè)位置痊夭,并且有個(gè)大佬告訴你我們這個(gè)姓氏在唐代的那個(gè)祖先,那想一想脏里,你指不準(zhǔn)會(huì)從我的祖先開始一個(gè)一個(gè)的遍歷他的所有后代她我,想象一下,粗略算一下,假設(shè)從唐代開始番舆,一共有n個(gè)人存在族譜樹上酝碳,那么你大概需要O(n^3)的時(shí)間復(fù)雜度(你肯定沒看過算法,所以你就忽略O(shè)()恨狈,看n^3就夠了)疏哗,假設(shè)這個(gè) n=1000,再假設(shè)你每看一個(gè)人禾怠,你就能記住他的位置返奉,而且你只需要1秒鐘,那么你就需要1000*1000*1000=1000000000吗氏,10億秒芽偏,(?'-')?加油,有興趣你可以算算要多長(zhǎng)時(shí)間:)弦讽,可以說這就是我們實(shí)際用原生js方法去找一個(gè)元素的過程污尉!

這太tnd可怕了,所以react提出了虛擬DOM這個(gè)東西往产!

好了我們來看看被碗,diff

react diff算法

1. diff策略

下面介紹一下react diff算法的3個(gè)策略

Web UI 中DOM節(jié)點(diǎn)跨層級(jí)的移動(dòng)操作特別少,可以忽略不計(jì)

擁有相同類的兩個(gè)組件將會(huì)生成相似的樹形結(jié)構(gòu)仿村,擁有不同類的兩個(gè)組件將會(huì)生成不同的樹形結(jié)構(gòu)锐朴。

對(duì)于同一層級(jí)的一組子節(jié)點(diǎn),它們可以通過唯一id進(jìn)行區(qū)分奠宜。

對(duì)于以上三個(gè)策略包颁,react分別對(duì)tree diff,component diff,element diff進(jìn)行算法優(yōu)化。

2.tree diff

基于策略一压真,WebUI中DOM節(jié)點(diǎn)跨層級(jí)的移動(dòng)操作少的可以忽略不計(jì),React對(duì)Virtual DOM樹進(jìn)行層級(jí)控制蘑险,只會(huì)對(duì)相同層級(jí)的DOM節(jié)點(diǎn)進(jìn)行比較滴肿,即同一個(gè)父元素下的所有子節(jié)點(diǎn),當(dāng)發(fā)現(xiàn)節(jié)點(diǎn)已經(jīng)不存在了佃迄,則會(huì)刪除掉該節(jié)點(diǎn)下所有的子節(jié)點(diǎn)泼差,不會(huì)再進(jìn)行比較。這樣只需要對(duì)DOM樹進(jìn)行一次遍歷呵俏,就可以完成整個(gè)樹的比較堆缘。復(fù)雜度變?yōu)镺(n);

疑問:當(dāng)我們的DOM節(jié)點(diǎn)進(jìn)行跨層級(jí)操作時(shí),diff會(huì)有怎么樣的表現(xiàn)呢普碎?

如下圖所示吼肥,A節(jié)點(diǎn)及其子節(jié)點(diǎn)被整個(gè)移動(dòng)到D節(jié)點(diǎn)下面去,由于React只會(huì)簡(jiǎn)單的考慮同級(jí)節(jié)點(diǎn)的位置變換,而對(duì)于不同層級(jí)的節(jié)點(diǎn)缀皱,只有創(chuàng)建和刪除操作斗这,所以當(dāng)根節(jié)點(diǎn)發(fā)現(xiàn)A節(jié)點(diǎn)消失了,就會(huì)刪除A節(jié)點(diǎn)及其子節(jié)點(diǎn)啤斗,當(dāng)D發(fā)現(xiàn)多了一個(gè)子節(jié)點(diǎn)A表箭,就會(huì)創(chuàng)建新的A作為其子節(jié)點(diǎn)。

此時(shí)钮莲,diff的執(zhí)行情況是:

createA-->createB-->createC-->deleteA

圖片發(fā)自簡(jiǎn)書App


由此可以發(fā)現(xiàn)免钻,當(dāng)出現(xiàn)節(jié)點(diǎn)跨層級(jí)移動(dòng)時(shí),并不會(huì)出現(xiàn)想象中的移動(dòng)操作崔拥,而是會(huì)進(jìn)行刪除伯襟,重新創(chuàng)建的動(dòng)作,這是一種很影響React性能的操作握童。因此官方也不建議進(jìn)行DOM節(jié)點(diǎn)跨層級(jí)的操作姆怪。

3.componnet diff

React是基于組件構(gòu)建應(yīng)用的,對(duì)于組件間的比較所采用的策略也是非常簡(jiǎn)潔和高效的澡绩。

如果是同一個(gè)類型的組件稽揭,則按照原策略進(jìn)行Virtual DOM比較。

如果不是同一類型的組件肥卡,則將其判斷為dirty component溪掀,從而替換整個(gè)組價(jià)下的所有子節(jié)點(diǎn)。

如果是同一個(gè)類型的組件步鉴,有可能經(jīng)過一輪Virtual DOM比較下來揪胃,并沒有發(fā)生變化。如果我們能夠提前確切知道這一點(diǎn)氛琢,那么就可以省下大量的diff運(yùn)算時(shí)間喊递。因此,React允許用戶通過shouldComponentUpdate()來判斷該組件是否需要進(jìn)行diff算法分析阳似。

如下圖所示骚勘,當(dāng)組件D變?yōu)榻M件G時(shí),即使這兩個(gè)組件結(jié)構(gòu)相似撮奏,一旦React判斷D和G是不用類型的組件俏讹,就不會(huì)比較兩者的結(jié)構(gòu),而是直接刪除組件D畜吊,重新創(chuàng)建組件G及其子節(jié)點(diǎn)泽疆。雖然當(dāng)兩個(gè)組件是不同類型但結(jié)構(gòu)相似時(shí),進(jìn)行diff算法分析會(huì)影響性能玲献,但是畢竟不同類型的組件存在相似DOM樹的情況在實(shí)際開發(fā)過程中很少出現(xiàn)殉疼,因此這種極端因素很難在實(shí)際開發(fā)過程中造成重大影響梯浪。

圖片發(fā)自簡(jiǎn)書App

4.element diff

當(dāng)節(jié)點(diǎn)屬于同一層級(jí)時(shí),diff提供了3種節(jié)點(diǎn)操作株依,分別為INSERT_MARKUP(插入)驱证,MOVE_EXISTING(移動(dòng)),REMOVE_NODE(刪除)。

INSERT_MARKUP:新的組件類型不在舊集合中恋腕,即全新的節(jié)點(diǎn)抹锄,需要對(duì)新節(jié)點(diǎn)進(jìn)行插入操作。

MOVE_EXISTING:舊集合中有新組件類型荠藤,且element是可更新的類型伙单,這時(shí)候就需要做移動(dòng)操作,可以復(fù)用以前的DOM節(jié)點(diǎn)哈肖。

REMOVE_NODE:舊組件類型吻育,在新集合里也有,但對(duì)應(yīng)的element不同則不能直接復(fù)用和更新淤井,需要執(zhí)行刪除操作布疼,或者舊組件不在新集合里的,也需要執(zhí)行刪除操作币狠。


注:diff算法來源于https://blog.csdn.net/qq_26708777

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末游两,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子漩绵,更是在濱河造成了極大的恐慌贱案,老刑警劉巖,帶你破解...
    沈念sama閱讀 211,376評(píng)論 6 491
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件止吐,死亡現(xiàn)場(chǎng)離奇詭異宝踪,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)碍扔,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,126評(píng)論 2 385
  • 文/潘曉璐 我一進(jìn)店門瘩燥,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人蕴忆,你說我怎么就攤上這事颤芬。” “怎么了套鹅?”我有些...
    開封第一講書人閱讀 156,966評(píng)論 0 347
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)汰具。 經(jīng)常有香客問我卓鹿,道長(zhǎng),這世上最難降的妖魔是什么留荔? 我笑而不...
    開封第一講書人閱讀 56,432評(píng)論 1 283
  • 正文 為了忘掉前任吟孙,我火速辦了婚禮澜倦,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘杰妓。我一直安慰自己藻治,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,519評(píng)論 6 385
  • 文/花漫 我一把揭開白布巷挥。 她就那樣靜靜地躺著桩卵,像睡著了一般。 火紅的嫁衣襯著肌膚如雪倍宾。 梳的紋絲不亂的頭發(fā)上雏节,一...
    開封第一講書人閱讀 49,792評(píng)論 1 290
  • 那天,我揣著相機(jī)與錄音高职,去河邊找鬼钩乍。 笑死,一個(gè)胖子當(dāng)著我的面吹牛怔锌,可吹牛的內(nèi)容都是我干的寥粹。 我是一名探鬼主播,決...
    沈念sama閱讀 38,933評(píng)論 3 406
  • 文/蒼蘭香墨 我猛地睜開眼埃元,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼涝涤!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起亚情,我...
    開封第一講書人閱讀 37,701評(píng)論 0 266
  • 序言:老撾萬榮一對(duì)情侶失蹤妄痪,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后楞件,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體衫生,經(jīng)...
    沈念sama閱讀 44,143評(píng)論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,488評(píng)論 2 327
  • 正文 我和宋清朗相戀三年土浸,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了罪针。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 38,626評(píng)論 1 340
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡黄伊,死狀恐怖泪酱,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情还最,我是刑警寧澤墓阀,帶...
    沈念sama閱讀 34,292評(píng)論 4 329
  • 正文 年R本政府宣布,位于F島的核電站拓轻,受9級(jí)特大地震影響斯撮,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜扶叉,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,896評(píng)論 3 313
  • 文/蒙蒙 一勿锅、第九天 我趴在偏房一處隱蔽的房頂上張望帕膜。 院中可真熱鬧,春花似錦溢十、人聲如沸垮刹。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,742評(píng)論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)荒典。三九已至,卻和暖如春乌庶,著一層夾襖步出監(jiān)牢的瞬間种蝶,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 31,977評(píng)論 1 265
  • 我被黑心中介騙來泰國(guó)打工瞒大, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留螃征,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 46,324評(píng)論 2 360
  • 正文 我出身青樓透敌,卻偏偏與公主長(zhǎng)得像盯滚,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子酗电,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,494評(píng)論 2 348

推薦閱讀更多精彩內(nèi)容