一、讀懂diff

diff是Unix/Linux系統(tǒng)的一個很重要的工具程序。
它用來比較兩個文本文件的差異，是代碼版本管理的基石之一。

diff <文件1> <文件2>

diff就會告訴你，這兩個文件有何差異。

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表示第一個文件第5行改變，a（add）,c（change）,d（delete）。后面的5表示第二個文件變動行。
• < 5：前面的小于號，表示要從test1當中刪除的內(nèi)容。
• ---：test1和test2的分割線。
• > 6：前面的大于號，表示要從test2當中增加該內(nèi)容。

4. 上下文格式

上面的結(jié)果顯示太簡單不易理解，所以加入上下文的方式。它的使用方法是加入c參數(shù)（代表context）

為了更明顯的顯示上下文的效果 我們把文件改成如下內(nèi)容：

test1

test2

diff -c test1 test2

對比結(jié)果

解析：

• ***：表示修改前的文件。
• ---：表示修改后的文件。
• 6,13：表示顯示的行6-13行。這時不僅顯示發(fā)生變化的行內(nèi)容，變化內(nèi)容前面三行和后面三行。
• 另外，文件內(nèi)容的每一行最前面，還有一個標記位。
  如果為空，表示該行無變化；
  如果是感嘆號（!），表示該行有改動；
  如果是減號（-），表示該行被刪除；
  如果是加號（+），表示該行為新增。

5. 合并格式

如果兩個文件相似度很高，那么上下文格式的diff，將顯示大量重復的內(nèi)容，比較浪費空間。
使用方式加一個參數(shù)u

diff -u test1 test2

合并結(jié)果

6. git格式的diff

版本管理系統(tǒng)git，使用的是合并格式diff的變體。

git diff

結(jié)果

解析：

• 進行比較的是，a版本的test1（即變動前）和b版本的test2（即變動后）。
• 第二行表示兩個版本的git哈希值（index區(qū)域的fcb0de4對象，與工作目錄區(qū)域的1e628d3對象進行比較），最后的六位數(shù)字是對象的模式（普通文件，644權(quán)限 讀寫-讀-讀 =>屬主-組成員-其他用戶）。

7. diff程序原理

在diff里面，我們比較的兩個文件叫做old和new，而一般是按行來比較。這里我們可以抽象成一個字符串的比較，比如：
old: abc
new: abcd
那么其中的每一個字符都可以表示文件里面的一行。那么diff里面用到的比較思想是從old和new里面找出最長的subsequence。這是基于LCS（Longest Common Subsequnece）算法。

子序列的概念是......舉例說明吧：

a b c d e f g h i
a b c h d f g ij

那么最長公共子序列就是：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))
使用遞歸來計算最長的相似元素的長度。

矩陣的列是old,橫坐標是new

MJAU

GC||GA

詳情閱讀LCS算法

二、首先了解一下虛擬DOM

1. 對前端狀態(tài)管理的小總結(jié)

在最開始我們對于狀態(tài)改變更新對應的視圖，都是操作dom。但是對于復雜的應用程序來說，無疑這是很低效率，不便于維護的。

于是，出現(xiàn)了MVC等架構(gòu)模式，希望能從代碼組織方式來降低維護這種復雜應用程序的難度。但是 MVC 架構(gòu)沒辦法減少你所維護的狀態(tài)，也沒有降低狀態(tài)更新你需要對頁面的更新操作（前端來說就是DOM操作），你需要操作的DOM還是需要操作，只是換了個地方。

于是，后來人們想出了 MVVM 模式，只要在模版中聲明視圖組件是和什么狀態(tài)進行綁定的，雙向綁定引擎就會在狀態(tài)更新的時候自動更新視圖。

MVVM 可以很好的降低我們維護狀態(tài) -> 視圖的復雜程度。但是這不是唯一的辦法，還有一個非常直觀的方法，可以大大降低視圖更新的操作：一旦狀態(tài)發(fā)生了變化，就用模版引擎重新渲染整個視圖，然后用新的視圖更換掉舊的視圖。最大的問題就是這樣做會很慢，因為即使一個小小的狀態(tài)變更都要重新構(gòu)造整棵 DOM，性價比太低。Virtual DOM 就是這么做的，只是加了一些特別的步驟來避免了整棵 DOM 樹變更。

2. Virtual DOM

DOM很慢，輕微的操作都可能導致頁面重新排版，非常耗性能。

相對于DOM對象，js對象處理起來更快，而且更簡單。

Virtual DOM算法原理就是：用 JavaScript 對象表示 DOM 信息和結(jié)構(gòu)，當狀態(tài)變更的時候，重新渲染這個 JavaScript 的對象結(jié)構(gòu)。 我們用新的對象樹去比對舊的對象樹，記錄差異，然后應用到真正的DOM樹上面去。這樣我們就不需要重新構(gòu)造整個DOM樹了。本質(zhì)就是：在js和DOM之間做了一個緩存。

3. 對React Virtual DOM 的誤解

React 從來沒有說過 “React 比原生操作 DOM 快”。React 的基本思維模式是每次有變動就整個重新渲染整個應用。如果沒有 Virtual DOM，簡單來想就是直接重置 innerHTML。很多人都沒有意識到，在一個大型列表所有數(shù)據(jù)都變了的情況下，重置 innerHTML 其實是一個還算合理的操作... 真正的問題是在 “全部重新渲染” 的思維模式下，即使只有一行數(shù)據(jù)變了，它也需要重置整個 innerHTML，這時候顯然就有大量的浪費。

• 框架的意義在于為你掩蓋底層的 DOM 操作，讓你用更聲明式的方式來描述你的目的，從而讓你的代碼更容易維護。

• 沒有任何框架可以比純手動的優(yōu)化 DOM 操作更快，因為框架的 DOM 操作層需要應對任何上層 API 可能產(chǎn)生的操作，它的實現(xiàn)必須是普適的。在構(gòu)建一個實際應用的時候，我們不可能為每一個地方都去做手動優(yōu)化，出于可維護性的考慮，這顯然不可能。

• 框架給你的保證是，你在不需要手動優(yōu)化的情況下，我依然可以給你提供過得去的性能。

4. React：虛擬DOM Diff算法基礎學習

步驟1：用js對象模擬DOM樹

代碼

代碼運行效果

步驟2：DOM Diff算法
即給定任意兩棵樹，找到最少的轉(zhuǎn)換步驟。但是標準的的Diff算法復雜度需要O(n^3)，這里n表示的是樹的節(jié)點的總數(shù)。這顯然無法滿足性能要求。要達到每次界面都可以整體刷新界面的目的，勢必需要對算法進行優(yōu)化。這看上去非常有難度，然而Facebook工程師卻做到了，他們結(jié)合Web界面的特點做出了兩個簡單的假設，使得Diff算法復雜度直接降低到O(n)，這相當于一個一層的for循環(huán)。

• Web 中DOM節(jié)點跨層次的移動操作很少，可以忽略不計
• 擁有相同類的兩個組件將會生成相似的樹形結(jié)構(gòu)，擁有不同類的兩個組件將會生成不同的樹形結(jié)構(gòu)。
• 對于同一層次的一組子節(jié)點，它們可以通過唯一的id進行區(qū)分。

基于以上三個前提策略，React對diff算法進行了優(yōu)化。使得算法的復制度降到了O(n)。

tree diff
DOM的diff算法實際上只會對樹進行逐層的比較。

比較圖

【示例1】

【示例1】React diff 的執(zhí)行情況：create A -> create B -> create C -> delete A。

當出現(xiàn)節(jié)點跨層級移動時，并不會出現(xiàn)想象中的移動操作，而是以 A 為根節(jié)點的樹被整個重新創(chuàng)建，這是一種影響 React 性能的操作，因此 React 官方建議不要進行 DOM 節(jié)點跨層級的操作。所以保持穩(wěn)定的DOM結(jié)構(gòu)會有助于性能的提升。

component diff

• 對于同一類型的組件，會按照原策略繼續(xù)比較 virtual DOM tree。
• 對于不同類型的組件，直接整個替換，即使結(jié)構(gòu)非常相似。

element diff
當節(jié)點處于同一層級時，React diff 提供了三種節(jié)點操作，分別為：INSERT_MARKUP（插入）、MOVE_EXISTING（移動）和 REMOVE_NODE（刪除）。

ABCD--->BADC 這樣我們需要做的就很多了，我們需要刪除ABCD 然后插入DCBA。

React 發(fā)現(xiàn)這類操作繁瑣冗余，因為這些都是相同的節(jié)點，但由于位置發(fā)生變化，導致需要進行繁雜低效的刪除、創(chuàng)建操作，其實只要對這些節(jié)點進行位置移動即可。

針對這一現(xiàn)象，React 提出優(yōu)化策略：允許開發(fā)者對同一層級的同組子節(jié)點，添加唯一 key 進行區(qū)分，雖然只是小小的改動，性能上卻發(fā)生了翻天覆地的變化！

那么對于上面的例子，我們就可以只移動AC,BD不做任何操作。

移動

那么，如此高效的 diff 到底是如何運作的呢？

首先對新集合的節(jié)點進行循環(huán)遍歷，for (name in nextChildren)，通過唯一 key 可以判斷新老集合中是否存在相同的節(jié)點，if (prevChild === nextChild)，如果存在相同節(jié)點，則進行移動操作，但在移動前需要將當前節(jié)點在老集合中的位置與 lastIndex 進行比較，
if (在老集合中的節(jié)點位置 < lastIndex)，則進行節(jié)點移動操作，否則不執(zhí)行該操作。這是一種順序優(yōu)化手段，lastIndex 一直在更新，表示訪問過的節(jié)點在老集合中最右的位置（即最大的位置），如果新集合中當前訪問的節(jié)點比 lastIndex 大，說明當前訪問節(jié)點在老集合中就比上一個節(jié)點位置靠后，則該節(jié)點不會影響其他節(jié)點的位置，因此不用添加到差異隊列中，即不執(zhí)行移動操作，只有當訪問的節(jié)點比 lastIndex 小時，才需要進行移動操作。

待補充