Интенсивное чтение "Подробное объяснение принципа DOM diff"

JavaScript React.js

Как инженерная задача, DOM diff требует определенного алгоритмического мышления, поэтому часто появляется в сценариях интервью, ведь это редкая алгоритмическая задача в инженерной сфере.

Будь то для целей интервью или для углубленного изучения, необходимо понять этот вопрос, поэтому мы посвятим главу разъяснению этого вопроса в предварительном интенсивном чтении.

интенсивное чтение

Dom diff — это то, что должны делать все фреймворки в наши дни, и причина этого — переход от ориентированного на действия процесса эпохи Jquery к представлению, управляемому данными.

Почему эра jQuery не нужна dom diff? Потому что DOM Diff передается в бизнес, мы называем.appendили.moveОперационные функции Dom, подобные этой, явно указывают, как выполнять diff diff.Это решение является наиболее эффективным, потому что только бизнес знает, как перемещать Dom.

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

Решение основано на данных, нам нужно только обратить внимание на то, как данные отображаются в пользовательский интерфейс, поэтому независимо от того, насколько сложна бизнес-логика, нам всегда нужно решить только сопоставление локальных состояний, что значительно сокращает обслуживание. сложность сложных систем, которые раньше требовали старого почерка логики, теперь это может сделать новичок, что является очень заметным изменением.

Но есть свои преимущества и недостатки.За этим, Dom diff должен выполняться фреймворком, поэтому эффективность Dom diff является важным показателем того, можно ли применить фреймворк, управляемый данными, к производственной среде.Далее, давайте взгляните на Dom diff Как это делает diff.

Разница в идеальном доме

Как показано на рисунке, идеальный diff Dom, естественно, повторно использует все, что может быть повторно использовано без утечки, и выполняет вставку или удаление только при обнаружении нового или удаленного. Такая операция наиболее близка к производительности нашего рукописного diff Dom в эпоху Jquery.

Жаль, что программа не может угадать ваши мысли, а за точное повторное использование приходится платить высокую цену: алгоритм сравнения с временной сложностью O(n³), что явно неприемлемо, поэтому идеальный алгоритм сравнения Дом не может быть использован. .

О происхождении O(n³). Поскольку любой узел в левом дереве может появиться в правом дереве, необходимо глубоко пройти по правому дереву, одновременно обходя левое дерево в глубину, чтобы найти соответствующую связь каждого узла, Временная сложность здесь O (n²), после что необходимо добавлять, удалять и перемещать каждый узел дерева.Этот процесс можно просто понять как добавление слоя цикла обхода, поэтому умножьте на n.

Упрощенный дом diff

Как показано на рисунке, временную сложность можно уменьшить до O(n), просто сравнивая по слоям. Послойное сравнение не является обходом по ширине, фактически оно предназначено для оценки различий между дочерними элементами узла, а одноуровневые узлы в родительском узле не нужно сравнивать.

Это действительно очень эффективно, но цена в том, что суждение немного глупо.Например, ac, очевидно, является операцией перемещения, но ошибочно распознается как удаление + добавление.

К счастью, повторное использование cross-DOM редко происходит в реальных бизнес-сценариях, поэтому частота этой неуклюжести на самом деле очень низка.В настоящее время мы не должны слишком увлекаться строгим академическим мышлением.В конце концов, фреймворк предназначен для практических проектов.Для сценариев которые редко появляются в реальных проектах, алгоритм можно игнорировать.

Ниже приведены три возможные ситуации в одном и том же слое diff, которые очень просты, просто посмотрите на картинку:

Так как же сравнение на одном уровне достигает временной сложности O(n)? Давайте рассмотрим идею конкретного фреймворка.

Дом разница для Vue

В Vue Dom diff всего шагов 5. Давайте посмотрим на первые три шага в сочетании со следующим рисунком:

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

Этот алгоритм обычно использует два указателя. Если после выполнения первых двух шагов обнаруживается, что указатели старого дерева перекрываются, а нового дерева еще нет, что это значит? Это означает, что остальная часть нового дерева является добавляемым узлом, который можно вставлять партиями. Просто, верно? А если бы было наоборот? Как показано ниже:

После выполнения первого и второго шагов обнаруживается, что указатели нового дерева перекрываются, а старого дерева еще нет, что это значит? Это означает, что остальная часть старого дерева не существует в новом дереве, и вы можете удалять его партиями.

Конечно, если указатель не обработался после шагов 1, 2, 3 и 4, то пора вводить небольшой алгоритм, и нам нужно обработать оставшиеся узлы за O(n) временной сложности. Учащиеся, знакомые с алгоритмом, должны быть в состоянии быстро понять, что когда массив выполняет некоторые операции обнаружения, временная сложность должна контролироваться до O(n), а для изменения времени необходимо использовать пространство карты, которое на самом деле является То же самое. Давайте посмотрим на следующий рисунок для деталей.

Как показано на рисунке, после шагов 1, 2, 3 и 4 у Old и New остаются остатки, поэтому пятый шаг разбит на три небольших шага:

  1. Перейдите по старому, чтобы создать карту, которая представляет собой потребление пространства для изменения времени. Он записывает нижний индекс индекса каждого старого узла, который позже можно найти в новом в новом.
  2. Траверс Новый, кстати, с помощью приведенной выше Карты записывает индекс, и при этом удаляется описание Старого, которого нет в Новом, причем удаляется он напрямую.
  3. Не существующая позиция заполняется 0, и мы получаемe:4 d:3 c:2 h:0Для такого массива добавляется индекс 0, а не-0 перемещается, и пакет может быть преобразован в операцию вставки.

Оптимизация последнего шага также очень важна. Мы не просто двигаемся, когда видим разницу. Чтобы оптимизировать производительность, нам нужно сделать так, чтобы количество ходов было как можно меньше, так как же мы можем двигаться? как можно меньше? Предположим, мы двигаемся по желанию, как показано на изображении ниже:

Но на самом деле лучший способ передвижения таков:

Зачем? Потому что при перемещении положения других элементов также меняются относительно.Можно добиться эффекта А, удовлетворяя эффекту Б. То есть найти те элементы, взаимное расположение которых в порядке и остается неизменным, так что эти позиции заведомо неверны.Оптимально переместить элементы .

Что такое относительный порядок?a c eТри буквы в старом первоначальном порядкеa b c d eотносительно упорядочен, нам нужно только положитьb dУдалив, положение этих трех букв естественно будет правильным. Итак, нам просто нужно найти новый массивсамая длинная подпоследовательность. Конкретный метод поиска можно рассматривать как небольшую проблему алгоритма, потому что фактический индекс каждого элемента известен.Например, в этом примере индекс выглядит следующим образом:

[b:1, d:3, a:0, c:2, e:4]

Невооруженным глазом непрерывная самоувеличивающаяся подстрока имеетb dа такжеa c e,из-заa c eдольше, так что выбирайте последнее.

Чтобы сделать это в программе, вы можете использовать жадную + дихотомию, чтобы найти ее, вы можете увидеть этот вопрос для деталейсамая длинная возрастающая подпоследовательность, временная сложность O(nlogn). Поскольку последовательность результатов алгоритма не соответствует порядку, Vue помогает найти правильную последовательность, предварительно скопировав массив.

React’s Dom diff

Предполагая такую ​​ситуацию, после того, как мы переместим a в c, каркас оттолкнется от конечного состояния, как найти эту мотивацию как можно быстрее? Реагировать принимаетСтратегия только сдвига вправо, то есть при изменении положения элемента он будет перемещаться только вправо, затем перемещается вправо, а остальные позиции будут упорядочены.

Посмотрим на картинку:

Переход по старой карте хранилища такой же, как и в Vue, а второй шаг — переход к новой,bиндекс от оригинала1стал0, вам нужно двигаться влево, но мы не двигаемся влево, мы двигаемся только вправо, потому что после всех правых ходов автоматически делается левый ход (после того, как предыдущий элемент перемещен вправо, он естественно толкается вперед. , чтобы добиться эффекта сдвига влево).

Точно так же нижний индекс c взят из2стал1, нам нужно двигаться влево, но мы продолжаем движение.

индекс а от0стали2, может, наконец, двигаться вправо!

Следующие нижние индексы d и e не изменились, поэтому их не нужно перемещать. Глядя на все в целом, мы можем обнаружить, что b и c естественным образом сдвинулись влево, потому что предыдущее a было удалено. Это эффективная операция по замене двух сдвигов влево одним сдвигом вправо.

В то же время мы обнаружили, что это нашло оптимальную стратегию смещения, о которой мы упоминали в начале.

Действительно ли этот алгоритм настолько умен? Очевидно, что нет, этот алгоритм является просто недоразумением.Существует алгоритм, использующий сдвиг вправо вместо сдвига влево, и алгоритм, использующий сдвиг влево вместо сдвига вправо., так как выбран правый сдвиг вместо левого, эффективность левого сдвига вместо правого должна быть потеряна.

Когда наиболее эффективно использовать левый сдвиг вместо правого? Это сцена, где последний элемент массива сдвигается к первому:

Очевидно, что сдвиг влево занимает всего один шаг, тогда сдвиг вправо составляет n-1 шагов, в данном примере это 4 шага.Посмотрим на схему алгоритма сдвига вправо:

Сначала найдите e, положение от4стал0, но мы не можем сдвинуться влево! Так что мне остается только оставаться на месте, и начинается трагедия.

Хотя алгоритм уже не оптимален, но что нужно сделать, то еще предстоит сделать.На самом деле, существует понятие lastIndex, которое не упоминалось ранее, потому что e уже находится в4, поэтому измените a с0перейти к1недостаточно, в этот момент a следует изменить с0перейти к5.

Путь к записиlastIndex = max(oldIndex, newIndex) => lastIndex = max(4, 0), следующий переход кlastIndex + 1то есть5:

найти из0стал5(обратите внимание, что в этот момент учитывается фактор lastIndex), поэтому сдвиньте вправо.

То же самое верно для b, c и d. В конце концов мы обнаружили, что было 4 сдвига вправо, и e также достигла первой позиции из-за естественного сдвига влево 4 раза, что соответствовало ожиданиям.

Так что это алгоритм плюсов и минусов. Добавление и удаление относительно просто, как и в Vue.

PS: Алгоритм сравнения последней версии React Dom, если он обновлен, добро пожаловать в раздел комментариев, указав, что, поскольку этот алгоритм кажется не таким эффективным, как Vue.

Суммировать

Dom diff заключает следующие соображения:

  1. Полное сравнение O(n³) неприемлемо, поэтому оно понижено до схемы O(n) сравнения одного и того же слоя.
  2. Почему возможно понижение? Поскольку перекрестная иерархия встречается редко, ее можно игнорировать.
  3. Так же уровень не простой.Сложность в том как эффективно двигаться,то есть минимальное количество шагов для полного перемещения.
  4. Чтобы не двигаться как можно больше, Vue сначала обходит слева и справа, чтобы пропустить неизменное, а затем находит самую длинную непрерывную подстроку и сохраняет ее неподвижной, а также перемещает другие элементы.
  5. React использует схему только со сдвигом вправо, которая обеспечивает лучшую производительность в большинстве бизнес-сценариев со сдвигом слева направо.

Адрес обсуждения:Интенсивное чтение «Принцип DOM diff», выпуск № 308 dt-fe/еженедельно

Если вы хотите принять участие в обсуждении, пожалуйста,кликните сюда, с новыми темами каждую неделю, выходящими по выходным или понедельникам. Интерфейс интенсивного чтения — поможет вам отфильтровать надежный контент.

Сфокусируйся наАккаунт WeChat для интенсивного чтения в интерфейсе

Заявление об авторских правах: Бесплатная перепечатка - некоммерческая - не производная - сохранить авторство (Лицензия Creative Commons 3.0)