The core DIFF algorithm of VUE2 is a two-end comparison algorithm

The vuE3 core Diff algorithm uses the longest increasing subsequence algorithm without the head and tail

This paper mainly analyzes the core DIff algorithm of VUE3

Longest increasing subsequence

This is a classic algorithm problem.

In computer science, the longest increasing subsequence problem refers to finding a subsequence in a given numerical sequence, making the number of elements in the subsequence increase successively, and the length of the subsequence as large as possible. The elements in the longest increasing subsequence are not necessarily continuous in the original sequence. The algorithm for solving the longest increasing subsequence problem requires a minimum time complexity of O(n log n), where n represents the size of the input sequence.

Most of the solutions use the idea of dynamic programming, the time complexity of the algorithm is O(n2), and vue.js internal use is the “greedy + binary search” algorithm, the time complexity of the greedy algorithm is O(n), the time complexity of binary search is O(logn), so its total time complexity is O(nlogn).

example

For the following original sequence 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15, the longest increasing subsequence is 0, 2, 6, 9, 11, 15. It is worth noting that the longest increasing subsequence of the original sequence is not necessarily unique. For the original sequence, there are actually three longest increasing subsequences 0, 4, 6, 9, 11, 15 0, 4, 6, 9, 13, 15 0, 2, 6, 9, 13, 15Copy the code

The algorithm outlined below uses array and binary search algorithms to effectively solve the longest increasing subsequence problem. It processes the sequence elements in turn, holding the longest increment subsequence currently found, for example: [X[0], X[1]]. After processing X[I], the algorithm stores the values in two arrays:

  • M[j] — Stores the index K of X [k] with the smallest value, so that subsequences of length j ending in X [k] are increased in the range k≤ I. Note: j ≤ (I +1), because j≥1 indicates the length of the increasing subsequence, and k≥0 indicates the index at which it terminates.
  • P[k] – Stores the previous index of X [k] in the longest increasing subsequence ending in X [k].

In addition, the algorithm stores a variable L, which represents the length of the longest incrementing subsequence found so far. The following algorithm uses zero-based numbering. For clarity, M is filled with M [0], whereas M [0] is not used, so M [j] corresponds to a subsequence of length j. Actual implementations can skip M [0] and adjust the index accordingly.

Note that at any time in the algorithm, the sequence

X[M[1]], X[M[2]], … , X[M[L]] is increasing. Because, if the subsequence of length j≥2 ends with X [M [j]], then the subsequence of length j-1 ends with a smaller value: that is, the subsequence [j]] ending with X [P [M]. So, we can use binary search to complete the search in order log n time.

The pseudocode is as follows:

P = array of length N M = array of length N + 1 L = 0 for i in range 0 to N-1: Binary search for the largest positive j ≤ L // such that X[M[j]] <= X[I] lo = 1 hi = L while lo ≤ hi: mid = ceil((lo+hi)/2) if X[M[mid]] < X[i]: lo = mid+1 else: hi = mid-1 // After searching, lo is 1 greater than the // length of the longest prefix of X[i] newL = lo // The predecessor of X[i] is the last index of // the subsequence of length newL-1 P[i] = M[newL-1] M[newL] = i if newL > L: // If we found a subsequence longer than any we've // found yet, update L L = newL // Reconstruct the longest increasing subsequence S = array of length L k = M[L] for i in range L-1 to  0: S[i] = X[k] k = P[k] return SCopy the code

Vue3 source code implementation

The main idea is to iterate the array, and then solve the longest increasing subsequence when the length is I. When the I element is greater than the i-1 element, add I element and update the oldest sequence. Otherwise, look forward until you find an element smaller than I, then insert after that element and update the corresponding longest increasing subsequence.

The main purpose of this approach is to make the difference of the increasing sequence as small as possible, so that you can get a longer increasing subsequence, which is the idea of a greedy algorithm.

function getSequence (arr) { 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 Update the value of the result while < v (u) = {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], arr[result[u]]) {if (u > 0) {p[I] = result[u-1]} result[u] = I}} u = result. While (u-- > 0) {result[u] = v v = p[v]} return result}Copy the code