“🌟🌟🌟🌟🌟“

“Taste: Spicy fried clams“

“Cooking time: 10min“

Github github.com/Geekhyt, welcome to the canteen, if you think the food is delicious, a Star is a great encouragement to the canteen owner.

To understand Vue3’s DOM Diff core algorithm, let’s start with a Real LeetCode problem.

Let’s read the questions together:

The longest ascending subsequence

Given an unordered array of integers, find the length of the longest ascending subsequence.

Example:

Input: [10,9,2,5,3,7,101,18] output: 4 explanation: the longest ascending subsequence is [2,3,7,101], which has a length of 4.

Description:

  • There can be multiple combinations of the longest ascending subsequence, and you just output the corresponding length.
  • The time complexity of your algorithm should be O(n2).

Advanced: Can you reduce the time complexity of the algorithm to O(nlogn)?

End of reading.

What is an ascending subsequence?

First, we need to understand and distinguish the basic concepts:

  • Substring: must be continuous
  • Subsequence: Subsequences do not require continuity for example, [6, 9, 12] is a subsequence of [1, 3, 6, 8, 9, 10, 12]
  • Ascending/increasing subsequence: must be a strictly ascending/increasing subsequence

Note: The relative order of the elements in the subsequence must remain the relative order in the original array

Answer key

Dynamic programming

For those of you who are not familiar with the idea of dynamic programming, you can step into this column, “Algorithmic ideas”, divide and conquer, dynamic programming, backtracking and greed

We can define the state dp[I] as the length of the longest increasing subsequence ending in nums[I], which must include nums[I], and initialize dp[I] to 1, since each element is a separate subsequence.

Define the state transition equation:

  • When we iteratenums[i], you need to compare the traversal at the same timenums[j]
  • ifnums[i] > nums[j].nums[i]I can add it to the sequencenums[j]And then finally, the length is zerodp[j] + 1Note:(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)} Copy the code
  • Time complexity: O(n^2)
  • Space complexity: O(n)

I’ve drawn a picture here just so you can understand it.

Greedy + binary search

Those of you who don’t know much about greed and binary search can take a look at these two columns of mine.

  • “Algorithmic thinking” divide-and-conquer, dynamic programming, backtracking, greed
  • Binary search algorithms from drinking table games

So if you want to think about greed, [1,2] is better than [1,4] because it has more potential. In other words, if we want to make the longest increasing subsequence, we want to make the ascending subsequence as slow as possible, so that it’s longer.

We can create an array of tails to hold the longest incrementing subsequence, and append it if the nums[I] currently traversed is greater than the last element of Tails (the maximum value in tails). Otherwise, we look for the first number of tails greater than nums[I] and replace it. Since the sequence is monotonically increasing, we can use binary search to reduce the time complexity to 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++) {  // If nums[I] is greater than the last element of the previous increment subsequence, append to it  if (nums[i] > tails[tails.length - 1]) {  tails.push(nums[i]);  } else {  // Otherwise, find the first element in the increasing subsequence that is greater than the current value and replace it with the current traversal element nums[I]  // Increasing sequence, can use binary search  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; }; Copy the code
  • Time complexity: O(nlogn)
  • Space complexity: O(n)

I’ve drawn a picture here just so you can understand it.

Note: the new array formed by this substitution may not be the correct array of solution 1, but it is the same length and does not affect our solution.

For example: [1,4,5,2,3,7,0]

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

We can see that the length of the tails is correct, but the value inside is incorrect, because the substitution in the last step breaks the nature of the subsequence.

Vue3 DOM Diff core algorithm

Having solved the problem of the longest increasing subsequence, let’s take a look at Vue3’s DOM Diff core algorithm.

I know you can’t wait, but if you don’t already know React and the DOM Diff algorithm of Vue2, you can follow this link to get a better understanding.

  • Vue. Js technology revealed

We came back and thought about the question: What is the purpose of the Diff algorithm?

“To reduce the performance overhead of DOM operations, we want to reuse DOM elements as much as possible. So we need to determine if any nodes need to be moved, how they should be moved, and find out which nodes need to be added or removed.“

Okay, let’s move on to the topic of this article, the Vue3 DOM Diff core algorithm.

The first thing we need to figure out is where the core algorithm is. The core algorithm is triggered when both the old and new children are multiple children.

The following code is Vue3’s DOM Diff core algorithm, I added the path in the source code, easy for you to find.

// 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 } Copy the code

The purpose of getSequence is to find the elements that do not need to be moved, so we can skip through the loop without doing anything else.

In fact, the core idea of this algorithm is the second solution of the longest increasing subsequence we talked about above, greedy + binary search method. That’s why I’m not going to rush into it, because if you read the LeetCode solution above, you already have the idea of Vue3’s DOM Diff core algorithm.

However, to understand the details of each line of code, you need to place it in the context of Vue3’s entire DOM Diff. It is also important to note that the getSequence method in the above code returns a different value from the one required in the LeetCode problem, which returns the index of the longest increasing subsequence. As mentioned earlier, there are some bugs in the greedy + binary search substitution approach, which can result in incorrect results. Vue3 solves this problem, so let’s take a look at how it works.

// packages/runtime-core/src/renderer.ts
function getSequence(arr: number[]) :number[] {
  const p = arr.slice() // copy an array p
  const result = [0]
  let i, j, u, v, c
 const len = arr.length  for (i = 0; i < len; i++) {  const arrI = arr[i]  // exclude the case that is equal to 0  if(arrI ! = =0) {  j = result[result.length - 1]  // Compare with the last item  if (arr[j] < arrI) {  p[i] = j // The last item corresponds to the index corresponding to p  result.push(i)  continue  }  // arrI is smaller than arr[j], use binary search to find and replace it  // define binary search interval  u = 0  v = result.length - 1  // Enable binary search  while (u < v) {  // Round to get the current position  c = ((u + v) / 2) | 0  if (arr[result[c]] < arrI) {  u = c + 1  } else {  v = c  }  }  // Compare => replace  if (arrI < arr[result[u]]) {  if (u > 0) {  p[i] = result[u - 1] // Correct result  }  result[u] = i // It is possible that the substitution will cause the result to be incorrect, and a new array p is required to record the correct result  }  }  }  u = result.length  v = result[u - 1]  // Overwrite result with p to find the final correct index  while (u-- > 0) {  result[u] = v  v = p[v]  }  return result } Copy the code

Vue3 solves the problem of greedy + binary look-and-replace by copying an array, storing the correct result, and then backtracking assignments.

This is the core algorithm part of Vue3 DOM Diff, welcome to the front canteen, guest officer you walk ~

❤️ Love triple punch

1. If you think the food and drinks in the canteen are ok with you, please give me a thumbs-up. Your thumbs-up is my biggest motivation.

2. Pay attention to the front canteen of public account, “eat every meal!”

3. Like, comment, forward === urge more!