React Diff算法一览
<h1>前言</h1><p>diff算法不停是React体系最焦点的部分，而且由于演化自传统diff，使得比力方式从O(n^3)降级到O(n)，然后又改成了链表方式，可谓是厘革万千。</p>
<h1>传统Diff算法</h1>
<p>传统diff算法必要循环比力两棵树，全部节点的循环，那么单纯比力次数就是O(n^2)，n*n</p>
<code >P L
A A
/ \ / \
/ \ / \
B D ====> D B
/ \
C C
</code>
<p>刷刷刷，每次都必要循环遍历，于是有以下的查找过程：</p>
<code >PA->LA
PA->LB
PA->LC
PA->LD
PB->LA
...</code>
<p>除了查找过程消耗了O(n^2)之外，找到差别后还要计算最小转换方式，终极结果为O(n^3)。</p>
<p>以是，传统的diff算法的时间复杂度为O(n^3)。</p>
<p>假如React运用这种算法，那么节点过多，将会有大量的开销，固然CPU的秒速达到30亿次计算，但仍旧黑白常耗费性能的。</p>
<p>有没有什么方式可以降低时间复杂度呢？</p>
<p>于是，React15对传统的diff做了一些限制，使得时间复杂度变为了O(n)。</p>
<h1>React 15的Diff算法</h1>
<p>《深入React技术栈》这本书，给出了三种Diff策略分析，文字形貌太过抽象，直接表述如下：</p>
<p>Tree diff、Component diff、Element diff</p>
<h2>Tree diff</h2>
<p>什么是Tree diff？先上图：</p>
<p><div align="center"></div></p>
<p> </p>
<p>首先，进行同级比力，并非循环比力。如许比力次数就降为一层一次，时间复杂度直接降为O(n)</p>
<p>假如同级雷同位置节点不一样，则直接删除更换，简单粗暴。</p>
<p>而对于节点移动，同样原理，也是简单粗暴的删除重修。如下图所示（图中第四步应该是删除左侧的整棵A树）：</p>
<p><div align="center"></div></p>
<h2>Component diff</h2>
<p>不多说，先上图：</p>
<h2><div align="center"></div></h2>
<p>着实component diff相当于是子树的diff，根本方案和tree diff是同等的，假如如上图D变为G，那么直接删除D这一整棵树，然后重新渲染G树。</p>
<p>仍旧是简单粗暴。</p>
<h2>Element diff</h2>
<p>对于同一节点的元素，diff算法提供了三种操纵：插入、移动、删除。还是先上图：</p>
<p><div align="center"></div></p>
<p>此时的操纵，是B、D不做任何操纵，AC移动到相应位置【前提是都有雷同的key】</p>
<p>假如，此时的key不雷同，全都发生了厘革，那么节点全都是要删除重新构建，将会消耗大量性能。</p>
<h1>React 16的Diff算法</h1>
<p>React16相比React15的Diff算法发生了很大的厘革，其中最重要就是引入了Fiber循环任务调治算法。</p>
<h2>Fiber</h2>
<p>Fiber是什么？干了什么？</p>
<p>Fiber在diff阶段，做了如下的操纵：</p>
<p>1、可以随时将diff操纵进行任务拆分。</p>
<p>2、diff阶段的每个任务可以随时执行或者中止。</p>
<p>3、diff阶段任务调治优先级控制。</p>
<p>以是，Fiber相当于是，在15的diff算法阶段，做了优先级的任务调治控制，</p>
<p>以是，Fiber是根据一个fiber节点（VDOM节点）来拆分，以fiber node为一个任务单位，一 个组件实例都是一个任务单位。任务循环中，每处理完一个fiber node，可以制止/挂起/恢复。</p>
<p>它又是怎样可以或许进行如许的异步操纵的呢？这就不得不说一个方法：requestIdleCallback</p>
<p>欣赏器提供的requestIdleCallback API中的Cooperative Scheduling可以让欣赏器在空闲时间执行回调（开发者传入的方法），在回调参数中可以获取到当前帧（16ms）剩余的时间。使用这个信息可以公道的安排当前帧必要做的事变，假如时间足够，那继续做下一个任务，假如时间不敷就歇一歇，调用requestIdleCallback来获知主线程不忙的时候，再继续做任务<br />Fiber Node是什么？</p>
<p>链表！</p>
<p>将要处理的节点，存在链表结构，那么就可以或许做到节点复用。【这大概是Fiber的焦点吧】</p>
<p>大要上的Diff引入了Fiber之后，我们就增长了更多的链表复勤奋能，通过这一点，我们可以使得React Diff的性能得到提升。</p>
<h1>总结</h1>
<p>着实，这篇文章偏重讲的还是React15的diff，React 16的diff并未详细探究，接下来会出一篇文章，单独解说React 16的Diff策略。不外React 16Diff策略的焦点Fiber是不可错过的点。</p>
<h1>参考资料</h1>
<p>《深入React技术栈》</p>
<p>https://segmentfault.com/a/1190000016723305</p>
<p>https://www.jianshu.com/p/3ba0822018cf</p>
<p>https://www.jianshu.com/p/21a445066d51?from=timeline</p>
<p>https://www.zhihu.com/question/66851503/answer/246766239</p>
<p>https://blog.csdn.net/P6P7qsW6ua47A2Sb/article/details/82322033</p>
<p>https://blog.csdn.net/VhWfR2u02Q/article/details/100011830</p>
<p> </p>
<p> </p>
<p>我的博客：http://www.gaoyunjiao.fun/?p=170</p><br><br/><br/><br/><br/><br/>来源：<a href="https://www.cnblogs.com/qixingduanyan/p/11725749.html" target="_blank">https://www.cnblogs.com/qixingduanyan/p/11725749.html</a>
页:
[1]