Предисловие: С выпуском бета-версии vue3.0 ожидается, что официальная версия vue3.0 скоро встретит нас. You Yuxi также сказал в прямом эфире, что новые функции vue3.0 сильно поддерживаются машинописным текстом, принципом прокси-ответа, повторной виртуализацией DOM, оптимизированным улучшением производительности алгоритма diff и т. д. Редактор внимательно изучил исходный код vue3.0beta версии алгоритма сравнения здесь и надеется поделиться с вами подробностями и тайнами.
Прежде всего, давайте подумаем о некоторых вопросах, которые легко задать на интервью крупным и средним фабрикам:
1 Когда используется алгоритм сравнения и где его область применения? 2 Как работает алгоритм сравнения и что он делает? 3 Какова роль ключа в списке циклов v-for 4 Действительно ли полезно использовать индекс в качестве ключа? Какое решение лучше всего использовать в качестве ключа?
Если вы столкнетесь с такими вопросами, как вы на них ответите? Я верю, что когда вы закончите читать эту статью, эти вопросы будут решены.
1 Когда используется алгоритм сравнения и область применения алгоритма сравнения?
1.1 Область применения алгоритма сравнения
Введение концепции патча
В процессе обхода дочерних vnode во время процесса обновления vue будут использоваться разные методы исправления для исправления новых и старых vnode.Если соответствующие newVnode и oldVnode найдены, можно повторно использовать узлы реального dom внутри. Позволяет избежать накладных расходов на производительность при многократном создании элементов. В конце концов, браузер создает настоящий DOM и манипулирует настоящим DOM, а цена производительности высока.
В процессе исправления, если в текущем vnode много дочерних узлов, необходимо отдельно пройти новый дочерний vnode и старый дочерний vnode патча.
тип vnode, где существуют дети
Сначала подумайте, у какого типа vnode будут дети.
①элемент тип элемента vnode
Первая ситуация заключается в том, что тип элемента vnode будет иметь дочерние элементы vode, а три тега span на данный момент являются дочерними элементами vnode.
<div>
<span> 苹果🍎 </span>
<span> 香蕉🍌 </span>
<span> 鸭梨🍐 </span>
</div>
В исходном коде vue3.0 patchElement используется для обработки vnodes типа element.
②тип фрагмента флага vnode
В Vue3.0 была введена концепция фрагмента. Вы можете спросить, что такое фрагменты? Если вы создаете компонент Vue, он может иметь только один корневой узел.
<template>
<span> 苹果🍎 </span>
<span> 香蕉🍌 </span>
<span> 鸭梨🍐 </span>
</template>
Это может вызвать предупреждение, потому что экземпляр Vue, представляющий любой компонент Vue, должен быть привязан к одному элементу DOM. Единственный способ создать компонент с несколькими узлами DOM — это создать функциональный компонент без базового экземпляра Vue.
Появляется флаг, который выглядит как обычный элемент DOM, но он виртуальный и вообще не отображается в дереве DOM. Таким образом, мы можем связать функциональность компонента с одним элементом, не создавая дополнительный узел DOM.
<Fragment>
<span> 苹果🍎 </span>
<span> 香蕉🍌 </span>
<span> 鸭梨🍐 </span>
</Fragment>
В исходном коде vue3.0 processFragment используется для обработки vnodes типа Fragment.
1.2 patchChildren
Из вышеизложенного мы знаем, что есть типы дочерних узлов vnode, поэтому, если есть дочерние элементы, нам нужно пропатчить каждый Детский узел траверсирует вниз по очереди. Затем вам нужен метод patchChildren, который, в свою очередь, исправляет подкласс vnode.
patchChildren
В vue3.0 такой исходник есть в методе patchChildren
if (patchFlag > 0) {
if (patchFlag & PatchFlags.KEYED_FRAGMENT) {
/* 对于存在key的情况用于diff算法 */
patchKeyedChildren(
c1 as VNode[],
c2 as VNodeArrayChildren,
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
optimized
)
return
} else if (patchFlag & PatchFlags.UNKEYED_FRAGMENT) {
/* 对于不存在key的情况,直接patch */
patchUnkeyedChildren(
c1 as VNode[],
c2 as VNodeArrayChildren,
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
optimized
)
return
}
}
patchChildren выполняет реальное сравнение или прямое исправление в зависимости от того, существует ли ключ.
Поскольку алгоритм diff существует в методе patchChildren, а метод patchChildren используется во vnode типа Fragment и типа элемента, это также объясняет, какова область действия алгоритма diff.
1.3 Роль алгоритма DIFF?
Из предисловия мы знаем, что vnode, который существует в этой ситуации дочерних элементов, должен пройти дочерние элементы через patchChildren, чтобы выполнить операцию исправления по очереди. затем найдите то же самое, что и новый vnode.Соответствующий vnode так важен.
Мы используем две картинки, чтобы показать вам изменения vnode.
На двух рисунках выше показаны изменения старого и нового деревьев DOM за одно обновление.
Предполагая, что алгоритма сравнения нет, что будет происходить с патчем по порядку?
еслиАлгоритма сравнения нет, но непосредственно patchchildren появится логика, как показано ниже.
первый патчДети
второй патчДети
Третий патч Дети‘
Четвертый патчДети
Если алгоритм diff не используется, а дерево виртуального дома патчится поочередно, то вышеописанное слегкаИзменить порядок домов, в процессе исправления не будет правильной пары старых и новых vnode, поэтому ни один из старых vnode-узлов не может быть повторно использован, поэтому нам нужно пересоздавать новые узлы, тратя впустую накладные расходы на производительность, что явно не то, что нам нужно.
Затем приходит роль алгоритма diff.
Функция diff состоит в том, чтобы найти старый vnode, соответствующий новому vnode, в процессе исправления под-vnode, повторно использовать реальный узел dom и избежать ненужных накладных расходов на производительность.
2 Что именно делает алгоритм сравнения (курсив)?
Прежде чем формально говорить об алгоритме diff, в процессе patchChildren естьpatchKeyedChildren patchUnkeyedChildren
patchKeyedChildren — это официальный процесс открытия различий, так какова роль patchUnkeyedChildren? Давайте посмотрим, что делает patchUnkeyedChildren в случае отсутствия ключа.
c1 = c1 || EMPTY_ARR
c2 = c2 || EMPTY_ARR
const oldLength = c1.length
const newLength = c2.length
const commonLength = Math.min(oldLength, newLength)
let i
for (i = 0; i < commonLength; i++) { /* 依次遍历新老vnode进行patch */
const nextChild = (c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i]))
patch(
c1[i],
nextChild,
container,
null,
parentComponent,
parentSuspense,
isSVG,
optimized
)
}
if (oldLength > newLength) { /* 老vnode 数量大于新的vnode，删除多余的节点 */
unmountChildren(c1, parentComponent, parentSuspense, true, commonLength)
} else { /* /* 老vnode 数量小于于新的vnode，创造新的即诶安 */
mountChildren(
c2,
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
optimized,
commonLength
)
}
Можно сделать вывод, что при отсутствии ключа① Сравните длину новых и старых дочерних элементов, чтобы получить минимальное значение, а затем повторно заплатите общую часть. ② Если количество старых узлов больше количества новых узлов, удалите лишние узлы. ③ Если количество новых узлов больше, чем количество старых узлов, повторно смонтируйте новые добавленные узлы.
А как же дело с ключом? Будет использоваться алгоритм сравнения Что делает алгоритм сравнения?
Что именно делает метод patchKeyedChildren?Давайте сначала посмотрим на некоторые объявленные переменные.
/* c1 老的vnode c2 新的vnode */
let i = 0 /* 记录索引 */
const l2 = c2.length /* 新vnode的数量 */
let e1 = c1.length - 1 /* 老vnode 最后一个节点的索引 */
let e2 = l2 - 1 /* 新节点最后一个节点的索引 */
① Первый шаг — поиск с начала до конца.
(a b) c (a b) d e
/* 从头对比找到有相同的节点 patch ，发现不同，立即跳出*/
while (i <= e1 && i <= e2) {
const n1 = c1[i]
const n2 = (c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i]))
/* 判断key ，type是否相等 */
if (isSameVNodeType(n1, n2)) {
patch(
n1,
n2,
container,
parentAnchor,
parentComponent,
parentSuspense,
isSVG,
optimized
)
} else {
break
}
i++
}
Первым делом нужно с начала найти такой же vnode, а потом патчить, если обнаружится, что это не тот нод, то сразу выпрыгивать из цикла.
Конкретный процесс показан на рисунке
isSameVNodeType
export function isSameVNodeType(n1: VNode, n2: VNode): boolean {
return n1.type === n2.type && n1.key === n2.key
}
Функция isSameVNodeType состоит в том, чтобы определить, равны ли текущий тип vnode и ключ vnode.
②Второй шаг начинается с конца до той же разницы, что и раньше.
a (b c) d e (b c)
/* 如果第一步没有patch完，立即，从后往前开始patch ,如果发现不同立即跳出循环 */
while (i <= e1 && i <= e2) {
const n1 = c1[e1]
const n2 = (c2[e2] = optimized
? cloneIfMounted(c2[e2] as VNode)
: normalizeVNode(c2[e2]))
if (isSameVNodeType(n1, n2)) {
patch(
n1,
n2,
container,
parentAnchor,
parentComponent,
parentSuspense,
isSVG,
optimized
)
} else {
break
}
e1--
e2--
}
После первого шага, если обнаружится, что патча нет, то сразу переходим ко второму шагу, переходя от хвостового к переднему дифференциалу.
Если обнаружится, что это не тот узел, то сразу выпрыгиваем из цикла.
Конкретный процесс показан на рисунке
③④В основном для ситуации добавления и удаления элементов предпосылка заключается в том, что элемент не перемещается.
③ Если старый узел исправлен, а новый узел не исправлен, создайте новый vnode.
(a b) (a b) c i = 2, e1 = 1, e2 = 2 (a b) c (a b) i = 0, e1 = -1, e2 = 0
/* 如果新的节点大于老的节点数 ，对于剩下的节点全部以新的vnode处理（ 这种情况说明已经patch完相同的vnode ） */
if (i > e1) {
if (i <= e2) {
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
)
i++
}
}
}
i > e1
Если количество новых узлов больше, чем количество старых узлов, все оставшиеся узлы обрабатываются новыми внодами (в этом случае те же вноды были пропатчены), то есть должны быть созданы все новые вноды.
Конкретная логика показана на рисунке
④ Если все новые узлы пропатчены, а старые узлы остались, удалите все старые узлы.
i > e2
(a b) c
(a b)
i = 2, e1 = 2, e2 = 1
a (b c)
(b c)
i = 0, e1 = 0, e2 = -1
else if (i > e2) {
while (i <= e1) {
unmount(c1[i], parentComponent, parentSuspense, true)
i++
}
}
В случае, когда старый узел больше нового узла, выгрузите все лишние узлы (в этом случае один и тот же vnode был пропатчен)
Конкретная логика показана на рисунке
⑤ Неопределенные элементы (в данном случае тот же vnode не был исправлен), мы можем продолжить поиск с логикой ①②
разностное ядро
В случае ① и ② узлы, которые не были пройдены, показаны на следующем рисунке.
остальные узлы.
const s1 = i //第一步遍历到的index
const s2 = i
const keyToNewIndexMap: Map<string | number, number> = new Map()
/* 把没有比较过的新的vnode节点,通过map保存 */
for (i = s2; i <= e2; i++) {
if (nextChild.key != null) {
keyToNewIndexMap.set(nextChild.key, i)
}
}
let j
let patched = 0
const toBePatched = e2 - s2 + 1 /* 没有经过 path 新的节点的数量 */
let moved = false /* 证明是否 */
let maxNewIndexSoFar = 0
const newIndexToOldIndexMap = new Array(toBePatched)
for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0
/* 建立一个数组，每个子元素都是0 [ 0, 0, 0, 0, 0, 0, ] */
Пройдите все новые узлы и сохраните индекс и соответствующий ключ в карте keyToNewIndexMap
keyToNewIndexMapСохраните карту ключа -> индекс
D : 2 E : 3 C : 4 I : 5
Затем объявите новый указательj, запишите индекс оставшихся новых узлов.patched, запишите количество новых узлов, исправленных на шаге ⑤toBePatchedЗапишите количество новых узлов, которые не были исправлены до шага ⑤.movedПредставляет, было ли движение, наша демонстрация переместилась.
newIndexToOldIndexMapМассив для хранения индекса нового узла и индекса старого узла. Индекс массива newIndexToOldIndexMap — это индекс нового vnode, а значение — индекс старого vnode.
следующий
for (i = s1; i <= e1; i++) { /* 开始遍历老节点 */
const prevChild = c1[i]
if (patched >= toBePatched) { /* 已经patch数量大于等于， */
/* ① 如果 toBePatched新的节点数量为0 ，那么统一卸载老的节点 */
unmount(prevChild, parentComponent, parentSuspense, true)
continue
}
let newIndex
/* ② 如果,老节点的key存在 ，通过key找到对应的index */
if (prevChild.key != null) {
newIndex = keyToNewIndexMap.get(prevChild.key)
} else { /* ③ 如果,老节点的key不存在 */
for (j = s2; j <= e2; j++) { /* 遍历剩下的所有新节点 */
if (
newIndexToOldIndexMap[j - s2] === 0 && /* newIndexToOldIndexMap[j - s2] === 0 新节点没有被patch */
isSameVNodeType(prevChild, c2[j] as VNode)
) { /* 如果找到与当前老节点对应的新节点那么 ，将新节点的索引，赋值给newIndex */
newIndex = j
break
}
}
}
if (newIndex === undefined) { /* ①没有找到与老节点对应的新节点，删除当前节点，卸载所有的节点 */
unmount(prevChild, parentComponent, parentSuspense, true)
} else {
/* ②把老节点的索引，记录在存放新节点的数组中， */
newIndexToOldIndexMap[newIndex - s2] = i + 1
if (newIndex >= maxNewIndexSoFar) {
maxNewIndexSoFar = newIndex
} else {
/* 证明有节点已经移动了 */
moved = true
}
/* 找到新的节点进行patch节点 */
patch(
prevChild,
c2[newIndex] as VNode,
container,
null,
parentComponent,
parentSuspense,
isSVG,
optimized
)
patched++
}
}
Этот код считается основным алгоритмом сравнения.
Шаг 1: Найдите индекс, соответствующий новому узлу, через ключ старого узла: начните обход старого узла, чтобы определить, есть ли ключ, если есть ключ, найдите индекс нового узла через keyToNewIndexMap. новый узел, если ключа нет, он пройдет по остальным. Новый узел пытается найти соответствующий индекс.
Шаг 2: Если есть индекс, который доказывает, что существует соответствующий старый узел, то непосредственно повторно используйте старый узел для исправления.Если новый узел, соответствующий старому узлу, не найден, удалите текущий старый узел.
Шаг 3: newIndexToOldIndexMap находит взаимосвязь между старым и новым узлами.
На данный момент мы пропатчили его снова, и пропатчили все старые вноды.
как показано на рисунке
Но следующий вопрос.
1 Хотя все старые узлы пропатчены. Фактически вы можете переместить элемент dom для перемещенного узла. 2 Для вновь добавленного узла (узел I на рисунке) не обрабатывается, что делать.
/*移动老节点创建新节点*/
/* 根据最长稳定序列移动相对应的节点 */
const increasingNewIndexSequence = moved
? getSequence(newIndexToOldIndexMap)
: EMPTY_ARR
j = increasingNewIndexSequence.length - 1
for (i = toBePatched - 1; i >= 0; i--) {
const nextIndex = s2 + i
const nextChild = c2[nextIndex] as VNode
const anchor =
nextIndex + 1 < l2 ? (c2[nextIndex + 1] as VNode).el : parentAnchor
if (newIndexToOldIndexMap[i] === 0) { /* 没有老的节点与新的节点对应，则创建一个新的vnode */
patch(
null,
nextChild,
container,
anchor,
parentComponent,
parentSuspense,
isSVG
)
} else if (moved) {
if (j < 0 || i !== increasingNewIndexSequence[j]) { /*如果没有在长*/
/* 需要移动的vnode */
move(nextChild, container, anchor, MoveType.REORDER)
} else {
j--
}
⑥ Самая длинная стабильная последовательность
Предпочтительно получать самую длинную стабильную последовательность через getSequence, для случая index === 0, то естьДобавьте новый узел (I на рисунке)Вам необходимо перемонтировать новый vnode, а затем выполнить унифицированную операцию перемещения для перемещенного узла.
Какая самая длинная стабильная последовательность
Для следующей исходной последовательности 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 Самая длинная возрастающая подпоследовательность 0, 2, 6, 9, 11, 15.
Зачем получать самую длинную стабильную последовательность
Поскольку нам нужна последовательность в качестве базовой эталонной последовательности, другие узлы, которые не находятся в стабильной последовательности, перемещаются.
Суммировать
После вышеизложенного мы примерно знаем процесс алгоритма diff
1 Контраст с самого начала, чтобы найти один и тот же патч узла, если он отличается, немедленно выпрыгнуть.
2 Если первый шаг не завершен, немедленно начните патч с задней части на переднюю и немедленно выйдите из цикла, если он отличается.
3 Если количество новых узлов больше, чем количество старых узлов, все оставшиеся узлы обрабатываются новыми vnodes (в этом случае те же vnodes были пропатчены).
4 В случае, когда старый узел больше нового узла, удалите все лишние узлы (в этом случае тот же vnode был исправлен).
5 неопределенных элементов (в данном случае тот самый vnode, который не был пропатчен) противопоставляется 3 и 4.
1 Сохраните новый узел vnode, который не сравнивался с помощью карты
Запишите количество новых узлов, которые были исправлены.
Количество новых узлов, которые не прошли путь к BePatched
Создайте массив newIndexToOldIndexMap, каждый дочерний элемент — это число в [0, 0, 0, 0, 0, 0,] для записи индекса старого узла, а индекс массива — это индекс нового узла.
Начать обход старых узлов
① Если количество новых узлов в toBePatched равно 0, то старые узлы удаляются равномерно.
② Если ключ старого узла существует, найдите соответствующий индекс по ключу
③ Если ключ старого узла не существует 1 Перейти все оставшиеся новые узлы 2 Если найден новый узел, соответствующий текущему старому узлу, то назначить индекс нового узла в Newindex
④ Если новый узел, соответствующий старому узлу, не найден, удалите текущий старый узел.
⑤ Если найден новый узел, соответствующий старому узлу, запишите индекс старого узла в массиве, хранящем новый узел,
1 Если узел перемещается, запись перемещается
2 Исправление новых и старых узлов Найдите новые узлы для исправления узлов
конец обхода
Если происходит движение
① 根据 newIndexToOldIndexMap 新老节点索引列表找到最长稳定序列
② 对于 newIndexToOldIndexMap -item =0 证明不存在老节点 ，从新形成新的vnode
③ 对于发生移动的节点进行移动处理。
Роль трех ключей, как исправить ключ.
Роль 1key
В приведенном выше алгоритме сравнения метод isSameVNodeType используется для определения того, равны ли ключи для оценки старых и новых узлов. Итак, что мы можем сделать из этого?
В цикле v-for функция ключа заключается в повторном использовании старого узла, соответствующего новому узлу, путем оценки того, равны ли ключи newVnode и OldVnode, чтобы снизить нагрузку на производительность.
2 Как правильно пользоваться ключом
①Неправильное использование 1: Используйте индекс в качестве ключа.
Эффект от использования индекса в качестве ключа на самом деле такой же, как и без использования алгоритма diff.
Если мы используем индекс в качестве ключа, как бы мы ни перемещали и не удаляли узел, мы будем патчить от начала до конца в алгоритме diff (на рисунке:Все узлы не мультиплексированы эффективно)
②Неправильное использование 2: Используйте индекс для объединения других значений в качестве ключей.
Когда индекс используется для объединения других значений в качестве индекса, поскольку каждый узел не может найти соответствующий ключ, все узлы нельзя использовать повторно, и все новые вноды необходимо создавать заново. нужно воссоздать
как показано на рисунке.
③ Правильное использование: используйте уникальный идентификатор значения в качестве ключа (мы можем использовать идентификатор источника данных, взаимодействующего с интерфейсом и сервером, в качестве ключа).
как показано на рисунке. Каждый узел используется повторно. Настоящую роль сыграл алгоритм diff.
Четыре резюме
Выше мы решили все проблемы в начале и, наконец, использовали ментальную карту для реорганизации всего процесса. Алгоритм Diff, вы его изучили?
Сканируйте код в WeChat, подписывайтесь на официальный аккаунт и регулярно делитесь техническими статьями.