呜呜呜感动天，感动地，我终于实现了比 react 更牛逼的 diff 算法！

从此，fre 站起来了！

众所周知，fre、react 这俩世间仅存的俩孤儿，由于使用了链表的数据结构，导致很多优秀的算法都无法使用

以至于 react 那么牛逼的团队，有 inferno 作者坐镇的团队，都写不出一个高效的算法

对我来说，实现一个更好的算法是一个心愿

然后经过长时间的研究，我终于找到了思路！

我并没有发明新的算法，我只是将 vue 的算法移植到链表的生成过程中，而已！！！

基于 LIS 的 diff 算法

这是目前最快的 diff 算法，也是 inferno，ivi，vue3 等框架使用的算法，这个算法的本质是寻找最小移动，更多的命中预处理的分支

具体的实现思路可以看这里：https://github.com/localvoid/ivi/blob/master/packages/ivi/src/vdom/reconciler.ts#L585

这是一个 O(nlogn) 的算法

我花了很长一段时间研究这个算法，研究 LIS 和 LCS，但是最终发现，这个算法并不适合 fre

因为 fre 的链表的限制，它无法放弃子链的生成，导致不能更多地命中预处理，但是一旦算法命中了 O(nlogn) 的分支，这个算法将会变得很慢

总的来说，这个算法更适合 vue 这种同步框架，他们可以在恰当的时机放弃子树

于是，我吸取教训，选择另外一种 O(n) 的算法

基于两端遍历的 diff 算法

这个算法的好处是，从两端进行遍历，可以处理公共子缀

1 2 3 4
1 3 2 4
  ^ ^
这里的 1 和 4 就是相同的前缀后缀，直接跳过，只需要 diff 2 3

同时它是一个 O(n) 的算法，不会和 LIS 一样存在坏分支

实现思路可以看这个：https://github.com/Polymer/lit-html/blob/master/src/directives/repeat.ts#L141

在 react 的注释里还提到了：https://github.com/facebook/react/blob/master/packages/react-reconciler/src/ReactChildFiber.new.js#L760

大致意思是，链表没有反向指针，是无法实现这个算法的

我莞尔一笑

实际上，先生成链表，再做 diff 是无解的

唯一解就是，在生成过程中做 diff，这样整个遍历仍旧是数组的遍历，就可以从两端开始，这是这个算法的唯一实现思路，我之前还发明了破烂链表，可惜并不靠谱

链表仍旧要完整生成，所以从收益上来看，同一个算法，fre 并不如 vue，因为 vue 可以在恰当的时机放弃子树的遍历

但因为这是个 O(n) 的算法，所以就只是慢了一丢丢，整体收益还是很大的

适合的才是最好的

尽管无法实现 LIS 的算法有点遗憾，但两端遍历的算法也比 react 好太多，react 那个实现真的已经称不上是算法了

以前的我真的无可奈何，每当别人问我 fre 和 react 有什么优势的时候，我都无语凝噎

终于有一天，我可以说 fre 实现了 react 没能实现的算法

现在，fre 已经在某些方面拥有了优势

1. 比 react 更好的算法
2. 比 vue/preact 更好的调度（时间切片）

未来，fre 会走自己的路，探讨新的好玩的东西

更好的协程

上一篇文章有提到，我想到了一个基于多队列的实现更好的协程的思路

react 使用优先级这种枪占式的方式实现并发，这破坏了协程的概念，而且不够轻量，未来我会努力研究前端框架的协程，做更好的 Fiber

更少的代码

因为新的 diff 实现存在很多冗余代码，接下来我得思考怎么去精简，现在 fre 的代码总量已经超过了 1kb

之所以还叫 1kb 是因为可以通过 tree-shaking 将不用的 hooks API 给摇掉，算的是 hello world 的体积，哈哈哈

总结

既然 react 的算法并不慢，为什么你还要用新算法，如果你是这么认为的，那我可以告诉你，不用算法也不慢

实际上，新算法对性能的提升是很次要的，只是有了新算法，我才能算是发了 fre2

老算法我已经玩腻了，甚至我都看到了抄 fre 的框架，然后他挂的是 preact 的名字，尴尬

马上脱坑研究新事物，跑得快，就不怕被抄了……