腳本之家服務器常用軟件

快捷導航

Vue3 diff算法的簡單解刨

更新時間：2023年02月09日 08:44:22 作者：mick

如今Vue3的勢頭正盛，在diff算法方面也做了相應的變化，利用到了最長遞增子序列把性能又提升了一個檔次。本文就來帶大家簡單解刨一下Vue3中的diff算法

上篇我們介紹了vue2中的雙端diff算法的優(yōu)勢（相比于簡單算法相同場景下移動DOM次數(shù)更少）。如今Vue3的勢頭正盛，在diff算法方面也做了相應的變化，利用到了最長遞增子序列把性能又提升了一個檔次。對于技術棧使用Vue的同學來說又是必須要學習的一部分。

性能比較

此圖借鑒了《Vuejs設計與實現(xiàn)》這本書

ivi和inferno所采用的快速diff算法的性能要稍優(yōu)于Vue2的雙端diff算法。既然快速diff算法這么高效，我們當然有必要了解它咯。

前置與后置的預處理

這里有兩組子節(jié)點，c1表示老的子節(jié)點，c2表示新的子節(jié)點。首先將從c1和c2的頭部節(jié)點開始對比，如果節(jié)點相同則通過patch更新節(jié)點的內容。e1表示老的子節(jié)點的尾部索引，e2表示新的子節(jié)點的尾部索引。

while (i <= e1 && i <= e2) {
      const n1 = c1[i]
      const n2 = (c2[i] = optimized
        ? cloneIfMounted(c2[i] as VNode)
        : normalizeVNode(c2[i]))
        // 如果節(jié)點相同 則進行遞歸執(zhí)行patch更新節(jié)點
      if (isSameVNodeType(n1, n2)) {
        patch(
          n1,
          n2,
          container,
          null,
          parentComponent,
          parentSuspense,
          isSVG,
          slotScopeIds,
          optimized
        )
      } else {
        // 如果節(jié)點不相同，則直接退出
        break
      }
      i++
}

然后將索引遞增，發(fā)現(xiàn)c1中節(jié)點B和c2中節(jié)點D不是同一節(jié)點，則循環(huán)退出。接著將從c1和c2的尾部節(jié)點開始對比，如果節(jié)點相同則通過patch更新節(jié)點的內容。

while (i <= e1 && i <= e2) {
      const n1 = c1[e1]
      const n2 = (c2[e2] = optimized
        ? cloneIfMounted(c2[e2] as VNode)
        : normalizeVNode(c2[e2]))
        // 如果是相同節(jié)點 則遞歸執(zhí)行patch
      if (isSameVNodeType(n1, n2)) {
        patch(
          n1,
          n2,
          container,
          null,
          parentComponent,
          parentSuspense,
          isSVG,
          slotScopeIds,
          optimized
        )
      } else {
        // 如果節(jié)點不相同 則退出
        break
      }
      e1--
      e2--
}

此過程經歷了c1的節(jié)點C和c2的節(jié)點C對比，c1的節(jié)點B和c2的節(jié)點B對比,節(jié)點相同則通過patch更新節(jié)點的內容,每次循環(huán)e1 e2向前推進。當循環(huán)到了c1中節(jié)點B和c2中節(jié)點D不是同一節(jié)點，則循環(huán)退出

此時當新節(jié)點中還有剩余，則需要添加新節(jié)點。相反的，如果舊節(jié)點有剩余需要刪除舊節(jié)點

if (i > e1) {
      // 當索引大于老節(jié)點的尾部
      if (i <= e2) {
        // 當索引小于新節(jié)點的尾部 需要將剩余的節(jié)點添加
        const nextPos = e2 + 1
        const anchor = nextPos < l2 ? (c2[nextPos] as VNode).el : parentAnchor
        while (i <= e2) {
          patch(
            null,
            (c2[i] = optimized
              ? cloneIfMounted(c2[i] as VNode)
              : normalizeVNode(c2[i])),
            container,
            anchor,
            parentComponent,
            parentSuspense,
            isSVG,
            slotScopeIds,
            optimized
          )
          i++
        }
      }
}

else if (i > e2) {
      // 當索引i大于尾部索引e2 則直接刪除舊子樹從索引i開始到e1部分的節(jié)點
      while (i <= e1) {
        unmount(c1[i], parentComponent, parentSuspense, true)
        i++
      }
}

上面的情況是有序的，下面我們看下無序的情況

節(jié)點無序

上圖是經過上面的兩層循環(huán)之后的結果。我們首先看下代碼,由于節(jié)點無序情況的代碼比較長，我們一段段的解刨

const s1 = i // prev starting index  舊子序列開始索引 從i開始記錄
const s2 = i // next starting index  新子序列開始索引 從i開始記錄

// 5.1 build key:index map for newChildren
// 根據key 建立新子序列的索引圖
const keyToNewIndexMap: Map<string | number | symbol, number> = new Map()
for (i = s2; i <= e2; i++) {
    // 獲取新節(jié)點
    const nextChild = (c2[i] = optimized
      ? cloneIfMounted(c2[i] as VNode)
      : normalizeVNode(c2[i]))
    if (nextChild.key != null) {
      if (__DEV__ && keyToNewIndexMap.has(nextChild.key)) {
        warn(
          `Duplicate keys found during update:`,
          JSON.stringify(nextChild.key),
          `Make sure keys are unique.`
        )
      }
      //  根據新節(jié)點的key 和 對應的索引做映射關系
      // <key, index>
      keyToNewIndexMap.set(nextChild.key, i)
    }
}
let j
// 新子序列已經更新的節(jié)點數(shù)量
let patched = 0
// 新子序列待更新節(jié)點的數(shù)量，等于新子序列的長度
const toBePatched = e2 - s2 + 1
// 是否存在需要移動的節(jié)點
let moved = false
// 用于跟蹤判斷是否有節(jié)點需要移動的節(jié)點
let maxNewIndexSoFar = 0
// 這個數(shù)組存儲新子序列中的元素在舊子序列節(jié)點出的索引，用于確定最長遞增子序列
const newIndexToOldIndexMap = new Array(toBePatched)
// 初始化數(shù)組 為0
// 0是一個特殊的值，如果遍歷之后仍有元素的值為0，則說明這個新節(jié)點沒有對應的舊節(jié)點
for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0

s1表示舊子節(jié)點開始遍歷的索引，從i開始記錄，s2表示新子節(jié)點開始遍歷的索引，也從i開始記錄。根據新子節(jié)點的key建立新子序列的索引圖keyToNewIndexMap。patched表示新子序列已經更新的節(jié)點數(shù)量，toBePatched表示新子序列待更新節(jié)點的數(shù)量，等于新子序列的長度。moved表示是否存在需要移動的節(jié)點。maxNewIndexSoFar用于跟蹤判斷是否有節(jié)點需要移動的節(jié)點。newIndexToOldIndexMap存儲新子序列中的節(jié)點在舊子序列節(jié)點的索引，用于確定最長遞增子序列，初始化全部為0，0是一個特殊的值，如果遍歷之后仍有元素的值為0，則說明這個新節(jié)點沒有對應的舊節(jié)點。我們在圖中表示一下

然后正序遍歷舊子序列

// 正序遍歷舊子序列
for (i = s1; i <= e1; i++) {
    const prevChild = c1[i]
    if (patched >= toBePatched) {
      // 所有新的子序列節(jié)點都已經更新，刪除剩余的節(jié)點
      // all new children have been patched so this can only be a removal
      unmount(prevChild, parentComponent, parentSuspense, true)
      continue
    }

    let newIndex
    if (prevChild.key != null) {
      // 查找舊子序列中的節(jié)點在新子序列中的索引
      newIndex = keyToNewIndexMap.get(prevChild.key)
    } else {
      // key-less node, try to locate a key-less node of the same type
      for (j = s2; j <= e2; j++) {
        if (
          newIndexToOldIndexMap[j - s2] === 0 &&
          isSameVNodeType(prevChild, c2[j] as VNode)
        ) {
          newIndex = j
          break
        }
      }
    }
    if (newIndex === undefined) {
      // 找不到說明舊子序列需要刪除
      unmount(prevChild, parentComponent, parentSuspense, true)
    } else {
      // 更新新子序列中的元素在舊子序列中的索引，這里 +1 偏移是為了避免i為0的特殊情況 影響后面最長遞增子序列的求解
      newIndexToOldIndexMap[newIndex - s2] = i + 1
      //maxNewIndexSoFar 存儲的是上次舊值的newIndex 如果不是一直遞增 則說明有移動 
      if (newIndex >= maxNewIndexSoFar) {
        maxNewIndexSoFar = newIndex
      } else {
        moved = true
      }
      patch(
        prevChild,
        c2[newIndex] as VNode,
        container,
        null,
        parentComponent,
        parentSuspense,
        isSVG,
        slotScopeIds,
        optimized處
      )
      patched++
    }
}

每次遍歷拿到舊子節(jié)點的值prevChild，如果patched >= toBePatched也就是說新子序列已經更新的節(jié)點數(shù)量大于等于待更新的節(jié)點數(shù)量，說明新子序列的所有節(jié)點更新完畢，舊子序列中剩余的節(jié)點刪除即可。

如果每次循環(huán)拿到的舊子節(jié)點的值的key存在，則查找舊子序列中的節(jié)點在新子序列中的索引標記為newIndex。如果key不存在，則遍歷新子序列待更新的節(jié)點，如果prevChild和遍歷新子序列待更新的節(jié)點有相同的節(jié)點，則將索引賦值給newIndex。接著判斷newIndex是否存在，如果不存在，則說明新子序列中找不到舊子序列中的這個節(jié)點，則直接刪除。如果存在，則更新新子序列中的元素在舊子序列中的索引，這里 ‘+1’ 偏移是為了避免i為0的特殊情況，影響后面最長遞增子序列的求解，因為我們現(xiàn)在規(guī)定的newIndexToOldIndexMap中的元素為0說明這個元素沒有對應的老節(jié)點，如果不'+1'我們避免不了i為0的情況，這樣就影響了最長遞增子序列的求解。我們看下newIndexToOldIndexMap重新賦值之后的結果

maxNewIndexSoFar存儲的是上次舊值的newIndex,如果不是一直遞增則說明有移動，則moved設置為ture。然后將newIndex對應的新節(jié)點和prevChild老節(jié)點進行patch，然后patched++記錄更新的次數(shù)。

我們繼續(xù)看下面的代碼

const increasingNewIndexSequence = moved
        ? getSequence(newIndexToOldIndexMap)
        : EMPTY_ARR
j = increasingNewIndexSequence.length - 1
// 倒序遍歷 以便使用更新的節(jié)點作為錨點
for (i = toBePatched - 1; i >= 0; i--) {
    const nextIndex = s2 + i
    const nextChild = c2[nextIndex] as VNode
    // 錨點指向上一個更新的節(jié)點， 如果nextIndex超過新節(jié)點的長度，則指向parentAnchor
    const anchor =
      nextIndex + 1 < l2 ? (c2[nextIndex + 1] as VNode).el : parentAnchor
    if (newIndexToOldIndexMap[i] === 0) {
      // mount new
      // 掛載新節(jié)點
      patch(
        null,
        nextChild,
        container,
        anchor,
        parentComponent,
        parentSuspense,
        isSVG,
        slotScopeIds,
        optimized
      )
    } else if (moved) {
      // 沒有最長遞增子序列或者當前節(jié)點索引不在最長遞增子序列中， 需要移動
      if (j < 0 || i !== increasingNewIndexSequence[j]) {
        move(nextChild, container, anchor, MoveType.REORDER)
      } else {
        j--
      }
    }
}

首先判斷是否需要移動，如果需要移動怎么才能以移動最少的步數(shù)完成更新呢？這就需要用到最長遞增子序列（getSequence這個方法代碼我們貼到文章最后)。我們得到了最長遞增子序列的索引值的集合increasingNewIndexSequence，我們看下結果。

根據結果我們發(fā)現(xiàn)在newIndexToOldIndexMap中只有索引為0和1的節(jié)點是遞增的，所以只有這兩個對應的舊的子序列的節(jié)點是不需要移動的，其他的則需要移動。

倒序遍歷。為什么要倒序遍歷呢？因為我們將節(jié)點插入到已經更新的節(jié)點前面(從后往前遍歷可以始終保持當前遍歷的節(jié)點的下一個節(jié)點是更新過的)這里使用的是insertBefore。

比如這個例子節(jié)點‘G’就要插入到節(jié)點‘E’的前面，節(jié)點‘E’是已經更新過的了。

繼續(xù)往前推進，節(jié)點‘B’不在最長遞增子序列increasingNewIndexSequence中，所以需要移動。然后拿到節(jié)點‘B’對應的el插入到節(jié)點‘G’的前面。這個節(jié)點‘B’的el我們從節(jié)點‘B’的Vnode上面就可以獲取到了。因為當兩個新舊節(jié)點進行對比的時候會進行下面的操作

以上就是我們要介紹的Vue3的diff算法的核心內容

總結

有序的情況比較簡單，我們就直接說無序的情況。

1.根據key建立新子序列的索引圖 keyToNewIndexMap

通過遍歷新子序列的節(jié)點將key和index映射

2.根據新子序列中待更新節(jié)點的數(shù)量toBePatched創(chuàng)建數(shù)組newIndexToOldIndexMap數(shù)組初始化為0

這個數(shù)組就是保存新子序列中的節(jié)點在舊子序列中的索引位置。

3.遍歷舊子節(jié)點拿舊的子節(jié)點去keyToNewIndexMap中找對應新子節(jié)點的位置

如果找不到則說明這個節(jié)點在新的子節(jié)點中沒有則刪除
找到了之后則更新newIndexToOldIndexMap,數(shù)組中的元素被重新賦值為新子序列中的節(jié)點在舊子序列中的索引位置，為0的元素說明這個節(jié)點是新增的。
將新舊子節(jié)點對比更新

4.通過最長遞增子序列找到那些節(jié)點是需要移動的，哪些節(jié)點是不需要的移動的

最長遞增子序列

// https://en.wikipedia.org/wiki/Longest_increasing_subsequence
function getSequence(arr: number[]): number[] {
  const p = arr.slice()
  const result = [0]
  let i, j, u, v, c
  const len = arr.length
  for (i = 0; i < len; i++) {
    // arrI 為當前順序取出的元素
    const arrI = arr[i]
    // 排除0的情況
    if (arrI !== 0) {
      // result 存儲的是長度為i的遞增子序列最小末尾值的索引 
      j = result[result.length - 1]
      // arr[j]為末位置，如果滿足arr[j]<arrI 那么直接在當前遞增子序列后面添加
      if (arr[j] < arrI) {
        // 存儲result更新前的最后一個索引的值
        p[i] = j
        // 存儲元素對應的索引值
        result.push(i)
        continue
      }
      // 不滿足 則執(zhí)行二分搜索
      u = 0
      v = result.length - 1
      // 查找第一個比arrI小的節(jié)點，更新result的值
      while (u < v) {
        // c記錄中間的位置
        c = (u + v) >> 1
        if (arr[result[c]] < arrI) {
          // 若中間的值小于arrI 則在后邊 更新下沿
          u = c + 1
        } else {
          // 更新下沿
          v = c
        }
      }
      // 找到第一個比arrI小的位置u，插入它
      if (arrI < arr[result[u]]) {
        if (u > 0) {
          p[i] = result[u - 1]
        }
        result[u] = i
      }
    }
  }
  u = result.length
  v = result[u - 1]
  while (u-- > 0) {
    result[u] = v
    v = p[v]
  }
  return result
}

以上就是Vue3 diff算法的簡單解刨的詳細內容，更多關于Vue3 diff算法的資料請關注腳本之家其它相關文章！

您可能感興趣的文章: