一垃瞧、讀懂diff
diff是Unix/Linux系統(tǒng)的一個(gè)很重要的工具程序预鬓。
它用來比較兩個(gè)文本文件的差異，是代碼版本管理的基石之一鞭盟。
diff <文件1> <文件2>
diff就會(huì)告訴你圾结，這兩個(gè)文件有何差異。
1. diff的三種格式
- 正常格式
- 上下文格式
- 合并格式
2. 創(chuàng)建示例文件
touch test1
vim test1 //寫入12345
cat test1
cp test1 test2
vim test2//修改5位6 12346
cat test2
3. 正常格式
diff test1 test2
解析：
-
5c5：用來說明改變的位置懊缺。前面的5表示第一個(gè)文件第5行改變疫稿，a（add）,c（change）,d（delete）。后面的5表示第二個(gè)文件變動(dòng)行鹃两。 -
< 5：前面的小于號(hào)遗座，表示要從test1當(dāng)中刪除的內(nèi)容。 -
---：test1和test2的分割線俊扳。 -
> 6：前面的大于號(hào)途蒋，表示要從test2當(dāng)中增加該內(nèi)容。
4. 上下文格式
上面的結(jié)果顯示太簡(jiǎn)單不易理解馋记，所以加入上下文的方式号坡。它的使用方法是加入c參數(shù)（代表context）
為了更明顯的顯示上下文的效果 我們把文件改成如下內(nèi)容：
diff -c test1 test2
解析：
-
***：表示修改前的文件懊烤。 -
---：表示修改后的文件。 -
6,13：表示顯示的行6-13行宽堆。這時(shí)不僅顯示發(fā)生變化的行內(nèi)容腌紧，變化內(nèi)容前面三行和后面三行。 - 另外畜隶，文件內(nèi)容的每一行最前面壁肋，還有一個(gè)標(biāo)記位。
如果為空籽慢，表示該行無變化浸遗；
如果是感嘆號(hào)（!），表示該行有改動(dòng)箱亿；
如果是減號(hào)（-）跛锌，表示該行被刪除；
如果是加號(hào)（+）届惋，表示該行為新增髓帽。
5. 合并格式
如果兩個(gè)文件相似度很高，那么上下文格式的diff盼樟，將顯示大量重復(fù)的內(nèi)容氢卡，比較浪費(fèi)空間。
使用方式加一個(gè)參數(shù)u
diff -u test1 test2
6. git格式的diff
版本管理系統(tǒng)git晨缴，使用的是合并格式diff的變體译秦。
git diff
解析：
- 進(jìn)行比較的是，a版本的test1（即變動(dòng)前）和b版本的test2（即變動(dòng)后）击碗。
- 第二行表示兩個(gè)版本的git哈希值（index區(qū)域的fcb0de4對(duì)象筑悴，與工作目錄區(qū)域的1e628d3對(duì)象進(jìn)行比較），最后的六位數(shù)字是對(duì)象的模式（普通文件稍途，644權(quán)限 讀寫-讀-讀 =>屬主-組成員-其他用戶）阁吝。
7. diff程序原理
在diff里面，我們比較的兩個(gè)文件叫做old和new械拍，而一般是按行來比較突勇。這里我們可以抽象成一個(gè)字符串的比較，比如：
old: abc
new: abcd
那么其中的每一個(gè)字符都可以表示文件里面的一行坷虑。那么diff里面用到的比較思想是從old和new里面找出最長(zhǎng)的subsequence樟插。這是基于LCS（Longest Common Subsequnece）算法柠座。
子序列的概念是......舉例說明吧：
a b c d e f g h i
a b c h d f g ij
那么最長(zhǎng)公共子序列就是：abcdfgi（不需要連續(xù)）戳吝。
lcs = (A, B) ->
result = 0
if A.length is 0 or B.length is 0
result
else if A[0] is B[0]
result = 1 + lcs(A[1..], B[1..])
else
result = Math.max(lcs(A, B[1..]), lcs(A[1..], B))
使用遞歸來計(jì)算最長(zhǎng)的相似元素的長(zhǎng)度澜掩。
矩陣的列是old,橫坐標(biāo)是new
二、首先了解一下虛擬DOM
1. 對(duì)前端狀態(tài)管理的小總結(jié)
在最開始我們對(duì)于狀態(tài)改變更新對(duì)應(yīng)的視圖，都是操作dom痊远。但是對(duì)于復(fù)雜的應(yīng)用程序來說垮抗，無疑這是很低效率，不便于維護(hù)的碧聪。
于是冒版，出現(xiàn)了MVC等架構(gòu)模式，希望能從代碼組織方式來降低維護(hù)這種復(fù)雜應(yīng)用程序的難度矾削。但是 MVC 架構(gòu)沒辦法減少你所維護(hù)的狀態(tài)壤玫，也沒有降低狀態(tài)更新你需要對(duì)頁面的更新操作（前端來說就是DOM操作），你需要操作的DOM還是需要操作哼凯，只是換了個(gè)地方。
于是楚里，后來人們想出了 MVVM 模式断部，只要在模版中聲明視圖組件是和什么狀態(tài)進(jìn)行綁定的，雙向綁定引擎就會(huì)在狀態(tài)更新的時(shí)候自動(dòng)更新視圖班缎。
MVVM 可以很好的降低我們維護(hù)狀態(tài) -> 視圖的復(fù)雜程度蝴光。但是這不是唯一的辦法，還有一個(gè)非常直觀的方法达址，可以大大降低視圖更新的操作：一旦狀態(tài)發(fā)生了變化蔑祟，就用模版引擎重新渲染整個(gè)視圖，然后用新的視圖更換掉舊的視圖沉唠。最大的問題就是這樣做會(huì)很慢疆虚，因?yàn)榧词挂粋€(gè)小小的狀態(tài)變更都要重新構(gòu)造整棵 DOM，性價(jià)比太低满葛。Virtual DOM 就是這么做的径簿，只是加了一些特別的步驟來避免了整棵 DOM 樹變更。
2. Virtual DOM
DOM很慢嘀韧，輕微的操作都可能導(dǎo)致頁面重新排版篇亭，非常耗性能。
相對(duì)于DOM對(duì)象锄贷，js對(duì)象處理起來更快译蒂，而且更簡(jiǎn)單。
Virtual DOM算法原理就是：用 JavaScript 對(duì)象表示 DOM 信息和結(jié)構(gòu)谊却，當(dāng)狀態(tài)變更的時(shí)候柔昼，重新渲染這個(gè) JavaScript 的對(duì)象結(jié)構(gòu)。 我們用新的對(duì)象樹去比對(duì)舊的對(duì)象樹因惭，記錄差異岳锁，然后應(yīng)用到真正的DOM樹上面去。這樣我們就不需要重新構(gòu)造整個(gè)DOM樹了蹦魔。本質(zhì)就是：在js和DOM之間做了一個(gè)緩存激率。
3. 對(duì)React Virtual DOM 的誤解
React 從來沒有說過 “React 比原生操作 DOM 快”咳燕。React 的基本思維模式是每次有變動(dòng)就整個(gè)重新渲染整個(gè)應(yīng)用。如果沒有 Virtual DOM乒躺，簡(jiǎn)單來想就是直接重置 innerHTML招盲。很多人都沒有意識(shí)到，在一個(gè)大型列表所有數(shù)據(jù)都變了的情況下嘉冒，重置 innerHTML 其實(shí)是一個(gè)還算合理的操作... 真正的問題是在 “全部重新渲染” 的思維模式下曹货，即使只有一行數(shù)據(jù)變了，它也需要重置整個(gè) innerHTML讳推，這時(shí)候顯然就有大量的浪費(fèi)顶籽。
框架的意義在于為你掩蓋底層的 DOM 操作，讓你用更聲明式的方式來描述你的目的银觅，從而讓你的代碼更容易維護(hù)礼饱。
沒有任何框架可以比純手動(dòng)的優(yōu)化 DOM 操作更快，因?yàn)榭蚣艿?DOM 操作層需要應(yīng)對(duì)任何上層 API 可能產(chǎn)生的操作究驴，它的實(shí)現(xiàn)必須是普適的镊绪。在構(gòu)建一個(gè)實(shí)際應(yīng)用的時(shí)候，我們不可能為每一個(gè)地方都去做手動(dòng)優(yōu)化洒忧，出于可維護(hù)性的考慮蝴韭，這顯然不可能。
框架給你的保證是熙侍，你在不需要手動(dòng)優(yōu)化的情況下榄鉴，我依然可以給你提供過得去的性能。
4. React：虛擬DOM Diff算法基礎(chǔ)學(xué)習(xí)
步驟1：用js對(duì)象模擬DOM樹
步驟2：DOM Diff算法
即給定任意兩棵樹核行，找到最少的轉(zhuǎn)換步驟牢硅。但是標(biāo)準(zhǔn)的的Diff算法復(fù)雜度需要O(n^3)，這里n表示的是樹的節(jié)點(diǎn)的總數(shù)芝雪。這顯然無法滿足性能要求减余。要達(dá)到每次界面都可以整體刷新界面的目的，勢(shì)必需要對(duì)算法進(jìn)行優(yōu)化惩系。這看上去非常有難度位岔，然而Facebook工程師卻做到了，他們結(jié)合Web界面的特點(diǎn)做出了兩個(gè)簡(jiǎn)單的假設(shè)堡牡，使得Diff算法復(fù)雜度直接降低到O(n)抒抬，這相當(dāng)于一個(gè)一層的for循環(huán)。
- Web 中DOM節(jié)點(diǎn)跨層次的移動(dòng)操作很少晤柄，可以忽略不計(jì)
- 擁有相同類的兩個(gè)組件將會(huì)生成相似的樹形結(jié)構(gòu)擦剑，擁有不同類的兩個(gè)組件將會(huì)生成不同的樹形結(jié)構(gòu)。
- 對(duì)于同一層次的一組子節(jié)點(diǎn)，它們可以通過唯一的id進(jìn)行區(qū)分惠勒。
基于以上三個(gè)前提策略赚抡，React對(duì)diff算法進(jìn)行了優(yōu)化。使得算法的復(fù)制度降到了O(n)纠屋。
tree diff
DOM的diff算法實(shí)際上只會(huì)對(duì)樹進(jìn)行逐層的比較涂臣。
【示例1】React diff 的執(zhí)行情況：create A -> create B -> create C -> delete A。
當(dāng)出現(xiàn)節(jié)點(diǎn)跨層級(jí)移動(dòng)時(shí)售担，并不會(huì)出現(xiàn)想象中的移動(dòng)操作赁遗，而是以 A 為根節(jié)點(diǎn)的樹被整個(gè)重新創(chuàng)建，這是一種影響 React 性能的操作族铆，因此 React 官方建議不要進(jìn)行 DOM 節(jié)點(diǎn)跨層級(jí)的操作岩四。所以保持穩(wěn)定的DOM結(jié)構(gòu)會(huì)有助于性能的提升。
component diff
- 對(duì)于同一類型的組件骑素，會(huì)按照原策略繼續(xù)比較 virtual DOM tree炫乓。
- 對(duì)于不同類型的組件，直接整個(gè)替換献丑，即使結(jié)構(gòu)非常相似。
element diff
當(dāng)節(jié)點(diǎn)處于同一層級(jí)時(shí)侠姑，React diff 提供了三種節(jié)點(diǎn)操作创橄，分別為：INSERT_MARKUP（插入）、MOVE_EXISTING（移動(dòng)）和 REMOVE_NODE（刪除）莽红。
ABCD--->BADC 這樣我們需要做的就很多了妥畏，我們需要?jiǎng)h除ABCD 然后插入DCBA。
React 發(fā)現(xiàn)這類操作繁瑣冗余安吁，因?yàn)檫@些都是相同的節(jié)點(diǎn)醉蚁，但由于位置發(fā)生變化，導(dǎo)致需要進(jìn)行繁雜低效的刪除鬼店、創(chuàng)建操作网棍，其實(shí)只要對(duì)這些節(jié)點(diǎn)進(jìn)行位置移動(dòng)即可。
針對(duì)這一現(xiàn)象妇智，React 提出優(yōu)化策略：允許開發(fā)者對(duì)同一層級(jí)的同組子節(jié)點(diǎn)滥玷，添加唯一 key 進(jìn)行區(qū)分，雖然只是小小的改動(dòng)巍棱，性能上卻發(fā)生了翻天覆地的變化惑畴！
那么對(duì)于上面的例子，我們就可以只移動(dòng)AC,BD不做任何操作航徙。
那么如贷，如此高效的 diff 到底是如何運(yùn)作的呢？
首先對(duì)新集合的節(jié)點(diǎn)進(jìn)行循環(huán)遍歷，for (name in nextChildren)杠袱，通過唯一 key 可以判斷新老集合中是否存在相同的節(jié)點(diǎn)尚猿，if (prevChild === nextChild)，如果存在相同節(jié)點(diǎn)霞掺，則進(jìn)行移動(dòng)操作谊路，但在移動(dòng)前需要將當(dāng)前節(jié)點(diǎn)在老集合中的位置與 lastIndex 進(jìn)行比較，
if (在老集合中的節(jié)點(diǎn)位置 < lastIndex)菩彬，則進(jìn)行節(jié)點(diǎn)移動(dòng)操作缠劝，否則不執(zhí)行該操作。這是一種順序優(yōu)化手段骗灶，lastIndex 一直在更新惨恭，表示訪問過的節(jié)點(diǎn)在老集合中最右的位置（即最大的位置），如果新集合中當(dāng)前訪問的節(jié)點(diǎn)比 lastIndex 大耙旦，說明當(dāng)前訪問節(jié)點(diǎn)在老集合中就比上一個(gè)節(jié)點(diǎn)位置靠后脱羡，則該節(jié)點(diǎn)不會(huì)影響其他節(jié)點(diǎn)的位置，因此不用添加到差異隊(duì)列中免都，即不執(zhí)行移動(dòng)操作锉罐，只有當(dāng)訪問的節(jié)點(diǎn)比 lastIndex 小時(shí)，才需要進(jìn)行移動(dòng)操作绕娘。
待補(bǔ)充
