предисловие
В этой статье не объясняется реализация vDom, монтирование монтирования и функция рендеринга. Обсуждаются только три алгоритма сравнения. Тип VNode не учитывает компонент, функциональный компонент, фрагмент, телепорт. Учитываются только Элемент и Текст.Весь код этой статьи может относиться к этому проекту.
В следующем алгоритме сравнения будет несколько методов, которые перечислены здесь, и их функции объяснены.
-
mount(vnode, parent, [refNode]): пройти черезvnodeгенерировать реальныеDOMузел.parentреальный узел DOM его родителя,refNodeсерьезноDOMузел, родительский узел которогоparent. еслиrefNodeне ноль,vnodeСгенерированоDOMузел будет вставлен вrefNodeРаньше; еслиrefNodeпусто, тоvnodeСгенерированоDOMУзел вставляется как последний дочерний узел вparentсередина -
patch(prevNode, nextNode, parent): может быть просто понято как предоставление текущегоDOMУзел обновляется, и вызовdiffАлгоритм сравнивает свои собственные дочерние узлы;
1. Реагировать на различия
Идея React инкрементальна. Путем сравнения узлов в новом списке, увеличивается ли позиция в исходном списке, оценивается необходимость перемещения текущего узла.
1. Принцип реализации
Давайте рассмотрим такой пример.
nextListдля нового списка,prevListДля старого списка. Этот пример мы можем видеть новый список не требуется для перемещения. Теперь я используюreactИнкрементальная идея, объясняющая, почему узлы в новом списке не нужно перемещать.
Мы сначала пересекаемnextList, и найти каждый узел вprevListв месте.
function foo(prevList, nextList) {
for (let i = 0; i < nextList.length; i++) {
let nextItem = nextList[i];
for (let j = 0; j < prevList.length; j++) {
let prevItem = prevList[j]
if (nextItem === prevItem) {
}
}
}
}
Найдя позицию, сравните ее с позицией предыдущего узла.Если текущая позиция больше предыдущей позиции, это означает, что текущий узел не нужно перемещать. Таким образом, мы должны определитьlastIndexдля записи положения предыдущего узла.
function foo(prevList, nextList) {
let lastIndex = 0
for (let i = 0; i < nextList.length; i++) {
let nextItem = nextList[i];
for (let j = 0; j < prevList.length; j++) {
let prevItem = prevList[j]
if (nextItem === prevItem) {
if (j < lastIndex) {
// 需要移动节点
} else {
// 不需要移动节点，记录当前位置，与之后的节点进行对比
lastIndex = j
}
}
}
}
}
В приведенном выше примереnextListкаждый узел вprevListнаходится в0 1 2 3. Каждый элемент должен быть больше предыдущего, так что не нужно двигаться, этоreactизdiffПринципы алгоритма.
2. Найдите узел, который нужно переместить
В предыдущем разделе мы нашли соответствующую позицию, сравнив, равны ли значения. Но в vdom каждый узел является vNode, как мы должны судить об этом?
ответkey, мы проходимkeyделать задания, и пусть в том жеchildrenпод массивvnodeизkeyне совпадают, чтобы определить уникальность каждого узла и сравнить старый и новый списки.
function reactDiff(prevChildren, nextChildren, parent) {
let lastIndex = 0
for (let i = 0; i < nextChildren.length; i++) {
let nextChild = nextChildren[i];
for (let j = 0; j < prevChildren.length; j++) {
let prevChild = prevChildren[j]
if (nextChild.key === prevChild.key) {
patch(prevChild, nextChild, parent)
if (j < lastIndex) {
// 需要移动节点
} else {
// 不需要移动节点，记录当前位置，与之后的节点进行对比
lastIndex = j
}
}
}
}
}
3. Мобильный узел
Во-первых, давайте проясним, что узел является мобильным узлом по смыслуDOMузел.vnode.elуказывает на действительное, соответствующее этому узлуDOMузел.patchметод обновит обновленныйDOMузел, назначенныйновыйvnodeизelАтрибуты.
Для удобства рисования используем
keyзначение для представленияvnodeузел. Для удобства записи положимkeyзначениеaизvnodeсокращенноvnode-a,vnode-aСоответствующий реальный узел DOMDOM-A
Давайте заменим приведенный выше пример наreactDiffв исполнении. мы пересекаемновый список, и найтиvnodeсуществуетстарый списокв месте. при переходе наvnode-d, ранее пройденный встарый списокнаходится в0 < 2 < 3, проиллюстрироватьA C DВсе три узла не нужно перемещать. В настоящее времяlastIndex = 3, и введите следующий цикл, чтобы найтиvnode-bсуществуетстарый списокизindexдля1,1 < 3, проиллюстрироватьDOM-Bдвигаться.
Наблюдение мы можем найти, просто надоDOM-Bперейти кDOM-DПосле этого вы можете. то естьНайдите VNode, который нужно переместить, мы называем VNode α и перемещаем реальный DOM-узел, соответствующий α, где α新列表Предыдущий VNode соответствует задней части реального DOM.
В приведенном выше примереvnode-bСоответствующий реальный узел DOMDOM-B, перейти кvnode-bпредыдущий в новом спискеVNode——vnode-dСоответствующий реальный узел DOMDOM-Dпозади.
function reactDiff(prevChildren, nextChildren, parent) {
let lastIndex = 0
for (let i = 0; i < nextChildren.length; i++) {
let nextChild = nextChildren[i];
for (let j = 0; j < prevChildren.length; j++) {
let prevChild = prevChildren[j]
if (nextChild.key === prevChild.key) {
patch(prevChild, nextChild, parent)
if (j < lastIndex) {
// 移动到前一个节点的后面
let refNode = nextChildren[i - 1].el.nextSibling;
parent.insertBefore(nextChild.el, refNode)
} else {
// 不需要移动节点，记录当前位置，与之后的节点进行对比
lastIndex = j
}
}
}
}
}
Почему он так двигался? Сначала наш список从头到尾пройдено. Это означает, что для текущегоVNodeУзел, все узлы перед узлом сортируются, если узел нужно переместить, вам нужно только перейти к предыдущему узлу DOMvnodeПосле узла можно, потому что вновый списоксерединаvnodeПорядок такой.
4. Добавьте узлы
Предыдущий раздел мы говорим о том, как переместить узел, но проигнорировал другой случай, то естьновый списоксовершенно новыйVNodeузел, встарый списокне найдено в . В этом случае нам необходимоVNodeГенерация узловDOMузел и вставьтеDOMв дереве.
Пока что мы столкнулись с двумя проблемами: 1. Как обнаружить совершенно новые узлы, 2. СгенерированныеDOMкуда вставляется узел
Давайте сначала решим первую задачу.Найти узлы относительно просто.Определимfindпеременное значениеfalse. если встарый списокнашел этоkeyидентичныйvnode, будуfindЗначение изменяется наtrue. Судя по завершению обходаfindзначение, еслиfalse, указывая, что текущий узел является новым узлом.
function reactDiff(prevChildren, nextChildren, parent) {
let lastIndex = 0
for (let i = 0; i < nextChildren.length; i++) {
let nextChild = nextChildren[i],
find = false;
for (let j = 0; j < prevChildren.length; j++) {
let prevChild = prevChildren[j]
if (nextChild.key === prevChild.key) {
find = true
patch(prevChild, nextChild, parent)
if (j < lastIndex) {
// 移动到前一个节点的后面
let refNode = nextChildren[i - 1].el.nextSibling;
parent.insertBefore(nextChild.el, refNode)
} else {
// 不需要移动节点，记录当前位置，与之后的节点进行对比
lastIndex = j
}
break
}
}
if (!find) {
// 插入新节点
}
}
}
После нахождения нового узла следующий шаг — куда его вставить.Логика здесь фактически такая же, как и логика перемещения узла. Мы можем наблюдать приведенную выше картину и обнаружить, что новыеvnode-cявляется следующееvnode-bпоследний, иvnode-bУзел DOM --DOM-Bуже отсортировано, поэтому нам просто нужно поставитьvnode-cПолученный узел DOM вставляется вDOM-BПосле этого вы можете.
Но здесь следует отметить особый случай, то есть новый узел расположен вновый списокПервый, то нам нужно его найти.старый списокДля первого узла вставьте новый узел перед исходным первым узлом.
function reactDiff(prevChildren, nextChildren, parent) {
let lastIndex = 0
for (let i = 0; i < nextChildren.length; i++) {
let nextChild = nextChildren[i],
find = false;
for (let j = 0; j < prevChildren.length; j++) {
let prevChild = prevChildren[j]
if (nextChild.key === prevChild.key) {
find = true
patch(prevChild, nextChild, parent)
if (j < lastIndex) {
// 移动到前一个节点的后面
let refNode = nextChildren[i - 1].el.nextSibling;
parent.insertBefore(nextChild.el, refNode)
} else {
// 不需要移动节点，记录当前位置，与之后的节点进行对比
lastIndex = j
}
break
}
}
if (!find) {
// 插入新节点
let refNode = i <= 0
? prevChildren[0].el
: nextChildren[i - 1].el.nextSibling
mount(nextChild, parent, refNode);
}
}
}
5. Удалите узел
Есть увеличение и уменьшение, когда старого узла нетновый списокСо временем мы удалим соответствующий узел DOM.
function reactDiff(prevChildren, nextChildren, parent) {
let lastIndex = 0
for (let i = 0; i < nextChildren.length; i++) {
let nextChild = nextChildren[i],
find = false;
for (let j = 0; j < prevChildren.length; j++) {
let prevChild = prevChildren[j]
if (nextChild.key === prevChild.key) {
find = true
patch(prevChild, nextChild, parent)
if (j < lastIndex) {
// 移动到前一个节点的后面
let refNode = nextChildren[i - 1].el.nextSibling;
parent.insertBefore(nextChild.el, refNode)
} else {
// 不需要移动节点，记录当前位置，与之后的节点进行对比
lastIndex = j
}
break
}
}
if (!find) {
// 插入新节点
let refNode = i <= 0
? prevChildren[0].el
: nextChildren[i - 1].el.nextSibling
mount(nextChild, parent, refNode);
}
}
for (let i = 0; i < prevChildren.length; i++) {
let prevChild = prevChildren[i],
key = prevChild.key,
has = nextChildren.find(item => item.key === key);
if (!has) parent.removeChild(prevChild.el)
}
}
6. Оптимизация и недостатки
Вышеизложенное является идеей алгоритма сравнения React.
токreactDiffВременная сложностьO(m*n), мы можем поменять пространство на время,keyа такжеindexЧтобы сохранить отношенияMap, что снижает временную сложность доO(n), конкретный код может бытьПосмотреть этот товар.
Давайте рассмотрим такой пример далее
согласно сreactDiffИдеи, нам нужно сначалаDOM-Aперейти кDOM-Cпосле этого, а затемDOM-Bперейти кDOM-AПосле этого закончитьDiff. Но мы можем обнаружить путем наблюдения, что до тех пор, покаDOM-Cперейти кDOM-Aможно сделать раньшеDiff.
Здесь есть место для оптимизации.vue2.xсерединаdiffалгоритм--双端比较, алгоритм решает вышеуказанную задачу
2. Vue2.X Diff — двустороннее сравнение
так называемый双端比较то естьновый списока такжестарый списокГолова и хвост двух списков сравниваются друг с другом, при этом указатели будут постепенно двигаться внутрь, пока не будут пройдены все узлы определенного списка, и сравнение остановится.
1. Принцип реализации
Сначала мы используем четыре указателя, чтобы указать на начало и конец двух списков.
function vue2Diff(prevChildren, nextChildren, parent) {
let oldStartIndex = 0,
oldEndIndex = prevChildren.length - 1
newStartIndex = 0,
newEndIndex = nextChildren.length - 1;
let oldStartNode = prevChildren[oldStartIndex],
oldEndNode = prevChildren[oldEndIndex],
newStartNode = nextChildren[nextStartIndex],
newEndNode = nextChildren[nextEndIndex];
}
Находим четыре узла по четырем указателям, а потом сравниваем, так как же сравнивать? Мы делаем следующие четыре шага, чтобы сравнить
- использоватьстарый списокпервый узел
oldStartNodeа такженовый списокпервый узелnewStartNodeВ сравнении - использоватьстарый списокПоследний узел
oldEndNodeа такженовый списокпоследний узелnewEndNodeВ сравнении - использоватьстарый списокпервый узел
oldStartNodeа такженовый списокпоследний узелnewEndNodeВ сравнении - использоватьстарый списокпоследний узел
oldEndNodeа такженовый списокпервый узелnewStartNodeВ сравнении
Используйте вышеуказанные четыре шага для сравнения, чтобы найтиkeyТот же повторно используемый узел, найденный на определенном шаге, останавливает последующий поиск. Конкретная последовательность сравнения выглядит следующим образом
Структура кода последовательности сравнения выглядит следующим образом:
function vue2Diff(prevChildren, nextChildren, parent) {
let oldStartIndex = 0,
oldEndIndex = prevChildren.length - 1
newStartIndex = 0,
newEndIndex = nextChildren.length - 1;
let oldStartNode = prevChildren[oldStartIndex],
oldEndNode = prevChildren[oldEndIndex],
newStartNode = nextChildren[newStartIndex],
newEndNode = nextChildren[newEndIndex];
if (oldStartNode.key === newStartNode.key) {
} else if (oldEndNode.key === newEndNode.key) {
} else if (oldStartNode.key === newEndNode.key) {
} else if (oldEndNode.key === newStartNode.key) {
}
}
Когда повторно используемый узел найден во время сравнения, мы все равно сначалаpatchК элементу исправления, то указатель前/后移Однобитовый указатель. В зависимости от узла сравнения мы перемещаемуказательа такженаправлениеТакже отличаются, конкретные правила заключаются в следующем:
- когдастарый списокпервый узел
oldStartNodeа такженовый списокпервый узелnewStartNodeПри сравненииkeyтакой же. Такстарый списокуказатель головыoldStartIndexа такженовый списокуказатель головыnewStartIndexв то же время, чтобыназадСдвинься на один бит. - когдастарый списокпоследний узел
oldEndNodeа такженовый списокпоследний узелnewEndNodeПри сравненииkeyтакой же. Такстарый списокхвостовой указательoldEndIndexа такженовый списокхвостовой указательnewEndIndexв то же время, чтобывпередСдвинься на один бит. - когдастарый списокпервый узел
oldStartNodeа такженовый списокпоследний узелnewEndNodeПри сравненииkeyтакой же. Такстарый списокуказатель головыoldStartIndexКназадпереместить один бит;новый списокхвостовой указательnewEndIndexКвпередСдвинься на один бит. - когдастарый списокпоследний узел
oldEndNodeа такженовый списокпервый узелnewStartNodeПри сравненииkeyтакой же. Такстарый списокхвостовой указательoldEndIndexКвпередпереместить один бит;новый списокуказатель головыnewStartIndexКназадСдвинься на один бит.
function vue2Diff(prevChildren, nextChildren, parent) {
let oldStartIndex = 0,
oldEndIndex = prevChildren.length - 1,
newStartIndex = 0,
newEndIndex = nextChildren.length - 1;
let oldStartNode = prevChildren[oldStartIndex],
oldEndNode = prevChildren[oldEndIndex],
newStartNode = nextChildren[newStartIndex],
newEndNode = nextChildren[newEndIndex];
if (oldStartNode.key === newStartNode.key) {
patch(oldvStartNode, newStartNode, parent)
oldStartIndex++
newStartIndex++
oldStartNode = prevChildren[oldStartIndex]
newStartNode = nextChildren[newStartIndex]
} else if (oldEndNode.key === newEndNode.key) {
patch(oldEndNode, newEndNode, parent)
oldEndIndex--
newEndIndex--
oldEndNode = prevChildren[oldEndIndex]
newEndNode = nextChildren[newEndIndex]
} else if (oldStartNode.key === newEndNode.key) {
patch(oldStartNode, newEndNode, parent)
oldStartIndex++
newEndIndex--
oldStartNode = prevChildren[oldStartIndex]
newEndNode = nextChildren[newEndIndex]
} else if (oldEndNode.key === newStartNode.key) {
patch(oldEndNode, newStartNode, parent)
oldEndIndex--
nextStartIndex++
oldEndNode = prevChildren[oldEndIndex]
newStartNode = nextChildren[newStartIndex]
}
}
В начале подраздела упоминалось, что мы хотим, чтобы указатель двигался внутрь, поэтому нам нужно зациклиться. Условием остановки цикла является прохождение всех узлов в одном из списков, код выглядит следующим образом
function vue2Diff(prevChildren, nextChildren, parent) {
let oldStartIndex = 0,
oldEndIndex = prevChildren.length - 1,
newStartIndex = 0,
newEndIndex = nextChildren.length - 1;
let oldStartNode = prevChildren[oldStartIndex],
oldEndNode = prevChildren[oldEndIndex],
newStartNode = nextChildren[newStartIndex],
newEndNode = nextChildren[newEndIndex];
while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
if (oldStartNode.key === newStartNode.key) {
patch(oldStartNode, newStartNode, parent)
oldStartIndex++
newStartIndex++
oldStartNode = prevChildren[oldStartIndex]
newStartNode = nextChildren[newStartIndex]
} else if (oldEndNode.key === newEndNode.key) {
patch(oldEndNode, newEndNode, parent)
oldEndIndex--
newndIndex--
oldEndNode = prevChildren[oldEndIndex]
newEndNode = nextChildren[newEndIndex]
} else if (oldStartNode.key === newEndNode.key) {
patch(oldvStartNode, newEndNode, parent)
oldStartIndex++
newEndIndex--
oldStartNode = prevChildren[oldStartIndex]
newEndNode = nextChildren[newEndIndex]
} else if (oldEndNode.key === newStartNode.key) {
patch(oldEndNode, newStartNode, parent)
oldEndIndex--
newStartIndex++
oldEndNode = prevChildren[oldEndIndex]
newStartNode = nextChildren[newStartIndex]
}
}
}
На данный момент мы завершили общий цикл. Далее нам необходимо рассмотреть следующие два вопроса:
- при каких обстоятельствах
DOMУзел должен двигаться -
DOMкак двигаются узлы
Решим первую задачу:Когда вам нужно переехать, мы по-прежнему берем приведенную выше картинку в качестве примера.
Когда мы находимся в первом цикле, в第四步Обнаружитьхвостовой узел старого спискаoldEndNodeа такжеголовной узел нового спискаnewStartNodeизkeyто же, многоразовыйDOMузел. Наблюдая, мы можем найти, чтоУзел, который изначально был в конце старого списка, является началом нового списка, его никто не опережает, потому что он первый, поэтому нам нужно просто переместить текущий узел на первый в старом списке. list.Перед узлом сделайте его первым узлом.
function vue2Diff(prevChildren, nextChildren, parent) {
// ...
while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
if (oldStartNode.key === newStartNode.key) {
// ...
} else if (oldEndNode.key === newEndNode.key) {
// ...
} else if (oldStartNode.key === newEndNode.key) {
// ...
} else if (oldEndNode.key === newStartNode.key) {
patch(oldEndNode, newStartNode, parent)
// 移动到旧列表头节点之前
parent.insertBefore(oldEndNode.el, oldStartNode.el)
oldEndIndex--
newStartIndex++
oldEndNode = prevChildren[oldEndIndex]
newStartNode = nextChildren[newStartIndex]
}
}
}
Затем мы входим во вторую петлю, где мы находимся в第二步Обнаружить,хвостовой узел старого спискаoldEndNodeа такжехвостовой узел нового спискаnewEndNodeдля мультиплексирования узлов.Первоначально это был хвостовой узел в старом списке, а также хвостовой узел в новом списке, что указывает на то, что узел не нужно перемещать., так что нам ничего не нужно делать.
Точно так же, еслиголовной узел старого спискаoldStartNodeа такжеголовной узел нового спискаnewStartNodeДля повторного использования узлов нам тоже ничего делать не нужно.
Войдя в третью петлю, мы находимся в第三部Обнаружить,головной узел старого спискаoldStartNodeа такжехвостовой узел нового спискаnewEndNodeдля мультиплексирования узлов. Если вы сообразительны в этот момент, вы можете увидеть это с первого взгляда, нам просто нужно поставитьDOM-Aперейти кDOM-BЭто для спины.
Как обычно, объясним,Первоначально старый список был головным узлом, а затем новый список стал хвостовым узлом. Затем просто переместите текущий узел в конец исходного хвостового узла в старом списке, и все..
function vue2Diff(prevChildren, nextChildren, parent) {
// ...
while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
if (oldStartNode.key === newStartNode.key) {
// ...
} else if (oldEndNode.key === newEndNode.key) {
// ...
} else if (oldStartNode.key === newEndNode.key) {
patch(oldStartNode, newEndNode, parent)
parent.insertBefore(oldStartNode.el, oldEndNode.el.nextSibling)
oldStartIndex++
newEndIndex--
oldStartNode = prevChildren[oldStartIndex]
newEndNode = nextChildren[newEndIndex]
} else if (oldEndNode.key === newStartNode.key) {
//...
}
}
}
Хорошо, введите последний цикл. существует第一步старый списокголовной узелoldStartNodeа такженовый списокголовной узелnewStartNodeТо же место, так что делать нечего. Затем, чтобы закончить цикл, этоVue2 双端比较принцип.
2. Неидеальная ситуация
В предыдущем разделе мы говорили о双端比较Принцип , но есть частный случай, когда все четыре сравненияне нашелПри повторном использовании узлов мы можем взять тольконовый списокпервый узел, к которому нужно перейтистарый списокНаходясь в поискеkeyтот же узел.
.
function vue2Diff(prevChildren, nextChildren, parent) {
//...
while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
if (oldStartNode.key === newStartNode.key) {
//...
} else if (oldEndNode.key === newEndNode.key) {
//...
} else if (oldStartNode.key === newEndNode.key) {
//...
} else if (oldEndNode.key === newStartNode.key) {
//...
} else {
// 在旧列表中找到 和新列表头节点key 相同的节点
let newKey = newStartNode.key,
oldIndex = prevChildren.findIndex(child => child.key === newKey);
}
}
}
При поиске узлов на самом деле есть две ситуации: однастарый списокВ другом случае не обнаружено. Давайте возьмем приведенную выше картинку в качестве примера и поговорим о том, что мы нашли.
Когда мы находим соответствующий в старом спискеVNodeНам нужно только найти узелDOMэлемент, просто перейдите к началу. Логика здесь на самом деле第四步Логика та же, только第四步— хвостовой узел перемещения, здесь — узел, найденный перемещением.DOMПосле переезда мыстарый списокУзел в меняется наundefined,Этожизненно важныйшаг, потому что мы уже выполнили перемещение узла, поэтому нам не нужно делать еще одно сравнение. Наконец, мы помещаем указатель головыnewStartIndexПереместиться назад на один бит.
function vue2Diff(prevChildren, nextChildren, parent) {
//...
while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
if (oldStartNode.key === newStartNode.key) {
//...
} else if (oldEndNode.key === newEndNode.key) {
//...
} else if (oldStartNode.key === newEndNode.key) {
//...
} else if (oldEndNode.key === newStartNode.key) {
//...
} else {
// 在旧列表中找到 和新列表头节点key 相同的节点
let newtKey = newStartNode.key,
oldIndex = prevChildren.findIndex(child => child.key === newKey);
if (oldIndex > -1) {
let oldNode = prevChildren[oldIndex];
patch(oldNode, newStartNode, parent)
parent.insertBefore(oldNode.el, oldStartNode.el)
prevChildren[oldIndex] = undefined
}
newStartNode = nextChildren[++newStartIndex]
}
}
}
если встарый списокНе нашли в нем узел мультиплексирования? Это очень просто, просто создайте новый узел и поместите его впереди, а затем переместите указатель головы назад.newStartIndex.
function vue2Diff(prevChildren, nextChildren, parent) {
//...
while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
if (oldStartNode.key === newStartNode.key) {
//...
} else if (oldEndNode.key === newEndNode.key) {
//...
} else if (oldStartNode.key === newEndNode.key) {
//...
} else if (oldEndNode.key === newStartNode.key) {
//...
} else {
// 在旧列表中找到 和新列表头节点key 相同的节点
let newtKey = newStartNode.key,
oldIndex = prevChildren.findIndex(child => child.key === newKey);
if (oldIndex > -1) {
let oldNode = prevChildren[oldIndex];
patch(oldNode, newStartNode, parent)
parent.insertBefore(oldNode.el, oldStartNode.el)
prevChildren[oldIndex] = undefined
} else {
mount(newStartNode, parent, oldStartNode.el)
}
newStartNode = nextChildren[++newStartIndex]
}
}
}
наконец, когдастарый списокпройти кundefindпропускает текущий узел.
function vue2Diff(prevChildren, nextChildren, parent) {
//...
while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
if (oldStartNode === undefind) {
oldStartNode = prevChildren[++oldStartIndex]
} else if (oldEndNode === undefind) {
oldEndNode = prevChildren[--oldEndIndex]
} else if (oldStartNode.key === newStartNode.key) {
//...
} else if (oldEndNode.key === newEndNode.key) {
//...
} else if (oldStartNode.key === newEndNode.key) {
//...
} else if (oldEndNode.key === newStartNode.key) {
//...
} else {
// ...
}
}
}
3. Добавьте узлы
Сначала рассмотрим пример
Этот пример очень прост.Хвостовой узел один и тот же для нескольких циклов, а указатель хвоста продолжает двигаться вперед, пока цикл не закончится, как показано на следующем рисунке.
В настоящее времяoldEndIndexи меньше чемoldStartIndex,ноновый списокОстались узлы в , нам просто нужно вставить оставшиеся узлы вoldStartNodeизDOMРаньше было хорошо. зачем вставлятьoldStartNodeПредыдущий?原因是剩余的节点在новый списокнаходится вoldStartNodeраньше, если оставшийся узел находится вoldStartNodeПозже,oldStartNodeЕго будут сравнивать в первую очередь.Об этом нужно подумать.По сути, это все равно что第四步та же идея.
function vue2Diff(prevChildren, nextChildren, parent) {
//...
while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
// ...
}
if (oldEndIndex < oldStartIndex) {
for (let i = newStartIndex; i <= newEndIndex; i++) {
mount(nextChildren[i], parent, prevStartNode.el)
}
}
}
4. Удалите узел
В отличие от ситуации в предыдущем пункте, когдановый списокизnewEndIndexменьше, чемnewStartIndex, мы будемстарый списокОстальные узлы можно удалить. Здесь нужно обратить внимание,старый списокизundefind. Как мы упоминали во втором подразделе, когда головной и хвостовой узлы не совпадают, мы перейдем кстарый списокнайти вновый списокПервый узел , после перемещения узла DOM, будетстарый списокВместо этого узлаundefind. Поэтому нам нужно обратить внимание на это, когда мы удаляем его в конце.undefind, если вы столкнетесь с этим, вы можете пропустить текущий цикл.
function vue2Diff(prevChildren, nextChildren, parent) {
//...
while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
// ...
}
if (oldEndIndex < oldStartIndex) {
for (let i = newStartIndex; i <= newEndIndex; i++) {
mount(nextChildren[i], parent, prevStartNode.el)
}
} else if (newEndIndex < newStartIndex) {
for (let i = oldStartIndex; i <= oldEndIndex; i++) {
if (prevChildren[i]) {
partent.removeChild(prevChildren[i].el)
}
}
}
}
5. Резюме
слишком далеко双端比较Все готово, далее весь код.
function vue2diff(prevChildren, nextChildren, parent) {
let oldStartIndex = 0,
newStartIndex = 0,
oldStartIndex = prevChildren.length - 1,
newStartIndex = nextChildren.length - 1,
oldStartNode = prevChildren[oldStartIndex],
oldEndNode = prevChildren[oldStartIndex],
newStartNode = nextChildren[newStartIndex],
newEndNode = nextChildren[newStartIndex];
while (oldStartIndex <= oldStartIndex && newStartIndex <= newStartIndex) {
if (oldStartNode === undefined) {
oldStartNode = prevChildren[++oldStartIndex]
} else if (oldEndNode === undefined) {
oldEndNode = prevChildren[--oldStartIndex]
} else if (oldStartNode.key === newStartNode.key) {
patch(oldStartNode, newStartNode, parent)
oldStartIndex++
newStartIndex++
oldStartNode = prevChildren[oldStartIndex]
newStartNode = nextChildren[newStartIndex]
} else if (oldEndNode.key === newEndNode.key) {
patch(oldEndNode, newEndNode, parent)
oldStartIndex--
newStartIndex--
oldEndNode = prevChildren[oldStartIndex]
newEndNode = nextChildren[newStartIndex]
} else if (oldStartNode.key === newEndNode.key) {
patch(oldStartNode, newEndNode, parent)
parent.insertBefore(oldStartNode.el, oldEndNode.el.nextSibling)
oldStartIndex++
newStartIndex--
oldStartNode = prevChildren[oldStartIndex]
newEndNode = nextChildren[newStartIndex]
} else if (oldEndNode.key === newStartNode.key) {
patch(oldEndNode, newStartNode, parent)
parent.insertBefore(oldEndNode.el, oldStartNode.el)
oldStartIndex--
newStartIndex++
oldEndNode = prevChildren[oldStartIndex]
newStartNode = nextChildren[newStartIndex]
} else {
let newKey = newStartNode.key,
oldIndex = prevChildren.findIndex(child => child && (child.key === newKey));
if (oldIndex === -1) {
mount(newStartNode, parent, oldStartNode.el)
} else {
let prevNode = prevChildren[oldIndex]
patch(prevNode, newStartNode, parent)
parent.insertBefore(prevNode.el, oldStartNode.el)
prevChildren[oldIndex] = undefined
}
newStartIndex++
newStartNode = nextChildren[newStartIndex]
}
}
if (newStartIndex > newStartIndex) {
while (oldStartIndex <= oldStartIndex) {
if (!prevChildren[oldStartIndex]) {
oldStartIndex++
continue
}
parent.removeChild(prevChildren[oldStartIndex++].el)
}
} else if (oldStartIndex > oldStartIndex) {
while (newStartIndex <= newStartIndex) {
mount(nextChildren[newStartIndex++], parent, oldStartNode.el)
}
}
}
3. Vue3 Diff — самая длинная возрастающая подпоследовательность
vue3изdiffНаучитьсяinferno, в алгоритме есть две идеи. Первый — это предобработка одних и тех же пре- и постэлементов, второй — самая длинная возрастающая подпоследовательность, аналогичная идееReactизdiffПохожий, но не такой же. Давайте представим их один за другим.
1. Пре- и постобработка
Давайте посмотрим на эти два абзаца
Hello World
Hey World
На самом деле, просто взглянув на него, мы можем обнаружить, что некоторые из этих двух текстов совпадают.Эти тексты не нужно изменять или перемещать, действительно нужно изменить несколько букв в середине, поэтомуdiffстановится следующей частью
text1: 'llo'
text2: 'y'
Затем замените его наvnode, в качестве примера возьмем следующий рисунок.
Узлы, обведенные на рисунке зеленым цветом, перемещать не нужно, их нужно только залататьpatchВот и все. Мы пишем эту логику в виде кода.
function vue3Diff(prevChildren, nextChildren, parent) {
let j = 0,
prevEnd = prevChildren.length - 1,
nextEnd = nextChildren.length - 1,
prevNode = prevChildren[j],
nextNode = nextChildren[j];
while (prevNode.key === nextNode.key) {
patch(prevNode, nextNode, parent)
j++
prevNode = prevChildren[j]
nextNode = nextChildren[j]
}
prevNode = prevChildren[prevEnd]
nextNode = prevChildren[nextEnd]
while (prevNode.key === nextNode.key) {
patch(prevNode, nextNode, parent)
prevEnd--
nextEnd--
prevNode = prevChildren[prevEnd]
nextNode = prevChildren[nextEnd]
}
}
На данный момент нам нужно рассмотреть граничный случай, здесь есть два случая. одинj > prevEnd; другой естьj > nextEnd.
Давайте возьмем эту картинку в качестве примера,j > prevEndа такжеj <= nextEnd, нам просто нужно положитьновый списоксерединаjприбытьnextEndостальные узлы междувставлятьПросто войдите. И наоборот, еслиj > nextEnd, мы положилистарый списоксерединаjприбытьprevEndузел междуудалятьВот и все.
function vue3Diff(prevChildren, nextChildren, parent) {
// ...
if (j > prevEnd && j <= nextEnd) {
let nextpos = nextEnd + 1,
refNode = nextpos >= nextChildren.length
? null
: nextChildren[nextpos].el;
while(j <= nextEnd) mount(nextChildren[j++], parent, refNode)
} else if (j > nextEnd && j <= prevEnd) {
while(j <= prevEnd) parent.removeChild(prevChildren[j++].el)
}
}
Мы продолжаем думать, в нашейwhileПри зацикливании указатель постепенно перемещается внутрь с обоих концов, поэтому следует судить о граничных условиях в цикле, используемlabelГрамматика, когда мы запускаем крайний случай, выходим из всего цикла и переходим непосредственно к решению. код показывает, как показано ниже:
function vue3Diff(prevChildren, nextChildren, parent) {
let j = 0,
prevEnd = prevChildren.length - 1,
nextEnd = nextChildren.length - 1,
prevNode = prevChildren[j],
nextNode = nextChildren[j];
// label语法
outer: {
while (prevNode.key === nextNode.key) {
patch(prevNode, nextNode, parent)
j++
// 循环中如果触发边界情况，直接break，执行outer之后的判断
if (j > prevEnd || j > nextEnd) break outer
prevNode = prevChildren[j]
nextNode = nextChildren[j]
}
prevNode = prevChildren[prevEnd]
nextNode = prevChildren[nextEnd]
while (prevNode.key === nextNode.key) {
patch(prevNode, nextNode, parent)
prevEnd--
nextEnd--
// 循环中如果触发边界情况，直接break，执行outer之后的判断
if (j > prevEnd || j > nextEnd) break outer
prevNode = prevChildren[prevEnd]
nextNode = prevChildren[nextEnd]
}
}
// 边界情况的判断
if (j > prevEnd && j <= nextEnd) {
let nextpos = nextEnd + 1,
refNode = nextpos >= nextChildren.length
? null
: nextChildren[nextpos].el;
while(j <= nextEnd) mount(nextChildren[j++], parent, refNode)
} else if (j > nextEnd && j <= prevEnd) {
while(j <= prevEnd) parent.removeChild(prevChildren[j++].el)
}
}
2. Решите, нужно ли вам переехать
На самом деле, после просмотра нескольких алгоритмов рутина уже очевидна, то есть найти движущийся узел, а затем переместить его в правильное положение. Добавьте новый узел, который следует добавить, удалите старый узел, который следует удалить, и весь алгоритм закончен. Этот алгоритм не является исключением, давайте посмотрим, как он это сделает дальше.
когда前/后置После того, как предобработка окончена, мы входим в реальныйdiffсвязь. Во-первых, мы первыеновый списокколичество оставшихся узлов, создайтеsourceмассив и заполнить массив-1.
Сначала напишем эту логику.
function vue3Diff(prevChildren, nextChildren, parent) {
//...
outer: {
// ...
}
// 边界情况的判断
if (j > prevEnd && j <= nextEnd) {
// ...
} else if (j > nextEnd && j <= prevEnd) {
// ...
} else {
let prevStart = j,
nextStart = j,
nextLeft = nextEnd - nextStart + 1, // 新列表中剩余的节点长度
source = new Array(nextLeft).fill(-1); // 创建数组，填满-1
}
}
тогда этоsourceМассив, для чего он нужен? Он здесь, чтобы сделать соответствие между старым и новым узлами, мы будемновый узелсуществуетстарый списокхранится в этом массиве, мыsourceрассчитать его最长递增子序列Используется для перемещения узлов DOM. Для этого мы сначала создадим объект для хранения текущегоновый списоксередина节点а такжеindexотношения, перейти кстарый списокНайдите место.
Обратите внимание при поиске узлов,Если старого узла нет в новом списке, просто удалите его. В дополнение к этому нам также нужно количество для представления записей, которые у нас есть.patchпройденных узлов, если число уже соответствуетновый списокОставшееся количество узлов такое же, тогда оставшееся旧节点Мы можем просто удалить его
function vue3Diff(prevChildren, nextChildren, parent) {
//...
outer: {
// ...
}
// 边界情况的判断
if (j > prevEnd && j <= nextEnd) {
// ...
} else if (j > nextEnd && j <= prevEnd) {
// ...
} else {
let prevStart = j,
nextStart = j,
nextLeft = nextEnd - nextStart + 1, // 新列表中剩余的节点长度
source = new Array(nextLeft).fill(-1), // 创建数组，填满-1
nextIndexMap = {}, // 新列表节点与index的映射
patched = 0; // 已更新过的节点的数量
// 保存映射关系
for (let i = nextStart; i <= nextEnd; i++) {
let key = nextChildren[i].key
nextIndexMap[key] = i
}
// 去旧列表找位置
for (let i = prevStart; i <= prevEnd; i++) {
let prevNode = prevChildren[i],
prevKey = prevNode.key,
nextIndex = nextIndexMap[prevKey];
// 新列表中没有该节点 或者 已经更新了全部的新节点，直接删除旧节点
if (nextIndex === undefind || patched >= nextLeft) {
parent.removeChild(prevNode.el)
continue
}
// 找到对应的节点
let nextNode = nextChildren[nextIndex];
patch(prevNode, nextNode, parent);
// 给source赋值
source[nextIndex - nextStart] = i
patched++
}
}
}
Найдя локацию, наблюдаем за этим переназначеннымsource, мы видим, что если это совершенно новый узел, егоsourceСоответствующее значение в массиве является начальным-1, на этом шаге мы можем отличить новый узел от повторно используемого.
Во-вторых, мы должны решить, нужно ли нам двигаться. Так как же судить о движении? очень просто, иReactТак же воспользуемся инкрементным методом, если найдемindexвсегда увеличивается, указывая на то, что ни один узел не нужно перемещать. Мы сохраняем состояние того, нужно ли нам двигаться, устанавливая переменную.
function vue3Diff(prevChildren, nextChildren, parent) {
//...
outer: {
// ...
}
// 边界情况的判断
if (j > prevEnd && j <= nextEnd) {
// ...
} else if (j > nextEnd && j <= prevEnd) {
// ...
} else {
let prevStart = j,
nextStart = j,
nextLeft = nextEnd - nextStart + 1, // 新列表中剩余的节点长度
source = new Array(nextLeft).fill(-1), // 创建数组，填满-1
nextIndexMap = {}, // 新列表节点与index的映射
patched = 0,
move = false, // 是否移动
lastIndex = 0; // 记录上一次的位置
// 保存映射关系
for (let i = nextStart; i <= nextEnd; i++) {
let key = nextChildren[i].key
nextIndexMap[key] = i
}
// 去旧列表找位置
for (let i = prevStart; i <= prevEnd; i++) {
let prevNode = prevChildren[i],
prevKey = prevNode.key,
nextIndex = nextIndexMap[prevKey];
// 新列表中没有该节点 或者 已经更新了全部的新节点，直接删除旧节点
if (nextIndex === undefind || patched >= nextLeft) {
parent.removeChild(prevNode.el)
continue
}
// 找到对应的节点
let nextNode = nextChildren[nextIndex];
patch(prevNode, nextNode, parent);
// 给source赋值
source[nextIndex - nextStart] = i
patched++
// 递增方法，判断是否需要移动
if (nextIndex < lastIndex) {
move = false
} else {
lastIndex = nextIndex
}
}
if (move) {
// 需要移动
} else {
//不需要移动
}
}
}
3. Как движется DOM
Решив, нужно ли нам двигаться, нам нужно подумать, как двигаться. Когда нам нужно сделать перемещение DOM, первое, что мы должны сделать, это найтиsourceизсамая длинная возрастающая подпоследовательность.
function vue3Diff(prevChildren, nextChildren, parent) {
//...
if (move) {
const seq = lis(source); // [0, 1]
// 需要移动
} else {
//不需要移动
}
}
Что такое самая длинная возрастающая подпоследовательность: Учитывая числовую последовательность, найдите ее подпоследовательность, причем значения в подпоследовательности возрастают, а элементы подпоследовательности не обязательно идут подряд в исходной последовательности.
Например, данная последовательность чисел: [ 0, 8, 4, 12 ].
Тогда его самая длинная возрастающая подпоследовательность: [0, 8, 12].
Конечно, ответ может иметь несколько ситуаций, например: [0, 4, 12] также возможно.
Мы объясним самую длинную возрастающую подпоследовательность отдельно в следующем разделе.
В приведенном выше коде мы вызываемlisфункция поиска массиваsourceСамая длинная возрастающая подпоследовательность[ 0, 1 ]. Мы знаем, что значение исходного массива[2, 3, 1, -1], очевидно, что самая длинная возрастающая подпоследовательность должна быть[ 2, 3 ], но почему расчетный результат[ 0, 1 ]Шерстяная ткань? фактически[ 0, 1 ]представляет элементы самой длинной возрастающей подпоследовательности вsourceИндекс позиции в массиве, как показано на следующем изображении:
Мы основаны наsource,правильноновый списокперенумеровал и узнал最长递增子序列.
Мы переходим со спины на передsourceКаждый. На этом этапе произойдут три ситуации:
- Текущее значение
-1Это показывает, что узел является новым узлом, но так как мызадом напередОбходя, мы можем напрямую создать узел DOM и вставить его в конец очереди. - Текущий индекс
最长递增子序列значение в , то естьi === seq[j], что означает, что узел не нужно перемещать - Текущий индекс не
最长递增子序列Значение в , то это означает, что узел DOM нужно переместить.Это тоже хорошо понятно здесь.Мы также можем напрямую вставить узел DOM в хвост очереди, потому что хвост очереди сортируется.
function vue3Diff(prevChildren, nextChildren, parent) {
//...
if (move) {
// 需要移动
const seq = lis(source); // [0, 1]
let j = seq.length - 1; // 最长子序列的指针
// 从后向前遍历
for (let i = nextLeft - 1； i >= 0; i--) {
let pos = nextStart + i, // 对应新列表的index
nextNode = nextChildren[pos], // 找到vnode
nextPos = pos + 1， // 下一个节点的位置，用于移动DOM
refNode = nextPos >= nextChildren.length ? null : nextChildren[nextPos].el, //DOM节点
cur = source[i]; // 当前source的值，用来判断节点是否需要移动
if (cur === -1) {
// 情况1，该节点是全新节点
mount(nextNode, parent, refNode)
} else if (cur === seq[j]) {
// 情况2，是递增子序列，该节点不需要移动
// 让j指向下一个
j--
} else {
// 情况3，不是递增子序列，该节点需要移动
parent.insetBefore(nextNode.el, refNode)
}
}
} else {
//不需要移动
}
}
После разговора о случаях, когда вам нужно двигаться, давайте поговорим о случаях, когда вам не нужно двигаться. Если нам не нужно перемещаться, нам просто нужно решить, есть ли новый узел, который можно добавить к нему. Конкретный код выглядит следующим образом:
function vue3Diff(prevChildren, nextChildren, parent) {
//...
if (move) {
const seq = lis(source); // [0, 1]
let j = seq.length - 1; // 最长子序列的指针
// 从后向前遍历
for (let i = nextLeft - 1； i >= 0; i--) {
let pos = nextStart + i, // 对应新列表的index
nextNode = nextChildren[pos], // 找到vnode
nextPos = pos + 1， // 下一个节点的位置，用于移动DOM
refNode = nextPos >= nextChildren.length ? null : nextChildren[nextPos].el, //DOM节点
cur = source[i]; // 当前source的值，用来判断节点是否需要移动
if (cur === -1) {
// 情况1，该节点是全新节点
mount(nextNode, parent, refNode)
} else if (cur === seq[j]) {
// 情况2，是递增子序列，该节点不需要移动
// 让j指向下一个
j--
} else {
// 情况3，不是递增子序列，该节点需要移动
parent.insetBefore(nextNode.el, refNode)
}
}
} else {
//不需要移动
for (let i = nextLeft - 1； i >= 0; i--) {
let cur = source[i]; // 当前source的值，用来判断节点是否需要移动
if (cur === -1) {
let pos = nextStart + i, // 对应新列表的index
nextNode = nextChildren[pos], // 找到vnode
nextPos = pos + 1， // 下一个节点的位置，用于移动DOM
refNode = nextPos >= nextChildren.length ? null : nextChildren[nextPos].el, //DOM节点
mount(nextNode, parent, refNode)
}
}
}
}
слишком далекоvue3.0Дифф сделан.
4. Самая длинная возрастающая подпоследовательность
Возьмем этот массив в качестве примера
[10,9,2,5,3,8,7,13]
Мы можем рассмотреть эту задачу, используя идею динамического программирования. Идея динамического программирования состоит в том, чтобы разложить большую проблему на несколько небольших подзадач и попытаться получить оптимальные решения этих подзадач.Оптимальные решения подзадач могут использоваться в более крупных задачах, так что Через оптимальное решение маленькой задачи в конечном итоге будет получено оптимальное решение большой задачи.
Начнем с того, что допустим массив только с одним значением[13], то самая длинная возрастающая подпоследовательность массива равна[13]себя, длина которого1.Тогда мы считаем, что значение длины возрастающей последовательности каждого элемента равно 1
Итак, на этот раз мы добавляем значение в массив[7, 13], из-за7 < 13, поэтому самая длинная возрастающая подпоследовательность массива равна[7, 13], то длина2.Можем ли мы думать, что когда[7]меньше, чем[13]когда, с[7]Длина возрастающей последовательности для заголовка равна,[7]Длина и[13]сумма длин,Прямо сейчас1 + 1 = 2.
хорошо, давайте посчитаем массив на основе этой идеи. Сначала мы присваиваем начальное присвоение каждого значения1
первый7 < 13Так7Соответствующая длина13добавить 1 к длине1 + 1 = 2
Давай, сравним8. Мы первые и7Затем обнаружил, что приращение не выполняется, но это не имеет значения, мы можем продолжить и13Сравнивать,8 < 13Удовлетворить возрастание, то8длина также13Длина плюс один, а длина равна2
Давайте сравним3, мы сначала делаем это с8сравнение,3 < 8,Так3Длина8Длина , плюс один, то3длина3. Но это еще не конец, нам еще нужно отпустить3а также7В сравнении. такой же3 < 7, в этот момент нам нужно рассчитать длину, которая7Длина плюс один также3, мы сравниваем две длины,Если исходная длина не больше расчетного значения длины, мы заменим ее, в противном случае сохраним исходное значение.. из-за3 === 3, мы решили не заменять. Наконец, мы позволим3а также13для сравнения то же самое3 < 13, расчетная длина2, длиннее оригинала3Чтобы быть маленьким, мы решили сохранить исходное значение.
Дальнейшие вычисления аналогичны, и окончательный результат таков:
берем наибольшее значение из4, значение представляетКоличество самых длинных возрастающих подпоследовательностей. код показывает, как показано ниже:
function lis(arr) {
let len = arr.length,
dp = new Array(len).fill(1); // 用于保存长度
for (let i = len - 1; i >= 0; i--) {
let cur = arr[i]
for(let j = i + 1; j < len; j++) {
let next = arr[j]
// 如果是递增 取更大的长度值
if (cur < next) dp[i] = Math.max(dp[j]+1, dp[i])
}
}
return Math.max(...dp)
}
До сих пор мы рассмотрели основную самую длинную возрастающую подпоследовательность. Однако вvue3.0, нам нужен индекс самой длинной возрастающей подпоследовательности в исходном массиве. Поэтому нам также нужно создать массив для хранения самой длинной подпоследовательности каждого значения в массиве.index. Конкретный код выглядит следующим образом:
function lis(arr) {
let len = arr.length,
res = [],
dp = new Array(len).fill(1);
// 存默认index
for (let i = 0; i < len; i++) {
res.push([i])
}
for (let i = len - 1; i >= 0; i--) {
let cur = arr[i],
nextIndex = undefined;
// 如果为-1 直接跳过，因为-1代表的是新节点，不需要进行排序
if (cur === -1) continue
for (let j = i + 1; j < len; j++) {
let next = arr[j]
// 满足递增条件
if (cur < next) {
let max = dp[j] + 1
// 当前长度是否比原本的长度要大
if (max > dp[i]) {
dp[i] = max
nextIndex = j
}
}
}
// 记录满足条件的值，对应在数组中的index
if (nextIndex !== undefined) res[i].push(...res[nextIndex])
}
let index = dp.reduce((prev, cur, i, arr) => cur > arr[prev] ? i : prev, dp.length - 1)
// 返回最长的递增子序列的index
return result[index]
}