diff之React:Virtual DOM

一、读懂diff

diff是Unix/Linux系统的一个很重要的工具程序。
它用来比较两个文本文件的差异，是代码版本管理的基石之一。

diff <文件1> <文件2>

diff就会告诉你，这两个文件有何差异。

1. diff的三种格式

正常格式
上下文格式
合并格式

2. 创建示例文件

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当中删除的内容。
---：test1和test2的分割线。
> 6：前面的大于号，表示要从test2当中增加该内容。

4. 上下文格式

上面的结果显示太简单不易理解，所以加入上下文的方式。它的使用方法是加入c参数（代表context）

为了更明显的显示上下文的效果我们把文件改成如下内容：

test1

test2

diff -c test1 test2

对比结果

解析：

***：表示修改前的文件。
---：表示修改后的文件。
6,13：表示显示的行6-13行。这时不仅显示发生变化的行内容，变化内容前面三行和后面三行。
另外，文件内容的每一行最前面，还有一个标记位。
如果为空，表示该行无变化；
如果是感叹号（!），表示该行有改动；
如果是减号（-），表示该行被删除；
如果是加号（+），表示该行为新增。

5. 合并格式

如果两个文件相似度很高，那么上下文格式的diff，将显示大量重复的内容，比较浪费空间。
使用方式加一个参数u

diff -u test1 test2

合并结果

6. git格式的diff

版本管理系统git，使用的是合并格式diff的变体。

git diff

结果

解析：

进行比较的是，a版本的test1（即变动前）和b版本的test2（即变动后）。
第二行表示两个版本的git哈希值（index区域的fcb0de4对象，与工作目录区域的1e628d3对象进行比较），最后的六位数字是对象的模式（普通文件，644权限读写-读-读 =>属主-组成员-其他用户）。

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（不需要连续）。

 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. 对前端状态管理的小总结

在最开始我们对于状态改变更新对应的视图，都是操作dom。但是对于复杂的应用程序来说，无疑这是很低效率，不便于维护的。

于是，出现了MVC等架构模式，希望能从代码组织方式来降低维护这种复杂应用程序的难度。但是 MVC 架构没办法减少你所维护的状态，也没有降低状态更新你需要对页面的更新操作（前端来说就是DOM操作），你需要操作的DOM还是需要操作，只是换了个地方。

于是，后来人们想出了 MVVM 模式，只要在模版中声明视图组件是和什么状态进行绑定的，双向绑定引擎就会在状态更新的时候自动更新视图。

MVVM 可以很好的降低我们维护状态 -> 视图的复杂程度。但是这不是唯一的办法，还有一个非常直观的方法，可以大大降低视图更新的操作：一旦状态发生了变化，就用模版引擎重新渲染整个视图，然后用新的视图更换掉旧的视图。最大的问题就是这样做会很慢，因为即使一个小小的状态变更都要重新构造整棵 DOM，性价比太低。Virtual DOM 就是这么做的，只是加了一些特别的步骤来避免了整棵 DOM 树变更。

2. Virtual DOM

DOM很慢，轻微的操作都可能导致页面重新排版，非常耗性能。

相对于DOM对象，js对象处理起来更快，而且更简单。

Virtual DOM算法原理就是：用 JavaScript 对象表示 DOM 信息和结构，当状态变更的时候，重新渲染这个 JavaScript 的对象结构。我们用新的对象树去比对旧的对象树，记录差异，然后应用到真正的DOM树上面去。这样我们就不需要重新构造整个DOM树了。本质就是：在js和DOM之间做了一个缓存。

3. 对React Virtual DOM 的误解

React 从来没有说过 “React 比原生操作 DOM 快”。React 的基本思维模式是每次有变动就整个重新渲染整个应用。如果没有 Virtual DOM，简单来想就是直接重置 innerHTML。很多人都没有意识到，在一个大型列表所有数据都变了的情况下，重置 innerHTML 其实是一个还算合理的操作... 真正的问题是在 “全部重新渲染” 的思维模式下，即使只有一行数据变了，它也需要重置整个 innerHTML，这时候显然就有大量的浪费。

框架的意义在于为你掩盖底层的 DOM 操作，让你用更声明式的方式来描述你的目的，从而让你的代码更容易维护。
没有任何框架可以比纯手动的优化 DOM 操作更快，因为框架的 DOM 操作层需要应对任何上层 API 可能产生的操作，它的实现必须是普适的。在构建一个实际应用的时候，我们不可能为每一个地方都去做手动优化，出于可维护性的考虑，这显然不可能。
框架给你的保证是，你在不需要手动优化的情况下，我依然可以给你提供过得去的性能。

4. React：虚拟DOM Diff算法基础学习

步骤1：用js对象模拟DOM树

代码

代码运行效果

步骤2：DOM Diff算法
即给定任意两棵树，找到最少的转换步骤。但是标准的的Diff算法复杂度需要O(n^3)，这里n表示的是树的节点的总数。这显然无法满足性能要求。要达到每次界面都可以整体刷新界面的目的，势必需要对算法进行优化。这看上去非常有难度，然而Facebook工程师却做到了，他们结合Web界面的特点做出了两个简单的假设，使得Diff算法复杂度直接降低到O(n)，这相当于一个一层的for循环。

Web 中DOM节点跨层次的移动操作很少，可以忽略不计
拥有相同类的两个组件将会生成相似的树形结构，拥有不同类的两个组件将会生成不同的树形结构。
对于同一层次的一组子节点，它们可以通过唯一的id进行区分。

基于以上三个前提策略，React对diff算法进行了优化。使得算法的复制度降到了O(n)。

tree diff
DOM的diff算法实际上只会对树进行逐层的比较。

比较图

【示例1】

【示例1】React diff 的执行情况：create A -> create B -> create C -> delete A。

当出现节点跨层级移动时，并不会出现想象中的移动操作，而是以 A 为根节点的树被整个重新创建，这是一种影响 React 性能的操作，因此 React 官方建议不要进行 DOM 节点跨层级的操作。所以保持稳定的DOM结构会有助于性能的提升。

component diff

对于同一类型的组件，会按照原策略继续比较 virtual DOM tree。
对于不同类型的组件，直接整个替换，即使结构非常相似。

element diff
当节点处于同一层级时，React diff 提供了三种节点操作，分别为：INSERT_MARKUP（插入）、MOVE_EXISTING（移动）和 REMOVE_NODE（删除）。

ABCD--->BADC 这样我们需要做的就很多了，我们需要删除ABCD 然后插入DCBA。

React 发现这类操作繁琐冗余，因为这些都是相同的节点，但由于位置发生变化，导致需要进行繁杂低效的删除、创建操作，其实只要对这些节点进行位置移动即可。

针对这一现象，React 提出优化策略：允许开发者对同一层级的同组子节点，添加唯一 key 进行区分，虽然只是小小的改动，性能上却发生了翻天覆地的变化！

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

移动

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

首先对新集合的节点进行循环遍历，for (name in nextChildren)，通过唯一 key 可以判断新老集合中是否存在相同的节点，if (prevChild === nextChild)，如果存在相同节点，则进行移动操作，但在移动前需要将当前节点在老集合中的位置与 lastIndex 进行比较，
if (在老集合中的节点位置 < lastIndex)，则进行节点移动操作，否则不执行该操作。这是一种顺序优化手段，lastIndex 一直在更新，表示访问过的节点在老集合中最右的位置（即最大的位置），如果新集合中当前访问的节点比 lastIndex 大，说明当前访问节点在老集合中就比上一个节点位置靠后，则该节点不会影响其他节点的位置，因此不用添加到差异队列中，即不执行移动操作，只有当访问的节点比 lastIndex 小时，才需要进行移动操作。

待补充