preface
There are many related articles about VUe3 diff. Today, we will not talk about the specific diff process, but mainly solve the longest increasing subseries mainly used in vue3 DIff. Vue3 DIff mainly uses the longest increasing subseries to optimize the node movement
Longest increasing subseries (find the length)
Leetcode’s 300 longest increasing subseries title describes it as follows:
Given an integer array nums, find the length of the longest strictly increasing subsequence. Example 1: input: nums = [10,9,2,5,3,7,101,18] output: 4 explanation: the longest increasing subsequence is [2,3,7,101], so length is 4.
Note: the length of the longest increasing subseries for which this problem is solved; Vue3 Diff solves for the corresponding index of the longest increasing subseries
Code implementation
There are two main ways to calculate the length of the longest increasing subseries. One is dynamic programming, which is easy to understand, but time complexity is high. The second is greedy + dichotomy, the time complexity is O(N logn)(N: array length).
1. Dynamic planning
/ * * *@param {number[]} nums
* @return {number}* /
// Time complexity O(N^2) : double layer traversal
// Space complexity O(N) : space required by dp tables
Dp [I] = math.max (dp[I], dp[j] + 1) (j < I && nums[I] > nums[j])
Dp [I] = math. Max (dp[0,... i-1]) + 1
var lengthOfLIS = function(nums) {
var len = nums.length
if (len == 0) {
return 0;
}
var dp = Array(len).fill(1)
var max = 1
// dp[I]: the longest increasing subseries ending in I
for (var i = 1; i < len; i++) {
// Iterate over the elements before I to find subseries that can be added to ending with I
for (var j = i-1; j >= 0; j--) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1)
}
}
max = Math.max(max, dp[i])
}
return max
};
Copy the code2. Greed + dichotomy
// Time complexity O(NlogN) : O(N) is required to traverse the NUMS list and O(logN) is required for each NUMs [I] dichotomy.
// The space complexity O(N) : tails list takes up linear size extra space
The value of tails[k] represents the value of the tail element of the current (length k+1) subsequence
// The greedy method ensures that the subseries grow slowest. Since the arranged series is monotonically increasing, the dichotomy method can be used to find the current insertion position of the element, which is more efficient
var lengthOfLIS = function(nums) {
// The increasing subseries array of the current subseries
const tails = Array(nums.length)
let res = 0;
for(let i = 0; i < nums.length; i++) {
// tails are initially empty and can be added directly
// If nums[I] is larger than tails, add nums[I] to tails;
if (res === 0 || nums[i] > tails[res-1]) {
tails[res++] = nums[i]
} else {
// Otherwise, find the first position in tails that is greater than nums[I] and replace it with nums[I]
// Binary insertion: binary traversal of tails, find nums[I] position in tails
let l = 0, r = res;
while(l < r) {
let mid = (l+r) >> 1
if (tails[mid] < nums[i]) {
l = mid + 1
} else {
r = mid
}
}
// Replace the original value with nums[I]
tails[l] = nums[i]
}
}
return res
}
Copy the codeThere is a problem
Because the greedy algorithm takes the current local optimal solution every time, the longest increasing subseries that can be caused is not the correct order in the original series. For example: [2, 5, 3, 1], the result is that length 2 is correct, but the actual longest increasing subseries is [1, 3], obviously this is not correct, in the original series 1 after 3
Longest increasing subseries in vue3 DIff (corresponding index)
In the index position of the new node array in the old node array, increasing in the position array can ensure the order of the relative position in the old array, so there is no need to move. Therefore, the longest increasing subsequence can ensure the minimum number of moves, or can be understood as: The longest common subfamily of the old and new node arrays. Removing the longest common subfamily of other nodes from the old node array requires processing (move, delete).
Vue3 requires not the length of the subsequence, nor the final array of subsequences, but the index of the subsequence
Code implementation
// arr: array of positions;
// Returns an incrementing subseries of the position array
function getSequence(arr){
const p = arr.slice() P [I] is the last value recorded by result before arr[I] is updated
const result = [0]
let i, j, u, v, c
const len = arr.length
for (i = 0; i < len; i++) {
const arrI = arr[i]
// Iterate over the position array
// exclude the case that is equal to 0
if(arrI ! = =0) {
j = result[result.length - 1]
// (1) arrI is larger than arr[j]
if (arr[j] < arrI) {
p[i] = j // The last item corresponds to the index corresponding to p, saving the index of the last value of the last longest increment subseries
result.push(i) // result stores the set of indexes for the smallest trailing value of an increasing subsequence of length I
// (minimum trailing value: to get the longest increasing subseries, the subseries should grow as slowly as possible, so the subseries trailing value should be the smallest)
continue
}
// (2) arrI <= arr[j]; The cycle stops when u and v are equal
// define binary search interval [u, v]
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, the current subseries from scratch find the first arrI greater than the current value, and replace
if (arrI < arr[result[u]]) {
if (u > 0) {
p[i] = result[u - 1] P [I] = j
}
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}}}// The previous logic is similar to leetcode 300 to find the maximum length of the series
// The main fix below is that the longest increasing subseries possible due to greedy algorithms are not in the correct order in the original series
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** here’s the thing ~~ **
How does VUe3 correct the order disorder of the longest increasing subseries caused by greedy algorithm
In VUe3 (the code above), this is mainly implemented by:
- Depends on storing the previous index of the current element’s corresponding index in the current increment subseries by traversing the order each time the element is traversed
p[i] = j
/ /... ..... omitted
if (u > 0) {
p[i] = result[u - 1]
}
result[u] = i
Copy the codeThe above logic is equivalent to p[I] = result[U-1] ==> P [arrIndex] = result[resultIndex-1] (where resultIndex: arR current traversal element insert position in increment subseries)
- After all the elements are finally traversed, the current value of the final increment subseries is searched according to the corresponding pre-index saved previously
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]
}
Copy the codeResult [u-1] = p[result[u]] ==> result[resultindex-1] = P [result[resultIndex]] = P [result[arrIndex] (result[resultIndex]: index of the current traversal element in arR)
// resultIndex: The insertion position of the current traversal element in the arR in the incrementing subseries
// result[resultIndex]: index of the current traversal element in arR
// result[resultindex-1]: indicates the location of the last element smaller than the current element
p[i] = result[u-1] ==> p[arrIndex] = result[resultIndex-1]
result[resultIndex-1] = p[result[resultIndex]] = p[arrIndexCopy the codeAnalysis of the
Assume that the following are before and after the child node is updated:prev: [a, b, c, d, e, f]
next: [c, f, d, b]0.1.2.3] (Element index in position array) Position array: [2.5.3.1] (Position of elements in next array in prev array)Copy the codeTraversal ARR: [2, 5, 3, 1], corresponding results of each traversal operation are as follows:
| Arr index (index) | arr[index] | Increasing subseries | Index corresponding to increment subseries (result) | Array of precursor nodes (P) |
|---|---|---|---|---|
| 0 | 2 | [2] | [0] | [2, 5, 3, 1) |
| 1 | 5 | [2, 5] | [0, 1] | (2, 0, 3, 1) |
| 2 | 3 | [2, 3] | [0, 2) | (2, 0, 0, 1] |
| 3 | 1 | [1, 3] | (3, 2) | (2, 0, 0, 1] |
Arr: [2, 5, 3, 1] The index corresponding to the increasing subseries is result: [0, 2], and the index corresponding to the precursor node is P: [2, 0, 0, 1].
Specific analysis is as follows:arr: [2.5.3.1], traversal arr: when index =0When arr [0] = 2; p[0] = 2, copy the arr [0]; Incremental subseries: [2]; Index array result = [0] when index index=1When arr [1] = 5; Due to the5 > 2, increasing subseries: [2.5]; Index array result = [0.1]; ResultIndex indicates that the insertion position is1So p [1[index] = p[index] = p[1] = result[resultIndex - 1] = result[1-1]=result[0] = 0; When the index index =2When arr [2] = 3; Due to the3 > 2 && 3 < 5, increasing subseries: [2.3]; Index array result = [0.2]; ResultIndex indicates that the insertion position is1So p [2[index] = p[index] = p[2] = result[resultIndex - 1] = result[1-1]=result[0] = 0; When the index index =3When arr [3] = 1; Incremental subseries: [1.3]; result = [3.2]; ResultIndex indicates that the insertion position is0That is less than1, p[index] = p[3] = result[resultIndex - 1, so p []3] is the initial value;Copy the codereference
Leetcode antithesis www.cnblogs.com/eret9616/p/… Juejin. Cn/post / 693724…