diff算法
# diff 算法面试题
# vue2 diff 算法回答
diff 算法是一种通过同层的树节点进行比较的高效算法
两个特点：
（1） 比较只会在同层级进行, 不会跨层级比较
（2） 在 diff 比较的过程中，循环从两边向中间比较
使用场景：在 vue 中，作用于虚拟 dom 渲染成真实 dom 的新旧 VNode 节点比较
比较方式：diff 整体策略为：深度优先，同层比较
比较过程：首先，我们拿到新旧节点的数组，然后初始化四个指针，分别指向新旧节点的开始位置和结束位置，进行两两对比，若是 新的开始节点和旧开始节点相同，则都向后面移动，若是结尾节点相匹配，则都前移指针。若是新开始节点和旧结尾节点匹配上了，则会将旧的结束节点移动到旧的开始节点前。若是旧开始节点和新的结束节点相匹配，则会将旧开始节点移动到旧结束节点的后面。若是上述节点都没配有匹配上，则会进行一个兜底逻辑的判断，判断开始节点是否在旧节点中，若是存在则复用，若是不存在则创建。最终跳出循环，进行裁剪或者新增，若是旧的开始节点小于旧的结束节点，则会删除之间的节点，反之则是新增新的开始节点到新的结束节点。
# vue3 diff 算法的优化
- 静态标记
vue2 对比是进行全量的比较：在 Vue2.0 当中，当数据发生变化，它就会新生成一个 DOM 树，并和之前的 DOM 树进行比较，找到不同的节点然后更新。但这比较的过程是全量的比较
在 vue2 中 只要有某一个属性是动态的，那么这个元素都要 diff
vue3 采取的是优化静态标记(即使是动态节点，也只 diff 动态的模块)
Vue3.0 对于不参与更新的元素，做静态标记并提示，只会被创建一次，在渲染时直接复用
参考：https://www.jianshu.com/p/27643bf1b15c (opens new window)
- 静态提升
Vue3 中对不参与更新的元素，会做静态提升，只会被创建一次，在渲染时直接复用，这样就免去了重复的创建节点，大型应用会受益于这个改动，免去了重复的创建操作，优化了运行时候的内存占用
- 对比过程
vue3 diff 对比过程：
（1） 头和头比：先进行头和头比，发现不同就结束循环
（2） 尾和尾比：再进行尾和尾比，发现不同就结束循环
（3） 基于最长递增子序列进行移动/添加/删除
使用最长递增子序列可以最大程度的减少 DOM 的移动，达到最少的 DOM 操作
# Diff 算法回答模板
是什么
性能、好处：跨平台+兼容性
在什么地方使用，落地：在 patch 打补丁时，存在新旧虚拟 dom 时
怎么比较的：总体来说，深度优先+同层比较
# vue2 diff 算法
优化的 diff 算法时间复杂度：O(n)
优化的 diff 算法：深度优先算法，比较新旧节点只会在同层级进行, 不会跨层级比较。
Diff 算法就是 patch（打补丁）过程：
创建节点：新的 VNode 中有而旧的 oldVNode 中没有，就在旧的 oldVNode 中创建。
删除节点：新的 VNode 中没有而旧的 oldVNode 中有，就从旧的 oldVNode 中删除。
更新节点：新的 VNode 和旧的 oldVNode 中都有，就以新的 VNode 为准，更新旧的 oldVNode。
diff 算法原理：
diff 过程整体遵循深度优先，同层比较的策略；
两个节点之间的比较会根据他们是否拥有子节点或者文本节点做不同的操作，
比较两组子节点是算法的重点，首先假设头尾节点可能相同，做 4 次对比尝试，
如果没有找到相同的节点才按照通用方式遍历查找，查找结束再按照情况处理剩下的节点，
借助 key 通常可以非常精确的找到相同的节点，因此整个 patch 过程会非常的高效
# diff 对比原则
对比原则 1：逐层对比
第一层不一样，直接替换；第一层一样，进行第二层对比……
对比原则 2：从两边向中间
新旧元素的子节点首尾两两对比，有相同的，则放到新元素对应的位置；不相同就向中间移动，再次对比
# 传统的 diff 算法
传统的 diff 算法时间复杂度：O(n³)
传统 Diff 算法需要找到两个树的最小更新方式，所以需要两两对比每个叶子节点是否相同，对比就需要 O(n^2)次了，再加上更新（移动、创建、删除）时需要遍历一次，所以是 O(n^3)。
# vue2 diff 痛点
vue2.x 中的虚拟 dom 是进行**全量的对比**，在运行时会对所有节点生成一个虚拟节点树，当页面数据发生变更好，会遍历判断 virtual dom 所有节点（包括一些不会变化的节点）有没有发生变化；虽然说 diff 算法确实减少了多 DOM 节点的直接操作，但是这个减少是有成本的，如果是复杂的大型项目，必然存在很复杂的父子关系的 VNode,而 Vue2.x 的 diff 算法，会不断地递归调用 patchVNode，不断堆叠而成的几毫秒，最终就会造成 VNode 更新缓慢。
# vue3 diff 算法
vue2 核心 diff 算法 采用的是双端比较算法
vue3 核心 diff 算法采用的是去头尾的最长递增子序列算法
vue3 diff 对比过程：
头和头比：先进行头和头比，发现不同就结束循环
尾和尾比：再进行尾和尾比，发现不同就结束循环
基于最长递增子序列进行移动/添加/删除
使用最长递增子序列可以最大程度的减少 DOM 的移动，达到最少的 DOM 操作
最长递增子序列问题描述：在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。最长递增子序列中的元素在原序列中不一定是连续的。解决最长递增子序列问题的算法最低要求 O(n log n)的时间复杂度，这里 n 表示输入序列的规模。
最长递增子序列解决方案：
动态规划：算法的时间复杂度是 O(n2)，
vue3 内部使用的是“贪心 + 二分查找”的算法，贪心算法的时间复杂度是 O(n)，二分查找的时间复杂度是 O(logn)，所以它的总时间复杂度是 O(nlogn)。