Анализ основного алгоритма Vue3 DOM Diff

исходный код Vue.js
Анализ основного алгоритма Vue3 DOM Diff

"Видимость: 🌟🌟🌟🌟🌟"

"Вкус: Острые жареные моллюски"

"Время приготовления: 10 мин."

Эта статья попала в одноименный склад Github фронтенд-столовойgithub.com/Geekhyt, Добро пожаловать в кафетерий. Если вы считаете, что еда и вино вкусные, Звезда станет отличным поощрением для владельца кафетерия.

Чтобы понять основной алгоритм DOM Diff в Vue3, мы должны начать с реального вопроса о LeetCode.

Давайте вместе прочитаем заголовок:

LeetCode Zhenti 300. Самая длинная восходящая последовательность

Дан неупорядоченный массив целых чисел, найти длину самой длинной возрастающей подпоследовательности в нем.

Пример:

Введите: [10, 9, 2, 5, 3, 7, 101, 18] Выход: 4 Объяснение: Самая длинная возрастающая подпоследовательность — это [2, 3, 7, 101], то есть 4.

инструкция:

  • Может быть несколько комбинаций самых длинных восходящих подпоследовательностей, вам просто нужно вывести соответствующую длину.
  • Временная сложность вашего алгоритма должна быть O(n2) .

Для продвинутых: можете ли вы уменьшить временную сложность алгоритма до O(nlogn)?

Чтение окончено.

Что такое восходящая подпоследовательность?

Во-первых, нам нужно понять и различать основные понятия:

  • Подстрока: должна быть непрерывной
  • Подпоследовательность: Подпоследовательности не требуют непрерывности Пример: [6, 9, 12] является подпоследовательностью [1, 3, 6, 8, 9, 10, 12]
  • Восходящая/увеличивающаяся подпоследовательность: должна быть строго возрастающей/увеличивающейся подпоследовательностью

注意：子序列中元素的相对顺序必须保持在原始数组中的相对顺序

отвечать

динамическое программирование

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

мы можем поставить государствоdp[i]определяется какnums[i]Этот номер заканчивается (должен включатьnums[i]) и длину самой длинной возрастающей подпоследовательностиdp[i]Инициализируется значением 1, поскольку каждый элемент является отдельной подпоследовательностью.

Определите уравнение перехода состояния:

  • когда мы пересекаемnums[i]При необходимо сравнить пройденныйnums[j]
  • еслиnums[i] > nums[j],nums[i]можно добавить в последовательностьnums[j]Наконец, длинаdp[j] + 1Примечание:(0 <= j < i) (nums[j] < nums[i]) 
const lengthOfLIS = function(nums) {
    let n = nums.length;
    if (n == 0) {
        return 0;
    }
    let dp = new Array(n).fill(1);
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    return Math.max(...dp) 
}
  • Временная сложность: O(n^2)
  • Космическая сложность: O(n)

Вот нарисовал картинку для вашего понимания.

Жадный + бинарный поиск

Учащиеся, которые не знакомы с жадным и бинарным поиском, могут перейти к двум моим столбцам, чтобы начать.

Здесь объедините этот вопрос, чтобы понять жадную идею, которая также является последовательностью длины 2.[1,2]Конечно[1,4]Хорошо, потому что у него больше возможностей. Другими словами, мы хотим сформировать самую длинную возрастающую подпоследовательность, Необходимо сделать подъем в этой подпоследовательности как можно медленнее, чтобы он был длиннее.

мы можем создатьtailsМассив, используемый для хранения самой длинной возрастающей подпоследовательности, если текущий обходnums[i]больше, чемtailsпоследний элемент (т.е.tails), мы можем добавить его в конец. В противном случае ищемtailsпервое из которых большеnums[i]номер и заменить его. Поскольку это монотонно возрастающая последовательность, мы можем использовать бинарный поиск, чтобы уменьшить временную сложность доO(logn).

const lengthOfLIS = function(nums) {
    let len = nums.length;
    if (len <= 1) {
        return len;
    }
    let tails = [nums[0]];
    for (let i = 0; i < len; i++) {
        // 当前遍历元素 nums[i] 大于 前一个递增子序列的 尾元素时，追加到后面即可
        if (nums[i] > tails[tails.length - 1]) {
            tails.push(nums[i]);
        } else {
            // 否则，查找递增子序列中第一个大于当前值的元素，用当前遍历元素 nums[i] 替换它
            // 递增序列，可以使用二分查找
            let left = 0;
            let right = tails.length - 1;
            while (left < right) {
                let mid = (left + right) >> 1;
                if (tails[mid] < nums[i]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            tails[left] = nums[i];
        }
    }
    return tails.length;
};
  • Временная сложность: O(nlogn)
  • Космическая сложность: O(n)

Вот нарисовал картинку для вашего понимания.

注意：这种方式被替换后组成的新数组不一定是解法一中正确结果的数组，但长度是一样的，不影响我们对此题求解。

Например этот случай:[1,4,5,2,3,7,0]

  • tails = [1]
  • tails = [1,4]
  • tails = [1,4,5]
  • tails = [1,2,5]
  • tails = [1,2,3]
  • tails = [1,2,3,7]
  • tails = [0,2,3,7]

мы можем видеть в концеtailsДлина правильная, но значение внутри неверное, потому что замена на последнем шаге разрушает свойства подпоследовательности.

Базовый алгоритм Vue3 DOM Diff

После выяснения алгоритма самой длинной возрастающей подпоследовательности гораздо проще взглянуть на основной алгоритм DOM Diff в Vue3.

Я знаю, что вы не можете ждать, но мне все равно нужно вставить сюда предложение. Если вы не знаете React и алгоритм DOM Diff в Vue2, вы можете перейти по этой ссылке, чтобы узнать. Пошаговое обучение может дать вам лучшее понимание.

Вернувшись, думаем над вопросом:Diff 算法的目的是什么？

"Чтобы снизить нагрузку на производительность при манипулировании DOM, мы хотим как можно больше повторно использовать элементы DOM. Итак, нам нужно выяснить, есть ли узлы, которые нужно переместить, как их следует переместить, и выяснить, какие узлы нужно добавить или удалить."

Итак, давайте перейдем к теме этой статьи, основному алгоритму Vue3 DOM Diff.

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

Следующий код является основным алгоритмом DOM Diff для Vue 3. Для вашего удобства я добавил путь в исходный код.

// packages/runtime-core/src/renderer.ts
function getSequence(arr: number[]): number[] {
  const p = arr.slice()
  const result = [0]
  let i, j, u, v, c
  const len = arr.length
  for (i = 0; i < len; i++) {
    const arrI = arr[i]
    if (arrI !== 0) {
      j = result[result.length - 1]
      if (arr[j] < arrI) {
        p[i] = j
        result.push(i)
        continue
      }
      u = 0
      v = result.length - 1
      while (u < v) {
        c = ((u + v) / 2) | 0
        if (arr[result[c]] < arrI) {
          u = c + 1
        } else {
          v = c
        }
      }
      if (arrI < arr[result[u]]) {
        if (u > 0) {
          p[i] = result[u - 1]
        }
        result[u] = i
      }
    }
  }
  u = result.length
  v = result[u - 1]
  while (u-- > 0) {
    result[u] = v
    v = p[v]
  }
  return result
}

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

На самом деле, основная идея этого алгоритма — второе решение упомянутой выше самой длинной возрастающей подпоследовательности — метод жадного + бинарного поиска. Вот почему не торопитесь это говорить, потому что если вы понимаете вышеизложенноеLeetCodeРешение проблем, оно у вас уже естьVue3изDOM DiffИдея основного алгоритма.

Однако, если вы хотите понять детали каждой строки кода, вам нужно поставитьVue3весьDOM Diffв контексте. И следует отметить, что в приведенном выше кодеgetSequenceВозвращаемое значение метода такое же, какLeetCodeВозвращаемое значение, требуемое в вопросе, отличается,getSequenceВозвращает индекс самой длинной возрастающей подпоследовательности. Как мы упоминали выше, есть некоторые ошибки в использовании жадного + бинарного поиска и замены, которые могут привести к неправильным результатам. Vue3 решает эту проблему, давайте посмотрим, как она решается.

// packages/runtime-core/src/renderer.ts
function getSequence(arr: number[]): number[] {
  const p = arr.slice() // 拷贝一个数组 p
  const result = [0]
  let i, j, u, v, c
  const len = arr.length
  for (i = 0; i < len; i++) {
    const arrI = arr[i]
    // 排除等于 0 的情况
    if (arrI !== 0) {
      j = result[result.length - 1]
      // 与最后一项进行比较
      if (arr[j] < arrI) { 
        p[i] = j // 最后一项与 p 对应的索引进行对应
        result.push(i)
        continue
      }
      // arrI 比 arr[j] 小，使用二分查找找到后替换它
      // 定义二分查找区间
      u = 0
      v = result.length - 1
      // 开启二分查找
      while (u < v) {
        // 取整得到当前位置
        c = ((u + v) / 2) | 0
        if (arr[result[c]] < arrI) {
          u = c + 1
        } else {
          v = c
        }
      }
      // 比较 => 替换
      if (arrI < arr[result[u]]) {
        if (u > 0) { 
          p[i] = result[u - 1]  // 正确的结果
        }
        result[u] = i // 有可能替换会导致结果不正确，需要一个新数组 p 记录正确的结果
      }
    }
  }
  u = result.length
  v = result[u - 1]
  // 倒叙回溯 用 p 覆盖 result 进而找到最终正确的索引
  while (u-- > 0) {
    result[u] = v
    v = p[v]
  }
  return result
}

Vue3 копирует массив для хранения правильного результата, а затем решает проблему неверных значений, которые могут быть вызваны жадным + бинарным поиском и заменой путем обратного присваивания.

Это основная часть алгоритма Vue3 DOM Diff. Добро пожаловать в интерфейсную столовую, гость, прогуляйтесь не спеша~

❤️Любовное тройное комбо

1. Если вы считаете, что еда и напитки в столовой по-прежнему аппетитны, просто поставьте лайк и поддержите это, ваше"отличный"моя самая большая мотивация.

2. Обратите внимание на фронтальную столовую официального аккаунта,"Ешьте каждый прием пищи!"

3. Нравится, комментирует, пересылает === призывает больше!

Категории