diff 算法--快速diff实现

核心思路

1. 相较于双端diff，快速diff先对新旧节点进行了头尾的预处理，找出头部与尾部开始的相同节点，并对非相同部分进行移动处理
2. 根据预处理后新节点剩余部分构建数组 source 用于依次存储剩余 newChildred 中的节点在 oldChilren 的 idx，若为新增则值为 -1
3. 构建一个索引表 keyIdx，存储新节点中的某一个节点对应的在 newChildren 中的 idx，用于填充 source
4. 遍历 oldChildren 部分，根据 key 值从索引表 keyIdx 中获取此节点在 newChildren 中的idx，存储为 k
   4.1 若k不存在，则说明该旧节点需要删除
   4.2 若k存在，更新 source
5. 使用 lis 获取 source 的最长子序列 seq。
6. 循环预处理后的newChilren剩余节点，判断当前位置是否处于 最长子序列（不用移动）上，进行插入或移动

快速 Diff 算法在实测中性能最优。它借鉴了文本 Diff 中的预处理 思路，先处理新旧两组子节点中相同的前置节点和相同的后置节点。 当前置节点和后置节点全部处理完毕后，如果无法简单地通过挂载新 节点或者卸载已经不存在的节点来完成更新，则需要根据节点的索引 关系，构造出一个最长递增子序列。最长递增子序列所指向的节点即 为不需要移动的节点

实现效果

使用代码

import {
    patchChildrenFast } from './fastDiff.js';
import cloneFn from '../../CloneDeep/forClone.js'; // 引入深拷贝
const fastNewNode = [
    {
    key: 1 },
    {
    key: 2 },
    {
    key: 3 },
    {
    key: 4 },
    {
    key: 6 },
    {
    key: 9 },
    {
    key: 12 },
    {
    key: 5 }
]
const fastOldNode = [
    {
    key: 1 },
    {
    key: 2 },
    {
    key: 21 },
    {
    key: 4 },
    {
    key: 6 },
    {
    key: 12 },
    {
    key: 10 },
    {
    key: 9 },
    {
    key: 5 }
]
const {
    container, moveRecord } = patchChildrenFast(fastOldNode, fastNewNode, cloneFn(fastOldNode));
console.log(moveRecord);
console.log(container);

输出：

moveRecord：
[
  'delete 21',
  'delete 10',
  'move   : 12-> 5 before',
  'insert : 3 -> 4 before'
]
container：
[
  {
    key: 1 },
  {
    key: 2 },
  {
    key: 3 },
  {
    key: 4 },
  {
    key: 6 },
  {
    key: