对于Vue3 diff的讨论

vue3.0的diff

深度递归遍历vnode树，节点的标签和key相同认为是同一个节点则更新，不同则删除，然后处理子节点。 子节点分这几种情况处理：纯文本、vnode 数组和空

空往往意味着添加或删除； 纯文本相同直接更新innerText，不同则删除； 新旧子节点都是vnode数组则diff算法来处理；

vue3.0 diff算法思想

编译模版时进行静态分析，标记动态节点，diff对比差异时仅对比动态节点（性能提升明显）；

diff算法先去头去尾，借此缩短遍历对比数组长度（对数组插入和删除操作性能优化明显）；

通过对更新前后子节点数组建立映射表的方式，将O(n^2)复杂度的遍历降低到O(n)；

通过最长递增子序列方法了来diff前后的子节点数组，减少移动操作的次数；

最长递增子序列算法实现：

/*

寻找最长递增子序列

使用动态规划思想，a -> c = a -> b + b -> c

其中p数组存储的是从p[p[i]] 到 p[i] 的最长递增子序列索引，也就是前一个b的索引；

r数组存储最后一个元素也就是c的索引

*/