// vnode對(duì)象
const a = {
  type: 'div', // 標(biāo)簽
  props: {style: {color: 'red'}}, // 屬性
  children: [], // 子元素
  key: 'key1', // key
  el: '&lt;div style="color: 'red'"&gt;&lt;/div&gt;', // 真實(shí)dom節(jié)點(diǎn)
  ...
}

二、找規(guī)律

去掉前面和后面相同的部分

// c1表示舊的子節(jié)點(diǎn)，c2表示新的子節(jié)點(diǎn)
const patchKeyedChildren = (c1, c2) =&gt; {
  let i = 0
  let e1 = c1.length - 1
  let e2 = c2.length - 1
  // 從前面比
  while (i &lt;= e1 &amp;&amp; i &lt;= e2) {
    const n1 = c1[i]
    const n2 = c2[i]
    // 標(biāo)簽和key是否相同
    // if (n1.type === n2.type &amp;&amp; n1.key === n2.key)
    if (n1 === n2) {
      // 繼續(xù)對(duì)比其屬性和子節(jié)點(diǎn)
    } else {
      break
    }
    i++
  }
  // 從后面比
  while (i &lt;= e1 &amp;&amp; i &lt;= e2) {
    const n1 = c1[e1]
    const n2 = c2[e2]
    // 標(biāo)簽和key是否相同
    // if (n1.type === n2.type &amp;&amp; n1.key === n2.key)
    if (n1 === n2) {
      // 繼續(xù)對(duì)比其屬性和子節(jié)點(diǎn)
    } else {
      break
    }
    e1--
    e2--
  }
  console.log(i, e1, e2)
}
// 調(diào)用示例
patchKeyedChildren(['a', 'b', 'c', 'd'], ['a', 'b', 'c'])

通過(guò)這個(gè)函數(shù)可以得到：

1.

舊的：a b c
新的：a b c d

i = 3 e1 = 2 e2 = 3

2.

舊的： a b c
新的：d a b c

i = 0 e1 = -1 e2 = 0

3.

舊的：a b c d
新的：a b c

i = 3 e1 = 3 e2 = 2

4.

舊的：d a b c
新的： a b c

i = 0 e1 = 0 e2 = -1

5.

舊的：a b c d e i f g
新的：a b e c d h f g

i = 2 e1 = 5 e2 = 5

擴(kuò)展：

舊的：a b c
新的：a b c d e f
i = 3 e1 = 2 e2 = 5

舊的：a b c
新的：a b c
i = 3 e1 = 2 e2 = 2

舊的：e d a b c
新的： a b c
i = 0 e1 = 1 e2 = -1

舊的：c d e
新的：e c d h
i = 0 e1 = 2 e2 = 3

從上面結(jié)果中我們可以找到規(guī)律：

當(dāng)i大于e1時(shí)，只需添加新的子節(jié)點(diǎn)
當(dāng)i大于e2時(shí)，只需刪除舊的子節(jié)點(diǎn)

// 當(dāng)i大于e1時(shí)
if (i > e1) {
  if (i <= e2) {
    while (i <= e2) {
      const nextPos = e2 + 1
      const anchor = nextPos < c2.length ? c2[nextPos].el : null
      // 添加新的子節(jié)點(diǎn)c2[i]在anchor的前面
      // todo
      i++
    }
  }
}
// 當(dāng)i大于e2時(shí)
else if (i > e2) {
  if (i <= e1) {
    while (i <= e1) {
      // 刪除舊的子節(jié)點(diǎn)c1[i]
      // todo
      i++
    }
  }
}

其它，特殊處理

// 其它
let s1 = i
let s2 = i
// 以新的子節(jié)點(diǎn)作為參照物
const keyToNewIndexMap = new Map()
for (let i = s2; i <= e2; i++) {
  // 節(jié)點(diǎn)的key做為唯一值
  // keyToNewIndexMap.set(c2[i].key, i)
  keyToNewIndexMap.set(c2[i], i)
}
// 新的總個(gè)數(shù)
const toBePatched = e2 - s2 + 1
// 記錄新子節(jié)點(diǎn)在舊子節(jié)點(diǎn)中的索引
const newIndexToOldIndexMap = new Array(toBePatched).fill(0)
// 循環(huán)老的子節(jié)點(diǎn)
for (let i = s1; i <= e1; i++) {
  const oldChild = c1[i]
  // let newIndex = keyToNewIndexMap.get(oldChild.key)
  let newIndex = keyToNewIndexMap.get(oldChild)
  // 在新子節(jié)點(diǎn)中不存在
  if (newIndex === undefined) {
    // 刪除oldChild
    // todo
  } else {
    newIndexToOldIndexMap[newIndex - s2] = i + 1 // 永遠(yuǎn)不會(huì)等于0, 這樣0就可以表示需要?jiǎng)?chuàng)建了
    // 繼續(xù)對(duì)比其屬性和子節(jié)點(diǎn)
    // todo
  }
}
console.log(newIndexToOldIndexMap)
// 需要移動(dòng)位置
for (let i = toBePatched - 1; i >= 0; i--) {
  let index = i + s2
  let current = c2[index]
  let anchor = index + 1 < c2.length ? c2[index + 1].el : null
  if (newIndexToOldIndexMap[i] === 0) {
    // 在anchor前面插入新的節(jié)點(diǎn)current
    // todo
  } else {
    // 在anchor前面插入對(duì)應(yīng)舊節(jié)點(diǎn).el，current.el元素等于對(duì)應(yīng)的舊節(jié)點(diǎn).el（在其它代碼中賦值了）
    // todo
  }
}

第1種和第2種比較簡(jiǎn)單，不做過(guò)多的講解，我們來(lái)看看第3種，以下面為例

序號(hào)： 0 1 2 3 4 5 6 7
舊的：(a b) c d e i (f g)
新的：(a b) e c d h (f g)

前面a b和后面f g是一樣的，會(huì)去掉，只剩中間亂序部分
以新的節(jié)點(diǎn)為參照物，循環(huán)舊的節(jié)點(diǎn)，從舊的節(jié)點(diǎn)中去掉新的沒(méi)有的節(jié)點(diǎn)，如i
標(biāo)記舊的中沒(méi)有的節(jié)點(diǎn)，沒(méi)有就為0，表示需要?jiǎng)?chuàng)建；有就序號(hào)+1，表示可以復(fù)用

標(biāo)記： 4+1 2+1 3+1 0
新的：(...) e c d h (...)

從后往前循壞，h為0，創(chuàng)建，放在它下一個(gè)f前面；d不為0，復(fù)用舊的中的d，放在h前面；c不為0，復(fù)用舊的中的c，放在d前面；e不為0，復(fù)用舊的中的e，放在c前面

到目的為止，新舊元素的更替已經(jīng)全部完成，但大家有沒(méi)有發(fā)現(xiàn)一個(gè)問(wèn)題，e c d h四個(gè)元素都移動(dòng)了一次，我們可以看出如果只移動(dòng)e和創(chuàng)建h，c和d保持不變，效率會(huì)更高

三、算法優(yōu)化

1.

序號(hào)： 0 1 2 3 4 5 6 7
舊的：(a b) c d e i (f g)
新的：(a b) e c d h (f g)
對(duì)應(yīng)的標(biāo)記是[5, 3, 4, 0]

2.

序號(hào)：0 1 2 3 4 5
舊的：c d e i f g
新的：e c d f g j
對(duì)應(yīng)的標(biāo)記是[3, 1, 2, 5, 6, 0]

從上面兩個(gè)例子中可以看出：
第1個(gè)的最優(yōu)解是找到c d，只需移動(dòng)e，創(chuàng)建h
第2個(gè)的最優(yōu)解是找到c d f g，只需移動(dòng)e，創(chuàng)建j

過(guò)程：

從標(biāo)記中找到最長(zhǎng)的遞增子序列
通過(guò)最長(zhǎng)的遞增子序列找到對(duì)應(yīng)的索引值
通過(guò)索引值找到對(duì)應(yīng)的值

注意0表示直接創(chuàng)建，不參與計(jì)算

例子：

[3, 1, 2, 5, 6, 0]的最長(zhǎng)的遞增子序列為[1, 2, 5, 6]，
對(duì)應(yīng)的索引為[1, 2, 3, 4]，
然后我們遍歷e c d f g j，標(biāo)記中為0的，比如j，直接創(chuàng)建；c d f g索引分別等于1 2 3 4，保持不變；e等于0，移動(dòng)

// 需要移動(dòng)位置
// 找出最長(zhǎng)的遞增子序列對(duì)應(yīng)的索引值，如：[5, 3, 4, 0] -> [1, 2]
let increment = getSequence(newIndexToOldIndexMap)
console.log(increment)
let j = increment.length - 1
for (let i = toBePatched - 1; i >= 0; i--) {
  let index = i + s2
  let current = c2[index]
  let anchor = index + 1 < c2.length ? c2[index + 1].el : null
  if (newIndexToOldIndexMap[i] === 0) {
    // 在anchor前面插入新的節(jié)點(diǎn)current
    // todo
  } else {
    if (i !== increment[j]) {
      // 在anchor前面插入對(duì)應(yīng)舊節(jié)點(diǎn).el，current.el元素等于對(duì)應(yīng)的舊節(jié)點(diǎn).el（在其它代碼中賦值了）
      // todo
    } else { // 不變
      j--
    }
  }
}

最長(zhǎng)的遞增子序列

// 最長(zhǎng)的遞增子序列，https://en.wikipedia.org/wiki/Longest_increasing_subsequence
function getSequence(arr) {
  const len = arr.length
  const result = [0] // 以第一項(xiàng)為基準(zhǔn)
  const p = arr.slice() // 標(biāo)記索引，slice為淺復(fù)制一個(gè)新的數(shù)組
  let resultLastIndex
  let start
  let end
  let middle
  for (let i = 0; i < len; i++) {
    let arrI = arr[i]
    if (arrI !== 0) { // vue中等于0，表示需要?jiǎng)?chuàng)建
      resultLastIndex = result[result.length - 1]
      // 插到末尾
      if (arr[resultLastIndex] < arrI) {
        result.push(i)
        p[i] = resultLastIndex // 前面的那個(gè)是誰(shuí)
        continue
      }
      // 遞增序列，二分類查找
      start = 0
      end = result.length - 1
      while(start < end) {
        middle = (start + end) >> 1 // 相當(dāng)于Math.floor((start + end)/2)
        if (arr[result[middle]] < arrI) {
          start = middle + 1
        } else  {
          end = middle
        }
      }
      // 找到最近的哪一項(xiàng)比它大的，替換
      if (arr[result[end]] > arrI) {
        result[end] = i
        if (end > 0) {
          p[i] = result[end - 1] // 前面的那個(gè)是誰(shuí)
        }
      }
    }
  }
  let i = result.length
  let last = result[i - 1]
  while(i-- > 0) {
    result[i] = last
    last = p[last]
  }
  return result
}
console.log(getSequence([5, 3, 4, 0])) // [1, 2]
console.log(getSequence([3, 1, 2, 5, 6, 0])) // [ 1, 2, 3, 4 ]

講解后續(xù)補(bǔ)充...

完整代碼

// 最長(zhǎng)的遞增子序列，https://en.wikipedia.org/wiki/Longest_increasing_subsequence
function getSequence(arr) {
  const len = arr.length
  const result = [0] // 以第一項(xiàng)為基準(zhǔn)
  const p = arr.slice() // 標(biāo)記索引，slice為淺復(fù)制一個(gè)新的數(shù)組
  let resultLastIndex
  let start
  let end
  let middle
  for (let i = 0; i < len; i++) {
    let arrI = arr[i]
    if (arrI !== 0) { // vue中等于0，表示需要?jiǎng)?chuàng)建
      resultLastIndex = result[result.length - 1]
      // 插到末尾
      if (arr[resultLastIndex] < arrI) {
        result.push(i)
        p[i] = resultLastIndex // 前面的那個(gè)是誰(shuí)
        continue
      }
      // 遞增序列，二分類查找
      start = 0
      end = result.length - 1
      while(start < end) {
        middle = (start + end) >> 1 // 相當(dāng)于Math.floor((start + end)/2)
        if (arr[result[middle]] < arrI) {
          start = middle + 1
        } else  {
          end = middle
        }
      }
      // 找到最近的哪一項(xiàng)比它大的，替換
      if (arr[result[end]] > arrI) {
        result[end] = i
        if (end > 0) {
          p[i] = result[end - 1] // 前面的那個(gè)是誰(shuí)
        }
      }
    }
  }
  let i = result.length
  let last = result[i - 1]
  while(i-- > 0) {
    result[i] = last
    last = p[last]
  }
  return result
}
// c1表示舊的子節(jié)點(diǎn)，c2表示新的子節(jié)點(diǎn)
const patchKeyedChildren = (c1, c2) => {
  let i = 0
  let e1 = c1.length - 1
  let e2 = c2.length - 1
  // 從前面比
  while (i <= e1 && i <= e2) {
    const n1 = c1[i]
    const n2 = c2[i]
    // 標(biāo)簽和key是否相同
    // if (n1.type === n2.type && n1.key === n2.key)
    if (n1 === n2) {
      // 繼續(xù)對(duì)比其屬性和子節(jié)點(diǎn)
    } else {
      break
    }
    i++
  }
  // 從后面比
  while (i <= e1 && i <= e2) {
    const n1 = c1[e1]
    const n2 = c2[e2]
    // 標(biāo)簽和key是否相同
    // if (n1.type === n2.type && n1.key === n2.key)
    if (n1 === n2) {
      // 繼續(xù)對(duì)比其屬性和子節(jié)點(diǎn)
    } else {
      break
    }
    e1--
    e2--
  }
  console.log(i, e1, e2)
  // 當(dāng)i大于e1時(shí)
  if (i > e1) {
    if (i <= e2) {
      while (i <= e2) {
        const nextPos = e2 + 1
        const anchor = nextPos < c2.length ? c2[nextPos].el : null
        // 添加子節(jié)點(diǎn)c2[i]在anchor的前面
        // todo
        i++
      }
    }
  }
  // 當(dāng)i大于e2時(shí)
  else if (i > e2) {
    if (i <= e1) {
      while (i <= e1) {
        // 刪除子節(jié)點(diǎn)c1[i]
        // todo
        i++
      }
    }
  }
  // 其它
  else {
    let s1 = i
    let s2 = i
    // 以新的子節(jié)點(diǎn)作為參照物
    const keyToNewIndexMap = new Map()
    for (let i = s2; i <= e2; i++) {
      // 節(jié)點(diǎn)的key做為唯一值
      // keyToNewIndexMap.set(c2[i].key, i)
      keyToNewIndexMap.set(c2[i], i)
    }
    // 新的總個(gè)數(shù)
    const toBePatched = e2 - s2 + 1
    // 記錄新子節(jié)點(diǎn)在舊子節(jié)點(diǎn)中的索引
    const newIndexToOldIndexMap = new Array(toBePatched).fill(0)
    // 循環(huán)老的子節(jié)點(diǎn)
    for (let i = s1; i <= e1; i++) {
      const oldChild = c1[i]
      // let newIndex = keyToNewIndexMap.get(oldChild.key)
      let newIndex = keyToNewIndexMap.get(oldChild)
      // 在新子節(jié)點(diǎn)中不存在
      if (newIndex === undefined) {
        // 刪除oldChild
        // todo
      } else {
        newIndexToOldIndexMap[newIndex - s2] = i + 1 // 永遠(yuǎn)不會(huì)等于0, 這樣0就可以表示需要?jiǎng)?chuàng)建了
        // 繼續(xù)對(duì)比其屬性和子節(jié)點(diǎn)
        // todo
      }
    }
    console.log(newIndexToOldIndexMap)
    // 需要移動(dòng)位置
    // 找出最長(zhǎng)的遞增子序列對(duì)應(yīng)的索引值，如：[5, 3, 4, 0] -> [1, 2]
    let increment = getSequence(newIndexToOldIndexMap)
    console.log(increment)
    let j = increment.length - 1
    for (let i = toBePatched - 1; i >= 0; i--) {
      let index = i + s2
      let current = c2[index]
      let anchor = index + 1 < c2.length ? c2[index + 1].el : null
      if (newIndexToOldIndexMap[i] === 0) {
        // 在anchor前面插入新的節(jié)點(diǎn)current
        // todo
      } else {
        if (i !== increment[j]) {
          // 在anchor前面插入對(duì)應(yīng)舊節(jié)點(diǎn).el，current.el元素等于對(duì)應(yīng)的舊節(jié)點(diǎn).el（在其它代碼中賦值了）
          // todo
        } else { // 不變
          j--
        }
      }
    }
  }
}
// 調(diào)用示例
patchKeyedChildren(['c', 'd', 'e', 'i', 'f', 'g'], ['e', 'c', 'd', 'f', 'g', 'j'])

以上就是vue3 diff 算法示例的詳細(xì)內(nèi)容，更多關(guān)于vue3 diff 算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: