前言

diff算法一直是React系统最核心的部分,并且由于演化自传统diff,使得比较方式从O(n^3)降级到O(n),然后又改成了链表方式,可谓是变化万千。

传统Diff算法

传统diff算法需要循环比较两棵树,所有节点的循环,那么单纯比较次数就是O(n^2),n*n

P                         L
          A                     A  
         / \                   / \
        /   \                 /   \
       B     D     ====>     D     B
      /                             \
     C                               C

刷刷刷,每次都需要循环遍历,于是有以下的查找过程:

PA->LA
PA->LB
PA->LC
PA->LD
PB->LA
...

除了查找过程消耗了O(n^2)之外,找到差异后还要计算最小转换方式,最终结果为O(n^3)。

所以,传统的diff算法的时间复杂度为O(n^3)。

如果React运用这种算法,那么节点过多,将会有大量的开销,虽然CPU的秒速达到30亿次计算,但依旧是非常耗费性能的。

有没有什么方式可以降低时间复杂度呢?

于是,React15对传统的diff做了一些限制,使得时间复杂度变为了O(n)。

React 15的Diff算法

《深入React技术栈》这本书,给出了三种Diff策略分析,文字描述太过抽象,直接表述如下:

Tree diff、Component diff、Element diff

Tree diff

什么是Tree diff?先上图:

 

首先,进行同级比较,并非循环比较。这样比较次数就降为一层一次,时间复杂度直接降为O(n)

如果同级相同位置节点不一样,则直接删除替换,简单粗暴。

而对于节点移动,同样道理,也是简单粗暴的删除重建。如下图所示(图中第四步应该是删除左侧的整棵A树):

Component diff

不多说,先上图:

其实component diff相当于是子树的diff,基本方案和tree diff是一致的,如果如上图D变为G,那么直接删除D这一整棵树,然后重新渲染G树。

依旧是简单粗暴。

Element diff

对于同一节点的元素,diff算法提供了三种操作:插入、移动、删除。还是先上图:

此时的操作,是B、D不做任何操作,AC移动到相应位置【前提是都有相同的key】

如果,此时的key不相同,全都发生了变化,那么节点全都是要删除重新构建,将会消耗大量性能。

React 16的Diff算法

React16相比React15的Diff算法发生了很大的变化,其中最主要就是引入了Fiber循环任务调度算法。

Fiber

Fiber是什么?干了什么?

Fiber在diff阶段,做了如下的操作:

1、可以随时将diff操作进行任务拆分。

2、diff阶段的每个任务可以随时执行或者中止。

3、diff阶段任务调度优先级控制。

所以,Fiber相当于是,在15的diff算法阶段,做了优先级的任务调度控制,

所以,Fiber是根据一个fiber节点(VDOM节点)来拆分,以fiber node为一个任务单元,一 个组件实例都是一个任务单元。任务循环中,每处理完一个fiber node,可以中断/挂起/恢复。

它又是如何能够进行这样的异步操作的呢?这就不得不说一个方法:requestIdleCallback

浏览器提供的requestIdleCallback API中的Cooperative Scheduling可以让浏览器在空闲时间执行回调(开发者传入的方法),在回调参数中可以获取到当前帧(16ms)剩余的时间。利用这个信息可以合理的安排当前帧需要做的事情,如果时间足够,那继续做下一个任务,如果时间不够就歇一歇,调用requestIdleCallback来获知主线程不忙的时候,再继续做任务
Fiber Node是什么?

链表!

将要处理的节点,存在链表结构,那么就能够做到节点复用。【这大概是Fiber的核心吧】

大体上的Diff引入了Fiber之后,我们就增加了更多的链表复用功能,通过这一点,我们可以使得React Diff的性能得到提升。

总结

其实,这篇文章着重讲的还是React15的diff,React 16的diff并未详细探讨,接下来会出一篇文章,单独讲解React 16的Diff策略。不过React 16Diff策略的核心Fiber是不可错过的点。

参考资料

《深入React技术栈》

https://segmentfault.com/a/1190000016723305

https://www.jianshu.com/p/3ba0822018cf

https://www.jianshu.com/p/21a445066d51?from=timeline

https://www.zhihu.com/question/66851503/answer/246766239

https://blog.csdn.net/P6P7qsW6ua47A2Sb/article/details/82322033

https://blog.csdn.net/VhWfR2u02Q/article/details/100011830

167 thoughts on “React Diff算法一览

  1. Pingback: trustedmdstorefy.com
  2. Pingback: hqcialismht.com
  3. cialis说道:

    lower advance tadalafil somehow trip
    cialis
    generally painting cialis soon pace
    [url=http://cialislet.com/#cialis]buy cialis pills[/url]
    whenever university cialis nearly tale http://cialislet.com/

  4. essentially introduction generic pills in usa
    short shoot
    viagra online
    best cookie generic viagra without subscription initially string
    [url=http://www.vagragenericaar.org/#cheap viagra usa without prescription]generic
    pills in usa[/url]
    literally gas viagra no prescription once somewhere http://www.vagragenericaar.org/

  5. viagra for sale说道:

    first rent anywhere generic viagra sales
    late viagra for sale maybe power last [url=http://viacheapusa.com/]sale generic
    viagra online pills[/url] hard brother http://viacheapusa.com/

  6. roughly insurance [url=http://www.cialij.com/#]erection pills viagra online[/url] constantly world deeply
    river buy pills erection generic pray editor erection pills viagra online instead
    familiar http://www.cialij.com/

  7. cialis 20mg说道:

    completely concept [url=http://cialisles.com/#]cialis 20mg[/url] deeply
    difference left whereas cialis generic tadalafil for sale
    currently refrigerator cialis 20mg instead minute http://cialisles.com

  8. TyroneMerne说道:

    Incredible plenty of helpful information. https://viagrapycharm.com/

  9. TyroneMerne说道:

    Truly quite a lot of very good info! viagra dose

  10. ErnestCunda说道:

    You stated this exceptionally well! neurontin 300 mg

  11. ErnestCunda说道:

    Helpful forum posts. Many thanks! lasix medication

  12. Williamfic说道:

    safe canadian pharmacy http://cialisxtl.com canadian pharmacy no scripts

  13. Louiscoutt说道:

    You actually revealed it terrifically! Cialis Brno

  14. ErnestCunda说道:

    Truly plenty of superb knowledge! duloxetine 30 mg

  15. Williamfic说道:

    tadalafil canadian pharmacy http://cialisxtl.com specialty pharmacy

  16. AnthonyAmike说道:

    where to bay cialis (tadalafil) pills 80mg http://cialisxtl.com real cialis online with paypal

  17. Larrylubre说道:

    Amazing a good deal of good information. neurontin medication

  18. Louiscoutt说道:

    Seriously quite a lot of wonderful facts! provigil vs nuvigil

  19. Richardundip说道:

    Valuable advice. With thanks. viagra

  20. TyroneMerne说道:

    You actually suggested this terrifically. Cialis Overseas Shipping

  21. Richardundip说道:

    Whoa quite a lot of fantastic advice! is kratom legal

  22. Antoniokit说道:

    mail order pharmacy buy cialis cialis 30 day sample

  23. ErnestCunda说道:

    You made your point extremely clearly.. buy cialis online

  24. Antoniokit说道:

    generic cialis coming out cialisxtl generic cialis bitcoin

  25. Larrylubre说道:

    Beneficial facts. With thanks! zyloprim

  26. TyroneMerne说道:

    You actually expressed that fantastically! buy generic viagra

  27. Richardundip说道:

    You made your point extremely well!! cialis from canada

  28. Larrylubre说道:

    Many thanks, Plenty of forum posts.
    prednisolona

  29. Pingback: #1plus1
  30. Antoniokit说道:

    sildenafil vs viagra cialis warnings for cialis

  31. ErnestCunda说道:

    Information certainly applied!. augmentin 875

  32. Louiscoutt说道:

    You actually explained that terrifically. canadian online pharmacy

  33. Antoniokit说道:

    best canadian pharmacy for cialis generic cialis lowest cialis prices

  34. Louiscoutt说道:

    Amazing a good deal of amazing information. provigil

  35. Antoniokit说道:

    online pharmacy viagra cialis online viagra without doctor prescription

  36. TyroneMerne说道:

    You explained this adequately! viagra sex

  37. Lamont Ramage说道:

    It is not easy to meet good articles, collect them well, and study well!

  38. Antoniokit说道:

    viagra or cialis cialis xtl coffee with cialis

  39. ErnestCunda说道:

    You suggested that really well! flagyl 500

  40. Richardundip说道:

    Many thanks, A good amount of data.
    Cialis Adc

  41. Antoniokit说道:

    online cialis cialis discount viagra prescriptions over internet

  42. Antoniokit说道:

    save on pharmacy cialisxtl cialis vs viagra effectiveness

  43. Larrylubre说道:

    Truly tons of beneficial information! global pharmacy canada

  44. Antoniokit说道:

    generic viagra online canadian pharmacy generic cialis canadian pharmacy ltd

  45. Antoniokit说道:

    legit canadian pharmacy cialis discount cialis 30 day trial voucher

  46. Antoniokit说道:

    show cialis working cialis xtl legitimate canadian pharmacy

  47. Antoniokit说道:

    viagra prescriptions over internet cialis online the effects of cialis on women

  48. Pingback: watch online TV LIVE
  49. Antoniokit说道:

    viagra without a doctor prescription cialis discount cialis professional

发表评论