существуетИнтенсивное чтение "Принцип DOM diff"В статье мы упомянули, что Vue использует жадный алгоритм + деление пополам для нахождения самой длинной восходящей подпоследовательности, но не углублялись в принцип этого алгоритма, поэтому для подробного объяснения была открыта специальная глава.
Кроме того, как проблема алгоритма, самая длинная восходящая подпоследовательность является очень классической, и она практична и сложна в отрасли, поэтому я надеюсь, что каждый должен ее освоить.
интенсивное чтение
Какая самая длинная восходящая подпоследовательность? Он заключается в том, чтобы найти самую длинную непрерывно возрастающую часть массива, как показано на следующем рисунке:
Если сама последовательность является возрастающей, вернуть себя; если ни один сегмент последовательности не является возрастающим, вернуть любое число. Как видно на рисунке, хотя3, 7, 22также повышается, но поскольку22После этого его нельзя продолжить, поэтому его длина равна 3, что совпадает с3, 7, 8, 9, 11, 12Для сравнения, он, конечно, не самый длинный, поэтому найти его непросто.
В конкретном сценарии DOM diff, чтобы убедиться, что перемещается как можно меньше DOM, нам нужносохранить самый длинный восходящий подпорядокНе двигайтесь, просто перемещайте другие элементы. Зачем? Поскольку самая длинная восходящая подпоследовательность сама по себе относительно упорядочена, пока другие элементы перемещаются, ответ будет получен. Еще этот пример, предполагая, что исходный DOM находится в таком порядке возрастания (конечно, это должно быть 1 2 3 4 последовательных индекса, но не имеет значения, является ли алгоритм непрерывным или нет, пока он увеличивается):
Если вы сохраните самый длинный восходящий подпорядок без изменений, вам нужно будет переместиться всего три раза, чтобы восстановить:
Никакое другое движение не меньше трех шагов,Потому что мы сохранили детали, которые уже в порядке, насколько это возможно..
Итак, вопрос в том, как найти эту самую длинную восходящую подпоследовательность? Решения, о которых легче думать, это: насилие и динамическое программирование.
решение грубой силы
Временная сложность: O(2ⁿ)
Наконец, мы хотим сгенерировать самую длинную подпоследовательность, поэтому давайте смоделируем процесс создания этой подпоследовательности, но этот процесс насильственный.
Как создать подпоследовательность путем моделирования грубой силы? Это попытка выбрать или не выбрать текущий номер каждый раз из диапазона [0,n], при условии, что номер, выбранный после, больше, чем предыдущий номер. Так как длина массива равна n, каждое число может быть выбрано или нет, то есть у каждого числа есть два варианта, поэтому будет сгенерировано не более 2ⁿ результатов, и из него можно найти наибольшую длину, что и является ответом:
Если вы попробуете это тупо, вы обязательно сможете попробовать самый длинный сегмент, и вы можете записать самый длинный сегмент во время прохождения процесса.
Так как этот метод слишком неэффективен, его не рекомендуют, но этот вид насильственного мышления все же нужно освоить.
динамическое программирование
Временная сложность: O(n²)
Если рассматривать эту задачу с точки зрения динамического программирования, то определение DP(i) эмпирическое: длина самой длинной подпоследовательности, когда она заканчивается i-й строкой.
Здесь есть опыт, то есть общее возвращаемое значение DP датчика движения является ответом, а задача строки часто заканчивается на i-й строке, поэтому просканируйте ее один раз. При этом самая длинная подпоследовательность имеет повторяющиеся подзадачи, то есть i-я операция ответа включает в себя часть предыдущих вычислений.Чтобы не повторять вычисление, используется динамическое программирование.
Тогда это зависит от соотношения между результатом пункта i и предыдущими результатами, как показано на рисунке для удобства понимания:
Предположим, мы смотрим на число 8, которое и есть DP(4). Поскольку предыдущие DP (0), DP (1) ... DP (3) были рассчитаны в это время, давайте посмотрим, как DP (4) связан с предыдущими результатами расчета.
Простое наблюдение показывает, что еслиnums[i] > nums[i-1], то DP(i) равноDP(i-1) + 1, это очевидно, то есть если 8 больше 4, то ответ на позиции 8 равен длине ответа на позиции 4 + 1, если значение на позиции 8 равно 3, что меньше 4, то ответ 1, потому что предыдущий Чтобы встретить восходящие отношения, вы можете бороться только в одиночку с числом 3.
Но если хорошенько подумать, то обнаружится, что эта подпоследовательность не обязательно должна быть непрерывной: если i-й элемент сочетается с i-2, i-3 элементом, то она может быть длиннее, чем комбинация с i-м элементом. -1 предмет? Возьмем встречный пример:
очевидно,1, 2, 3, 4Комбинированная — это самая длинная восходящая подпоследовательность, если вы просто посмотрите на5, 4, то ответ может быть только4.
Именно из-за этой особенности прерывности нам необходимо сравнивать i-й предмет с j-м по очереди, гдеj=[0,i-1], только сравнив его со всеми предыдущими элементами, мы можем быть уверены, что результат, найденный i-м элементом, действительно является самым длинным:
Итак, как рассчитать временную сложность? В решении динамического программирования мы сначала выполняем цикл от 0 до n, а затем делаем это для каждого из этих i.[0,i-1], поэтому число вычислений равно1 + 2 + ... + n = n * (n + 1) / 2, после исключения констант порядок величины равен O(n²).
Жадность + два очка
Временная сложность: O(nlogn)
Честно говоря, обычно хорошо иметь возможность придумать решение для динамического программирования, но очень сложно дополнительно оптимизировать временную сложность. Если вы еще не ответили на этот вопрос и хотите оспорить его, прекратите читать здесь.
Что ж, ответ озвучен.Честно говоря,этот метод не похож на то,что придумало нормальное человеческое мышление.У него много мысленных скачков,поэтому я не могу привести процесс вывода мышления.Скажем только вывод: жадность + дихотомия.
Если нам нужно сказать, что мы думаем, мы можем посмотреть на временную сложность постфактум.Как правило, временная сложность n² станет nlogn после оптимизации, а временная сложность бинарного поиска равна logn, поэтому мы отчаянно пытаемся найти способ объединить их Бар.
Конкретный план состоит всего из одного предложения:Используя структуру стека, если значение больше, чем все значения в стеке, оно помещается в стек, в противном случае заменяется наименьшее число, большее, чем оно, и длина конечного стека является ответом:
Сначала объясните временную сложность.По причинам, связанным с работой, числа, хранящиеся в стеке, расположены в порядке возрастания, поэтому для сравнения и вставки можно использовать двоичный метод.Сложность logn, а внешний слой-n петель, поэтому общая временная сложность O(nlogn) . Другая проблема с этой схемой заключается в том, что длина ответа является точной, но массив в стеке может быть неправильным. Если вы хотите полностью понять это предложение, вы должны полностью понять принцип этого алгоритма, и только после понимания принципа вы сможете узнать, как его улучшить, чтобы получить правильную подпоследовательность.
Далее, чтобы объяснить принцип,Начальное мышление не сложное, его можно посмотреть за чаем. Прежде всего, мы должны иметь интуитивное понимание, то есть, чтобы сделать самую длинную восходящую подпоследовательность максимально длинной, мы должны изо всех сил стараться, чтобы скорость роста выбранных чисел была как можно более медленной, иначе, это максимально быстро. Например, если число, которое мы выбираем, равно0, 1, 2, 3, 4Тогда этот вид жадности относительно стабилен, потому что он рос максимально медленно, и можно заложить высокую вероятность столкнуться позже. Но если мы выберем0, 1, 100выбери это100Вы должны паниковать, потому что она увеличивается до100,Позади100Разве вы не отказываетесь от всех чисел внутри? на этот раз100Это не обязательно мудрый выбор, но его выбрасывание может иметь больше места в будущем.Это на самом деле жадное мышление.Так называемое локальное оптимальное решение является глобальным оптимальным решением.
Но вышеприведенная мысль явно неполна, продолжаем думать, если читаем0, 1, 100, если сзади нет числа, то100Вы все еще можете поставить его, хотя100Он огромен, но он последний и все еще полезен.Поэтому при переходе слева направо, если вы встретите большее число, вы должны сначала ввести его., дело в том, что если вы продолжите перечитывать, вы прочитаете больше, чем100Число все еще мало, что мне делать?
Если вы не можете сделать скачок в мышлении здесь, анализ может остановиться только там. Вы можете почувствовать, что можете продолжать анализировать, например, столкнувшись с5, очевидно,100Выжимай, потому что0, 1, 5а также0, 1, 100длина 3, но0, 1, 5«Потенциал» значительно выше, чем0, 1, 100Большой, поэтому длина осталась прежней, у одного больший потенциал и его необходимо заменить! Эта идея верна, но в другом сценарии, если вы столкнетесь с3, 7, 11, 15, вы столкнулись9, как изменить? Если рассматривать потенциал,3, 7, 9Потенциал лучший, но длина приносится в жертву с 4 на 3, и не знаешь, если нет сравнения9Если он больше, если его больше нет, эта длина не так хороша, как исходная 4; если это считается по длине, оставьте ее.3, 7, 11, 15, в случае нескольких последовательных10, 12, 13, 14Также ошеломлен, немного чувство близорукости.
Вот и вопрос, как поступить с очередным номером, чтобы не быть недальновидным в будущем, и "ухватиться за устойчивое счастье".Прыгающее мышление начинается здесь, ответ "если значение больше всех значений в стеке, то протолкнуть стек, в противном случае заменить наименьшее число большее, чем оно", упомянутое в приведенной выше схеме. Это отражает скачкообразное мышление, и суть реализации настоящего и будущего заключается в следующем:Жертвуя правильностью содержимого стека и гарантируя правильную общую длину, каждый шаг может использовать наилучшую возможность в будущем.Только когда общая длина верна, можно гарантировать самую длинную последовательность.Что касается принесения в жертву правильности содержимого стека, это стоит дорого, но в обмен на возможность в будущем, по крайней мере, длина может получить правильный результат, если содержание также будет корректным, то можно добавить некоторые вспомогательные средства для его решения, о которых речь пойдет позже. Так что в целом эта жертва очень оправдана.На следующем рисунке показано, почему жертвование правильностью содержимого стека может привести к правильной длине и использовать будущие возможности.
Возьмем крайний пример:3, 7, 11, 15, 9, 11, 12, если вы будете придерживаться того, что нашли в начале3, 7, 11, 15, это всего 4 в длину, но если вы сдадитесь11, 15,Пучок3, 7, 9, 11, 12Подключено, длина лучше. Согласно жадному алгоритму, мы сначала встретим3 7 11 15, так как каждое число больше предыдущего, тут и думать нечего, просто запихиваем в стек:
встретить9это прекрасное время,В настоящее время9Не самый большой, чтобы уловить устойчивое счастье, мы просто сравниваем9немного больше11заменили, что в результате?
Во-первых, длина массива не изменится, потому что операция замены не изменит длину массива.9Позже значения нет, и мы не растерялись.На данный момент выходная длина 4 по-прежнему является лучшим ответом. мы продолжаем, следующая встреча11, ставим еще чуть больше15заменять:
В этот момент мы заменяем последнюю цифру и находим3, 7, 9, 11Наконец разумный порядок, и длина и3, 7, 11, 15Такой же,но больше потенциала, следующий12Поставил в конце как надо, и получил окончательный ответ: 5.
На самом деле суть этого алгоритма здесь не разъяснена внятно, вернемся к3, 7, 9, 15Этот шаг, выяснить9Почему его можно заменить11.
Предположение9Позади большой99, то следующий шаг99будет добавлено непосредственно в конец:
То, что мы получаем в этот момент,3, 7, 9, 15, 99, но если вы присмотритесь, то обнаружите, что в исходной последовательности9существует15позже, потому что наша вставка приводит к9помещать15раньше, так что это явно не правильный ответ, но длина правильная, потому что этот ответ эквивалентен нашему выбору3, 7, 11, 15, 99! Почему это так понятно? потому чтоПока последнее число не заменено, очередь в нашем сердце на самом деле является исходной очередью.
То есть, пока стек не полностью заменен, вновь вставленное значение всегда будет служить только заполнителем. Цель состоит в том, чтобы позволить легко вставлять новое значение, но если действительно нет нового значения для вставки, то хотя содержимое стека Нет, но хотя бы длина правильная, т.к.9Это не совсем так, когда его не заменили9, это просто заполнитель, значение по-прежнему11. Поэтому, как бы вы его ни меняли, пока последний не заменяется, операция замены недействительна.Возьмем другой пример:
видимый,1, 2, 3, 4не могу поставить7, 8, 9, 10, 11заменены, поэтому окончательный результат1, 2, 3, 4, 11, но это не беда, пока замена не сделана, ответ7, 8, 9, 10, 11, просто мы его не записывали, но если посмотреть на длину, между ними нет никакой разницы, так что это не проблема. что если1, 2, 3, 4, 5, 6Шерстяная ткань? Давайте посмотрим, что произойдет, когда мы сможем заменить его:
виден при замене на5, порядок последовательности правильный, потому что1, 2, 3, 4, 5был полностью заменен7, 8, 9, 10, 11, а потенциал больше его, мы нашли оптимальное локальное решение. так1, 2, 3, 4, 11здесь1, 2, 3, 4как под прикрытием, в11Когда он был еще там, он сказал7, 8, 9, 10, 11для босса (на самом деле1сказать7для босса,2сказать8для начальника и так далее), но когда5Когда вы входите,1, 2, 3, 4, 5ты можешь и7, 8, 9, 10, 11Он повернулся лицом, потому что его сила превысила силу первоначального босса.
Затем, казалось бы, незначительные замены, которые мы сделали перед нами, на самом деле, на самом деле, чтобы продолжать искать наилучшее возможное решение в будущем до дня первых дней. Если ранних дней нет, это хорошо быть младшим братом , В первые дни максимальная длина была обновлена, поэтому такая жадность может учитывать как правильность, так и эффективность.
Наконец, давайте посмотрим, как мы можем найти правильную последовательность при поиске ответа?
найти правильную последовательность
Найти правильную последовательность непросто, давайте рассмотрим такую ситуацию:
После завершения жадного алгоритма общая длина верна, но очевидно, что порядок по-прежнему неправильный. Для того, чтобы облегчить вычисление, преобразуем его в индекс при сохранении:
И используйте хранилище двумерных массивов, чтобы можно было сохранить замененные числа. Когда вычисление завершено, мы начинаем с последнего бита и ищем вперед,Как только найдено значение, которое не монотонно убывает, поиск продолжается вверх по массиву до первого узла.
Таким образом, в приведенном выше примере последний последовательный индекс равен[0, 1, 2, 3, 4, 5, 9], соответствующие цифры[10, 20, 30, 40, 50, 60, 61],И это число является самой длинной подпоследовательностью с наибольшим потенциалом.
Суммировать
Итак, сколько Vue, наконец, использовал жадность для вычисления самой длинной восходящей подпоследовательности? На самом деле это соотношение между O(n) и O(nlogn) Давайте посмотрим на картинку:
Видно, что тенденция роста временной сложности O(nlogn) едва ли приемлема, особенно в инженерных сценариях, когда количество дочерних узлов родительского узла не может быть слишком большим, это не займет слишком много времени на анализ. Преимущество заключается в минимальном движении DOM. Это идеальное сочетание алгоритма и инженерной практики.
Адрес обсуждения:Интенсивное чтение «Самая длинная восходящая последовательность DOM diff», выпуск № 310 dt-fe / еженедельно
Если вы хотите принять участие в обсуждении, пожалуйста,кликните сюда, с новыми темами каждую неделю, выходящими по выходным или понедельникам. Интерфейс интенсивного чтения — поможет вам отфильтровать надежный контент.
Сфокусируйся наАккаунт WeChat для интенсивного чтения в интерфейсе
Заявление об авторских правах: Бесплатная перепечатка - некоммерческая - не производная - сохранить авторство (Лицензия Creative Commons 3.0)