vue2和vue3Diff算法

基本原理

Vue2

• 双端比较：使用双端（头尾）比较的方法，设置指针分别指向新旧节点列表的开始和结束，依次比较节点，寻找可复用的节点。
• 暴力更新：当新旧节点不匹配时，Vue2 可能会进行全量更新，即使是小的变化也可能导致整个子树的重新渲染。

Vue3

• 优化的快速 diff 算法：引入了更高效的 diff 算法，通过创建一个映射表来记录新旧节点的位置，并利用最长递增子序列（LIS）算法来优化节点的移动。
• 静态节点处理：对静态节点进行特殊处理，避免对这些节点进行不必要的比较，从而进一步提升性能。

性能优化

Vue2

• 时间复杂度：在最坏情况下，时间复杂度为 O(n³)，这在大型应用中可能导致性能瓶颈。
• 优化策略：虽然有一些优化策略（如头尾对比、交叉对比），但整体上仍然依赖于较多的遍历和比较操作。

Vue3

• 时间复杂度降低：通过引入映射表和 LIS 算法，Vue3 的 diff 算法将时间复杂度降低到 𝑂(𝑛)，使得在处理大量节点时更加高效。
• 更少的 DOM 操作：由于能够更好地复用现有节点，Vue3 在更新视图时减少了对 DOM 的直接操作，这不仅提高了性能，也改善了用户体验。

实现细节

Vue2

• 使用 updateChildren 函数进行子节点的比较和更新，通过循环遍历所有子节点来寻找差异。
• 在处理数组时，使用双指针从头部和尾部同时向中间遍历，以寻找可复用的节点。

Vue3

• 引入了 isSameVNodeType 函数来判断两个虚拟节点是否相同，并在此基础上进行更细粒度的更新操作。
• 通过映射表快速查找旧节点的位置，大幅提升了查找效率，并使用 LIS 算法来确定哪些节点可以原地复用。

具体步骤对比

Vue2 的 Diff 流程

1. 初始化指针：设置四个指针（oldStartIdx, oldEndIdx, newStartIdx, newEndIdx）指向新旧 VNode 列表。
2. 首尾比较：从前往后和从后往前同时比较，找到相同的节点并进行 patch。
3. 交叉比较：如果未找到匹配项，则交叉比较。
4. 新增和删除：处理剩余的新旧节点，进行新增或删除操作。

Vue3 的 Diff 流程

1. 前置和后置处理：首先处理前置和后置相同的节点。
2. 构建映射表：创建一个映射表记录新 VNode 在旧 VNode 中的位置索引。
3. 计算最长递增子序列（LIS）：利用 LIS 确定哪些新节点可以原地复用。
4. 移动和插入操作：根据 LIS 和映射表进行 DOM 的移动和插入。

代码demo

示例场景

我们将创建一个简单的列表组件，初始渲染的列表如下：

<ul id="app">   
	<li key="1">Item 1</li>  
	<li key="2">Item 2</li>  
	<li key="3">Item 3</li> 
</ul>

当我们更新这个列表，新的列表变为：

<ul id="app">   
	<li key="2">Item 2</li> 
	<li key="4">Item 4</li> 
	<li key="3">Item 3</li> 
</ul>

在这个更新中，我们删除了 Item 1，添加了 Item 4，并保持了 Item 2 和 Item 3。

Vue2 Diff 算法实现

以下是 Vue2 的 diff 算法的简化实现，主要通过双端比较来处理节点。

function sameVNode(a, b) {
    return a.key === b.key; // 比较节点的 key
}

function patch(oldVnode, vnode) {
    // 如果节点相同，直接复用
    if (oldVnode === vnode) return;

    // 更新节点属性（省略具体实现）
    // updateProps(oldVnode, vnode);

    const oldCh = oldVnode.children || [];
    const newCh = vnode.children || [];

    updateChildren(oldVnode.elm, oldCh, newCh);
}

function updateChildren(parentElm, oldCh, newCh) {
    let oldStartIdx = 0, oldEndIdx = oldCh.length - 1;
    let newStartIdx = 0, newEndIdx = newCh.length - 1;

    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
        if (sameVNode(oldCh[oldStartIdx], newCh[newStartIdx])) {
            patch(oldCh[oldStartIdx], newCh[newStartIdx]);
            oldStartIdx++;
            newStartIdx++;
        } else if (sameVNode(oldCh[oldEndIdx], newCh[newEndIdx])) {
            patch(oldCh[oldEndIdx], newCh[newEndIdx]);
            oldEndIdx--;
            newEndIdx--;
        } else {
            break; // 停止比较
        }
    }

    // 新增节点
    if (newStartIdx <= newEndIdx) {
        for (let i = newStartIdx; i <= newEndIdx; i++) {
            addVnode(parentElm, newCh[i]); // 添加新节点
        }
    }

    // 删除节点
    if (oldStartIdx <= oldEndIdx) {
        for (let i = oldStartIdx; i <= oldEndIdx; i++) {
            removeVnode(parentElm, oldCh[i]); // 删除旧节点
        }
    }
}

function addVnode(parentElm, vnode) {
    const el = document.createElement('li');
    el.textContent = vnode.text;
    parentElm.appendChild(el);
}

function removeVnode(parentElm, vnode) {
    const el = parentElm.querySelector(`li[key="${vnode.key}"]`);
    if (el) parentElm.removeChild(el);
}

Vue3 Diff 算法实现

以下是 Vue3 的 diff 算法的简化实现，主要通过映射表和最长递增子序列（LIS）来优化节点处理。

function isSameVNodeType(a, b) {
    return a.key === b.key; // 比较节点的 key
}

function patch(oldVNode, vNode) {
    if (oldVNode === vNode) return;

    // 更新节点属性（省略具体实现）
    
    const oldChildren = oldVNode.children || [];
    const newChildren = vNode.children || [];

    updateChildren(oldVNode.elm, oldChildren, newChildren);
}

function updateChildren(parentElm, oldCh, newCh) {
    let oldStartIdx = 0, oldEndIdx = oldCh.length - 1;
    let newStartIdx = 0, newEndIdx = newCh.length - 1;

    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
        if (isSameVNodeType(oldCh[oldStartIdx], newCh[newStartIdx])) {
            patch(oldCh[oldStartIdx], newCh[newStartIdx]);
            oldStartIdx++;
            newStartIdx++;
        } else if (isSameVNodeType(oldCh[oldEndIdx], newCh[newEndIdx])) {
            patch(oldCh[oldEndIdx], newCh[newEndIdx]);
            oldEndIdx--;
            newEndIdx--;
        } else {
            break; // 停止比较
        }
    }

    const keyToIndexMap = {};
    
    for (let i = oldStartIdx; i <= oldEndIdx; i++) {
        keyToIndexMap[oldCh[i].key] = i; // 构建映射表
    }

    const toMove = [];
    
    for (let i = newStartIdx; i <= newEndIdx; i++) {
        const key = newCh[i].key;
        const moveIndex = keyToIndexMap[key];
        
        if (moveIndex !== undefined) {
            toMove.push({ index: moveIndex, vnode: oldCh[moveIndex] });
        } else {
            addVnode(parentElm, newCh[i]); // 新增节点
        }
    }

    // 使用 LIS 确定移动顺序
    const lisIndices = calculateLIS(toMove.map(item => item.index));
    
    for (const index of lisIndices) {
        moveNode(parentElm, toMove[index].vnode); // 移动节点到正确位置
    }

    // 删除多余的旧节点
    for (let i = oldStartIdx; i <= oldEndIdx; i++) {
        removeVnode(parentElm, oldCh[i]);
    }
}

function calculateLIS(arr) {
   const lis = [];
   for (const value of arr) {
       let left = 0;
       let right = lis.length;

       while (left < right) {
           const mid = Math.floor((left + right) / 2);
           if (lis[mid] < value) left = mid + 1;
           else right = mid;
       }

       if (left >= lis.length) lis.push(value);
       else lis[left] = value;
   }
   return lis;
}

function addVnode(parentElm, vnode) {
   const el = document.createElement('li');
   el.textContent = vnode.text;
   parentElm.appendChild(el);
}

function removeVnode(parentElm, vnode) {
   const el = parentElm.querySelector(`li[key="${vnode.key}"]`);
   if (el) parentElm.removeChild(el);
}

function moveNode(parentElm, vnode) {
   const el = parentElm.querySelector(`li[key="${vnode.key}"]`);
   if (el && el !== parentElm.lastChild) { 
       parentElm.appendChild(el); // 移动到父元素最后
   }
}