Update: No code, multi – graph warning!

Declaration: non class algorithm slag to write the article, look carefully, there are any mistakes in the article please don’t hesitate to point out, more hope that the big guys can provide more information exchange, let me progress.

Significance of longest increasing subsequence in Virtual DOM algorithm

Those who know about IVI/Inferno should know that the core Diff algorithm of Virtual DOM in IVI/Inferno is applied to solve the longest increasing subsequence of a given sequence. The algorithm is from: En.wikipedia.org/wiki/Longes… . Of course, this article is not intended to explain the algorithm described in this link, but simply to solve the problem of finding * all * the longest increasing subsequences of a given sequence.

The implementation of the core Diff in IVI/Inferno is not explained here, but some information needs to be stated: the nodes in the old and new children have their own order, as shown below:

Ivi/Inferno would construct a Source array, and the values in the array stored the positions of nodes in the new children in the old children, as shown in the figure above. The Source array was [2, 3, 1, -1]. Then, if the node needs to move, the value in the Source array is treated as a sequence and its longest increasing subsequence is evaluated. For the sequence [2, 3, 1, -1], its longest increasing subsequence is [2, 3], but actually what we need is not the subsequence itself, but the position of the elements in the subsequence in the Source array, that is, [0, 1]. So what does [0, 1] do? It means that the nodes at position 0 and 1 in the new children do not need to be moved. In other words, only li-b nodes need to be moved in the figure above. This ensures that movement always has the least number of moves in the DOM operation, but how to prove that it is the least I don’t know yet, Because I tried many cases, SNabbdom didn’t move any more than IVi/Inferno. I’m just talking about the number of DOM moves, not the overall performance.

Solves the longest increasing subsequence of a given sequence

What is the longest increasing subsequence?

Within a given sequence of values, find a subsequence in which the elements of the subsequence increase in value and the length of the subsequence is as large as possible. Elements in the longest increasing subsequence are not necessarily continuous in the original sequence.

Without further ado, suppose the given sequence is as follows:

[0, 8, 4, 12, 2, 10]Copy the code

In fact, this is a problem that can be solved by using the idea of dynamic programming. The idea of dynamic programming is to decompose a big problem into many small sub-problems, and try to get the optimal solution of these sub-problems, the optimal solution of the sub-problem may be used in the larger problem, so as to obtain the optimal solution of the big problem through the optimal solution of the small problem. So what are the subproblems of a sequence? Very simply, sequences have length, so we can divide the numerator problem by the length of the sequence, as shown in the sequence above, it has 6 elements, that is, the length of the sequence is 6, so can we break down the sequence into shorter sequences? The longest increasing subsequence of the shorter sequence is solved first, and then the longest increasing subsequence of the original sequence is obtained. The answer is yes. If we take the last digit of the original sequence as a single sequence, then the sequence has only one element: [10]. Obviously, the length of the sequence with only one element is 1, and it cannot be shorter. So what is the longest increasing subsequence of the sequence [10]? Since there is only one element, there is no increment, but we need a convention: * When a sequence has only one element, we consider its increasing subsequence to be itself, so the longest increasing subsequence of the sequence [10] is also [10], with a length of 1.

Then we expand the subproblem, and now we take the last two numbers in the original sequence as a sequence, namely [2, 10]. For this sequence, we can regard it as composed of two sequences [2] and [10]. In addition, we observe the numbers in these two sequences and find that the condition 2 < 10 meets the requirement of increasing. Therefore, can we consider that the longest increasing subsequence of sequence [2, 10] is equal to the “sum” of the increasing subsequences of sequence [2] and sequence [10]? The answer is yes, and fortunately, we found in the previous step that the longest increasing subsequence of sequence [10] has a length of 1, and sequence [2] is also a sequence with only one element, so its longest increasing subsequence is itself, with a length of 1. Finally, we sum the two, The length of the longest increasing subsequence of sequence [2, 10] should be 1 + 1 = 2. In fact, we can see at a glance that the longest increasing subsequence of sequence [2, 10] is also [2, 10], which is of course 2 in length.

To avoid abstraction, we can draw the grid as shown below:

We assign a cell to each number in the original sequence and fill these cells with 1 as the initial value:

According to the previous analysis, we obtained the longest increasing subsequence lengths of the subproblem sequences [10] and [2, 10] as 1 and 2 respectively, so we modified the values in the corresponding grid as follows:

As shown above, the value of the cell corresponding to the number 10 in the original sequence is still 1 because the longest increasing subsequence of the sequence [10] has a length of 1. The value of the cell corresponding to the number 2 in the original sequence is 2, because the longest increasing subsequence of sequence [2, 10] has a length of 2. So you should see that the value in the cell represents the maximum length of the increasing subsequence that starts with the number of the cell.

Next, we continue to expand the subproblem by taking the last three numbers from the original sequence as the sequence of the subproblem: [12, 2, 10]. Similarly, for this sequence, we can regard it as composed of two sequences [12] and [2, 10]. But we find that the condition 12 < 2 is not true. What does that mean? In fact, this means that the maximum length of an increasing subsequence starting with the number 12 is equal to the maximum length of an increasing subsequence starting with the number 2. At this time, we do not need to modify the value of the cell corresponding to the number 12 in the original sequence, as shown below, the value of the cell is still 1:

But is that the end of it? Not yet. Let’s think about it for a moment. Our judgment condition is 12 < 2, which of course is not true, but let’s not forget that the number 2 in the sequence [12, 2, 10] has a number 10 after it. Of course it is. The simple reason is that if our sequence is [12, 2, 15], you will find that it is not enough to say that 12 is less than 2. Although 12 cannot have an increasing relationship with 2, 12 can have an increasing relationship with 15. Therefore, we conclude that when filling the value of a cell, we should compare the corresponding digits of the current cell one by one with the corresponding digits of all the cells following it, not only with the digits immediately following it. According to this idea, we continue to judge whether the condition 12 < 10 is valid or not, which is obviously not valid. Therefore, the value of the grid corresponding to the number 12 in the original sequence still does not need to be changed, it is still 1.

Then we expand the subproblem further, and now we extract the last four numbers from the original sequence as the sequence of the subproblem: [4, 12, 2, 10]. In the same way, we can regard this sequence as consisting of sequence [4] and sequence [12, 2, 10], and since condition 4 < 12 is true, So we can think of the length of the longest increasing subsequence of the sequence as equal to the sum of the length of the longest increasing subsequence of the sequence [4] and the length of the longest increasing subsequence starting with the number 12, which is obviously 1, The maximum length of an increasing subsequence starting with the number 12 is actually the value of the cell corresponding to the number 12, which we found to be 1 in the previous step, so we change the cell corresponding to the number 4 to 1 + 1 = 2:

Of course, this is not the end of the story. We also need to determine whether conditions 4 < 2 and 4 < 10 are true, for reasons we have already analyzed. Condition 4 < 2 is not true, so we don’t do anything, but condition 4 < 10 is true, we find the value of the cell corresponding to the number 10:1, add this value by 1 and then the value is 2, which is the same as the value of the cell corresponding to the number 4 now, so we don’t need to change it.

So far, I don’t know if you found any rules? How do you compute the values in a cell? It’s actually quite simple. The rules are:

1. Compare the number A corresponding to the cell to be filled with the number B corresponding to all the cells behind it. If the condition a < B is true, add 1 to the value of the cell corresponding to the number B, and fill the result into the cell corresponding to the number A. 2. Only if the calculated value is greater than the value in the corresponding cell of the number A, the value in that cell needs to be updated.

With these two rules, it is easy to fill in the remaining cells. Next, we fill in the values of the cells corresponding to the number 8 in the original sequence. According to the above analysis, we need to judge four conditions:

2, 8 < 12 3, 8 < 2 4, 8 < 10

  • It’s obvious that the condition 8 < 4 is not true, so do nothing;
  • If 8 < 12 is valid, take out the value of 12 in the corresponding grid: 1, add 1 to this value, and the value is 2, which is greater than the current value of the grid corresponding to the number 8, so the value of the grid is updated as 2;
  • If 8 is less than 2, we don’t do anything;
  • If 8 is less than 10, if you take the number 10 and add it to the value 1, you get 2, which is no greater than 8, so you don’t need to do anything.

Finally, we fill the corresponding grid for the number 8 with a value of 2:

Now, the remaining value of the grid corresponding to the number 0 in the original sequence has not been updated. According to the previous thinking, we need to determine the conditions as follows:

1, 0 < 8 2, 0 < 4 3, 0 < 12 4, 0 < 2 5, 0 < 10

If 0 < 8 is true, take out the value of the number 8 in the corresponding grid: 2, add 1 to this value to get the value of 3, greater than the current value of the number 0 corresponding to the grid, so update the value of the grid to be 3. Repeat the steps described above, and the result is that the number 0 in the original sequence corresponds to the cell value 3:

As shown in the figure above, now that the values of all the cells have been updated, all we need to do is find the longest increasing subsequence of the entire sequence based on these values. So how do you look? In fact, the maximum value in these cells represents the maximum length of the increasing subsequence of the entire sequence. In the figure above, the value of the number 0 corresponding to the cell is 3, which is the maximum value, so the longest increasing subsequence of the original sequence must start with the number 0:

Then you need to look for the value of 2 in all the cells following the value of 3. You find that there are three cells that satisfy the condition: the cells corresponding to the numbers 8, 4, and 2 in the original sequence. Suppose you picked the number 4:

Similarly, you need to continue to look for the number 1 in all the cells following the number 4. You find that there are two cells that satisfy the condition, namely the cells corresponding to the numbers 12 and 10 in the original sequence. Let’s pick a value at random again, assuming we choose the number 10:

Since the smallest value in the grid is the number 1, we don’t need to look any further. Looking at the figure above, we can see that the three numbers we selected are actually the longest increasing subsequence of the original sequence: [0, 4, 10]. Of course, as you’ve probably already discovered, there’s more than one answer. For example:

The point is, there are three squares with a value of 2, so you have three options:

  • [0, 8]
  • [0, 4)
  • [0, 2)

When you select [0, 8], you still have two options, because there are two boxes of 1 behind the number 8:

  • [0, 8, 12]
  • [0, 8, 10]

Similarly, if you choose [0, 4], there are two options:

  • [0, 4, 12]
  • [0, 4, 10]

But when you choose [0, 2], you have only one choice:

– [0, 2, 10]

This is because there is only one cell behind the number 2 that has the value 1, the cell behind the number 10, so you have only one choice. In other words, when you select [0, 2], you can’t select the number 12 even though the corresponding cell has the value of 1, because the number 12 is in front of the corresponding cell of the number 2.

So, that’s how we get all the longest increasing subsequences of a given sequence.

The code can be seen here:

lis – CodeSandboxcodesandbox.io

This is an implementation of calculating a longest increasing subsequence using the idea above. If you want to solve all of them, I will post the article and update it later.