# Diff算法解决的问题

众所周知，由于历史原因和浏览器资源问题^[1]，操作Dom是一个耗时操作，React这样的类库提出了Virtual Dom的解决方案，操作和对比Virtual Dom性能会比传统的DOM操作和对比性能上要好的多。 延伸之后，如何实现Virtual Dom的节点之间的对比算法和数据结构就成了主要问题，这其中又分了算法派和拟态派，这里只列出Diff相关的算法信息，数据结构和其他优化不是本问文主要内容。

# 各框架性能对比

https://stefankrause.net/js-frameworks-benchmark6/webdriver-ts/table.html

# 算法派历史

React最初推出时也不火，那时的招牌与现在性能不什么两样，也是高性能。但是JSX离经背道，与业界宣扬了多年的前后端分离，数据结构样式分离等教条差太远了，一直默默在角落里画圈。直到RN出来，解决原生编写界面的痛苦才一炮而红。大家才留意它的性能，它的性能背后的diff算法。最早研究React的diff算法是virtual-dom这个库，是基于经典的DFS算法。后来相应的算法就多起来。最后才是从接口进行模拟，就是所谓的React-like框架。因此虚拟DOM库是分为两大派系：算法派与拟态派。^[2]

# 拟态派历史

优化React代码体积以及其去掉prototype，constructor，增加key等他相关优化，react-lite时间系统鸡肋，难以扩展，最新的更新是12个月以前；preact，迷你话方案，并提供了preact-compact扩展，并去掉耗时的高级API的使用(如Object.freeze, Object.defineProperty)，核心问题是存在一些bug；anu，异步渲染，不使用高级API，外加使用requestAnimationFrame等方式优化, 新版本v1.4.0有了更多的优化^[3]。^[2:1]

# Diff算法分类

传统的DFS时间复杂度为O(n^3) Neil Diff^[4] Inferno DIff^[5] Nerv Diff^[6] Sanbbdom Diff(Vue 2.0)^[7]

# React Diff详解

React Diff分别解决了三个方面的差异对比：Tree，Component和Element^[8]

• React 通过制定大胆的 diff 策略，将 O(n^3) 复杂度的问题转换成 O(n) 复杂度的问题；
• React 通过分层求异的策略，对 tree diff 进行算法优化；
• React 通过相同类生成相似树形结构，不同类生成不同树形结构的策略，对 component diff 进行算法优化；
• React 通过设置唯一 key的策略，对 element diff 进行算法优化

# 1.Tree Diff

树形结构做广度优先遍历，如果父节点不同，就认为整个树形结构要重新创建，此外还有一个假设的前提是，不同层级之间的元素很少移动，不然这种算法会带来很大的性能损耗。

# 2.Component Diff

不同的组件，可以直接按照名称进行比较，当然也可以人为控制是否产生差异，使用shouldComponentUpdate来禁止组件被重新渲染。

# 3.Element Diff

依靠元素上的唯一ID，即key。key可以在不同层级之外不保持唯一性。

# 其他可以优化的内容

• 通过少量有状态组件控制无状态组件变化，所有状态通过Redux分发
• ReactDiff包含TreeDiff（同层比较），ComponentDiff(shouldComponentUpdate)，ElementDiff(Key).^[9]
• Babel-React-Optimise插件集合^[10]

# 引用资源

---

1. https://zhuanlan.zhihu.com/p/82652544 ↩︎

2. https://segmentfault.com/a/1190000011235844 ↩︎ ↩︎

3. https://www.cnblogs.com/rubylouvre/p/9140267.html ↩︎

4. https://neil.fraser.name/writing/diff/ ↩︎

5. https://www.zhihu.com/question/65824137/answer/235159117 ↩︎

6. https://github.com/NervJS/nerv/issues/3 ↩︎

7. https://github.com/snabbdom/snabbdom ↩︎

8. https://zhuanlan.zhihu.com/p/20346379 ↩︎

9. https://zhuanlan.zhihu.com/p/20346379 ↩︎

10. https://github.com/jamiebuilds/babel-react-optimize ↩︎