[React] Глубокое понимание алгоритмов виртуального дома и сравнения

Эта статья одновременно публикуется в моем личном блоге:zhengyq.club

написать впереди

существуетReactсередина,Virtual Domа такжеdiffКомбинация значительно повышает эффективность рендеринга.diffАлгоритм из оригиналаO(n^3)Сложность становится тем, чем она являетсяO(n), тогда что вы делали в этом, эта статья раскроет вам ответ~

виртуальный дом и разница

Что такое виртуальный дом?

Virtual DOMэто концепция программирования. В этой концепцииUIОно сохраняется в памяти в идеализированном, или «виртуальном» представлении. существуетReactсередина,renderРезультат исполнения не реаленDOMnode, результат просто легкийJavaScriptобъект. так:

<div class="box">
    <span>hello world!</span>
</div>

Вышеприведенный код преобразуется в манекен, подобный этомуDOMструктура

{
    tag: "div",
    props: {
        class: "box"
    },
    children: [{
        tag: "span",
        props: {},
        children: ["hello world!"]
    }]
}

Что такое алгоритм сравнения?

diffАлгоритм, будет сравнивать новый и старый виртуальныйDOM, запишите изменения между ними, а затем обновите измененную часть в представлении. На самом деле, преждеdiffАлгоритм состоит в том, чтобы рекурсировать каждый узел через цикл, а затем сравнить, сложностьO(n^3),n— это общее количество узлов в дереве, поэтому производительность очень низкая.

Принцип dom-diff

diffАлгоритм сравнивает до и после виртуальногоDOM, чтобы получитьpatches(патч), потом со старымVirtual DOMСделайте сравнение, примените его там, где оно нуждается в обновлении, получите новоеVirtual DOM, в интернете есть очень наглядная картинка, которая может помочь

Чтобы объяснить эту картину: существует реальнаяDOM, сначала сопоставленный с виртуальнымDOM, на этот раз мы удаляем последнийpузел иson2узел, получил новый виртуальныйDOM,новыйvdomбудет и старыйvdomСравнивая различия, получаемpathesвозражать, после, старой истинеdomработать и получать новыеDOM.

Несколько стратегий diff

• Web UIсерединаDOMПеремещение узлов по иерархии происходит очень редко и может быть проигнорировано.

• Два компонента с одним и тем же классом будут генерировать похожие древовидные структуры, а два компонента с разными классами будут генерировать разные древовидные структуры.

• Для группы дочерних узлов одного уровня они могут бытьidдифференцировать.

Основываясь на трех вышеуказанных стратегиях,Reactсоответственноtree diff,component diffтак же какelement diffПроведена оптимизация алгоритма.

tree diff

На основе первой стратегииreactБудут сравниваться только узлы одного уровня, как показано на следующем рисунке, будут сравниваться только узлы одного цвета.DOMУзлы сравниваются. Когда обнаруживается, что узел не существует, весь узел и его дочерние узлы будут удалены, и дальнейшее сравнение не будет выполняться. Таким образом, для завершения всего узла требуется только один обход.DOMСравнение деревьев

если естьDOMперемещение узлов по иерархии,React diffЧто случится?

ReactПросто рассматривается только преобразование положения узлов одного уровня, для узлов разных уровней есть только операции создания и удаления. Если узел A переместить в узел D, то корневой узел обнаружит, что A отсутствует в дочерних узлах, и уничтожит A; затем D обнаружит, что у него есть дополнительный дочерний узел, и создаст новый дочерний узел ( включая его собственные дочерние узлы). node) в качестве своих дочерних узлов.react diffбудет выполняться в таком порядке:craete a -> create b -> create c -> delete a. Такого рода межуровневое перемещение узла не произойдет, но будут выполняться такие операции, как создание и удаление. Такого рода операции повлияют на производительность React, поэтому официальный представитель React не рекомендует такие операции. При разработке компонентов поддержание стабильной структуры dom поможет повысить производительность.

component diff

ReactСтратегия, принятая для сравнения между компонентами, также лаконична и эффективна.

• Если это компонент того же типа, продолжайте сравнивать дерево виртуального дома в соответствии с исходной стратегией.

• Если нет, оцените компонент какdirty component, тем самым заменяя все дочерние узлы под всем компонентом

• Для одного и того же типа компонента возможно, чтоVirtual DOMНичего не меняется, зная это наверняка, можно сэкономить много денег.diffвремя работы, такReactРазрешить пользователям проходитьshouldComponentUpdate()Определить, нужен ли компонентdiff

Например, на рисунке нижеcomponentDизменить наcomponentG, даже если дваcompoentСтруктура похожа, ноreactОн определит, что D и G не являются компонентами одного типа, и не будет сравнивать их структуры, а будет напрямую удалять d и воссоздавать G и его дочерние узлы, что повлияет на производительность реакции.

element diff

Когда узлы находятся на одном уровне,React diffОбеспечивает три операции с узлами: вставка, перемещение и удаление.

• Вставка: новаяcomponentТипа нет в старой коллекции -> новый узел, необходимо выполнить операцию вставки на новом узле.

• Переезд: новое в старой коллекцииcomponentтип иelementявляется обновляемым типом,generateComponentChildrenназываетсяreceiveComponent,В этой ситуацииprevChild=nextChild, вам нужно выполнить операцию перемещения, вы можете повторно использовать предыдущуюdomузел

• Удалить: Старыйcomponentтип, который также присутствует в новой коллекции, но соответствующийelementЕсли он отличается, его нельзя повторно использовать и обновлять напрямую, и необходимо выполнить операцию удаления или старыйcomponentЕсли вы не в новой коллекции, вам также необходимо выполнить операцию удаления

Например 🌰: Посмотрите на рисунок ниже, старый набор содержит узлы A, B, C, D, а обновленный набор содержит узлы B, A, D, C. На данный момент разница между новым и старым наборами составляет сравнивается, и обнаруживается, что B не равно A, затем B создается и вставляется в новый набор, старый набор A удаляется и так далее. . . Это очень утомительно, потому что это те же узлы, но расположение изменилось.В ответ на это явление React предлагает стратегию оптимизации, которая позволяет разработчикам добавлять уникальные ключи для различения одной и той же группы дочерних узлов на одном уровне [Примечание: это отражает роль ключа ~】

Ситуация, которую мы описали выше, неkeyСитуация, если естьkey(при условииkeyИмя, соответствующее каждому узлу на приведенном выше рисунке, например узел A, соответствующийkeyдля A), это будет выглядеть так:

diffпройдешьkeyОбнаружено, что узлы в новом и старом наборах являются одним и тем же узлом, поэтому нет необходимости удалять и создавать узлы, достаточно просто переместить положение узла в старом наборе и обновить его до положения узла в новый набор, на данный моментReactданоdiffВ результате B и D ничего не делают, а A и C двигаются.

Первый цикл через узлы новой коллекции, через уникальныйkeyМожно судить, существует ли один и тот же узел в новом и старом наборах, и если да, то выполняется операция перемещения, но положение текущего узла в старом наборе необходимо сравнить с положением старого набора перед перемещением. .lastIndexсравнить, если节点当前的位置<lastIndex, выполняется операция перемещения узла, иначе операция не выполняется. Это метод последовательной оптимизации,lastIndexОн был обновлен, указывая, что посещенный узел находится в самой правой позиции (т. е. наибольшей позиции) в старом наборе, если текущий посещенный узел в новом наборе больше.lastIndexЕсли значение большое, это означает, что текущий узел доступа более поздний, чем предыдущий узел в старом наборе, и узел не повлияет на положение других узлов, поэтому его не нужно добавлять в очередь разностей, т.е. то есть операция перемещения не выполняется.lastIndexчасов до переезда

Поговорим об общем процессе (следующее_mountIndexэто местоположение текущего узла,lastIndexдля эталонной позиции)

1. Получить B из нового набора, определить, существует ли такой же узел в старом наборе, и определить, была ли выполнена операция перемещения, путем сравнения позиций узлов._mountIndex=1,В настоящее времяlastIndex = 0, не удовлетвореныchild._mountIndex < lastIndexусловие, поэтому операция перемещения не выполняется на B; обновление в это времяlastIndex = Math.max(prevChild._mountIndex, lastIndex), [где prevChild.mountIndex представляет позицию B в старой коллекции].lastIndex=1, и обновите позицию B до позиции в новом набореprevChild._mountIndex=nextIndex, теперь в новом набореB._mountIndex=0,nextIndex++Введите решение следующего узла

2. Получите A из нового набора, определите, что тот же самый узел A существует в старом наборе, и решите, следует ли выполнять операцию перемещения, сравнивая позиции узла и позицию A в старом наборе.A._mountIndex=0,В настоящее времяlastIndex=1, удовлетворятьchild.mountIndex<lastIndexусловие, поэтому операция перемещения выполняется на AenqueueMove(this, child._mountIndex, toIndex),вtoIndexНа самом деле этоnextIndex, указывающее позицию A, в которую необходимо перейти; обновитьlastIndex = Math.max(prevChild._mountIndex, lastIndex),ноlastIndex ＝ 1, и воляAпозиция обновляется до позиции в новой коллекцииprevChild._mountIndex = nextIndex, теперь в новом набореA._mountIndex = 1，nextIndex++Введите решение следующего узла.

3. Возьмите D из нового набора, оцените, есть ли такие же узлы в старом наборе, и решите, следует ли выполнять операцию перемещения, сравнив позиции и позицию D в старом наборе.D._mountIndex=3,В настоящее времяlastIndex=1, не удовлетвореныchild._mountIndex<lastIndexусловие, поэтому на D не выполняется операция перемещения; обновитьlastIndex=Math.max(prevChild._mountIndex, lastIndex),ноlastIndex=3, и обновите позицию D до позиции в новом набореprevChild._mountIndex=nextIndex, теперь в новом набореD._mountIndex=2,nextIndex++Введите решение следующего узла

4, узел C такой же

Что, если существует нечто большее, чем просто отношение обмена позициями в старом и новом множествах? Как работает React diff? (Ключом каждого узла на рисунке ниже является соответствующее имя узла)

1. Получить B из нового набора, определить, существует ли такой же узел в старом наборе, и найти положение B в старом наборе.B._mountIndex=1,В настоящее времяlastIndex=0, так что операция перемещения над B не выполняется; обновитьlastIndex=1, и обновите позицию B до позиции в новом набореB._mountIndex=0, nextIndex++ вводит оценку следующего узла

2. Получить в новом наборе узел E. Так как такой же узел не существует в старом наборе, создайте новый узел E, обновитеlastIndex=1и обновите позицию E до позиции в новом наборе,nextIndex++Введите решение следующего узла.

3. Получите узел C в новом наборе, и такой же узел существует в старом наборе,C._mountIndex=2,lastIndex=1,В настоящее времяC._mountIndex > lastIndex, поэтому на C не выполняется операция перемещения; обновитьlastIndex=2, и обновить позицию C до позиции в новом наборе, а nextIndex++ вводит оценку следующего узла.

4. Получите узел A в новом наборе, такой же узел существует в старом наборе,A._mountIndex=0,lastIndex=2,В настоящее времяA._mountIndex < lastIndex, выполнить операцию перемещения на A; обновитьlastIndex=2, и обновите позицию A до позиции в новом наборе,nextIndex++Введите решение следующего узла.

5. При завершении всех узлов в новом набореdiffНаконец, необходимо пройти по старому множеству в цикле, чтобы определить, есть ли узел, которого нет в новом множестве, но все еще существует в старом множестве.Найден, что есть такой узел D, поэтому узел Д удален.diffполностью завершена.

Суммировать

на основеdiffтакая стратегия, такreactРекомендуется добавить уникальныеkeyспособ оптимизации, который может включать проблему:

Что не так с использованием индекса в качестве ключа?

indexтак какkey, если мы удаляем узел, то следующий элемент массива может двигаться вперед.В это время перемещенный узел и удаленный узел совпадаютkey, вreact, еслиkeyЕсли они одинаковы, они будут считаться одними и теми же компонентами, но эти два компонента не одинаковы, что вызовет некоторые проблемы, которые мы не хотим видеть ~ поэтомуkeyЗначение , мы должны рассмотреть его, а затем определить ~

наконец

В этой статье подробно описывается виртуальныйdomа такжеdiffалгоритм, мы должны различатьkeyНетkeyКак сделать сравнение, а также узнать, почему временная сложность была значительно улучшена и т. д. ~ Если что-то не так со статьей, пожалуйста, укажите ~ Давайте учиться вместе и добиваться прогресса вместе ~~

Если вы хотите получать статьи быстрее, обратите внимание на мой паблик-аккаунт "веб-дневник"~

Справочная статья

• Серия анализа исходного кода React - невероятная реакция diff

• Анализ и реализация исходного кода React (3): практическая работа с DOM Diff