In the intensive reading of The DOM Diff Principle, we mentioned that Vue used a greedy + dichotomy algorithm to find the longest ascending subsequence, but did not go into the principle of this algorithm, so a special chapter was opened for detailed explanation.
In addition, as an algorithm, the longest ascending subsequence is very classic, practical in the industry at the same time, and a certain degree of difficulty, so I hope you must master.
Intensive reading
What is the longest ascending subsequence? Is to find the longest continuously ascending portion of an array, as shown below:
If the sequence itself is ascending, return itself; If no part of the sequence is ascending, return any number. As you can see, even though 3, 7, and 22 are also going up, because 22 is not going to be the longest after that, it’s not going to be as long as 3, 7, 8, 9, 11, 12, so it’s not that easy to find.
In the concrete DOM diff scenario, to move as little DOM as possible, we need to keep the longest ascending suborder intact and move only other elements. Why is that? Because the longest ascending subsequence itself is relatively ordered, the answer will come as soon as all the other elements have moved. Again, assuming that the original DOM is in such an ascending order (of course, it should be 1, 2, 3, 4 consecutive subscripts, but for the algorithm does not matter whether consecutive intervals, just incrementing) :
If the longest ascending suborder remains unchanged, it only needs to move three times to restore:
Any other way of moving is no less than three steps, because we’re keeping the parts that are already in order as still as possible.
So the question is, how do I find this longest ascending subsequence? It is easy to think of solutions are: violence, dynamic programming.
Violent solution
Time complexity: O(2 2N)
We will eventually generate a maximum sequence length, so let’s simulate the process of generating this subsequence, only it will be violent.
Violence simulation generates a subsequence how do you do that? This is to try to pick or not pick the current number every time from [0,n], as long as the last number is larger than the previous one. Because the array is n in length, each number can be selected or not selected, that is, each number has two choices, so a maximum of 2 or 2n results will be generated, the longest number from which is the answer:
If you do this stupid thing, you’re going to get the longest one, and you’re just going to keep track of the longest one.
This method is not recommended because it is too inefficient, but this kind of violent thinking should be mastered.
Dynamic programming
Time complexity: O(n²)
If we consider this problem in a dynamic programming way, then DP(I) is defined as a rule of thumb: the length of the longest sequence at the end of the ith string.
The rule of thumb here is that the dynamic gauge usually returns the answer, the string problem usually ends in the ith string, so just scan it. Moreover, the oldest sequence has repeated subproblems, that is, the answer operation of the ith contains the previous calculations. In order to avoid repeated calculations, dynamic programming is used.
So the result of term I is related to the previous results, as shown in the figure for ease of understanding:
So let’s say we look at the number 8, which is DP of 4. Because of the preceding DP(0), DP(1)… So DP of 3, we’ve already figured it out, so let’s see how DP of 4 relates to this.
If nums[I] is greater than nums[I -1], then DP(I) is equal to DP(I -1) + 1. If 8 is 3, less than 4, then the answer is 1, because it’s not going to go up, so you’re going to have to go up with 3.
But if you think about it, this subsequence doesn’t have to be continuous, because if you combine the i-th term with the i-2 term and the i-3 term, maybe it’s longer than if you combine it with the I-1 term, right? We can take a counter example:
Obviously, 1, 2, 3, 4 is the longest ascending subsequence, so if you just look at 5, 4, you can only get 4.
Because of the discontinuity, we need to compare the ith term with the j term in turn, where j=[0,i-1]. Only by comparing with all the preceding terms can we be assured that the result found in the ith term is indeed the longest:
So what about the time? In the dynamic programming solution, we first loop from 0 to n, and then do an extra loop [0, I -1] for each I, so the number of calculations is 1 + 2 +… Plus n is n times n plus 1 over 2, minus the constants, order n squared.
Greed + two
Time complexity: O(nlogn)
To be honest, it’s generally good to think of dynamic programming solutions, but it’s very difficult to think of further optimizing time complexity. If you haven’t done this problem before and want to challenge yourself, stop reading here.
Good, published the answer, to tell the truth, this method is not like normal human thinking, with a great leap of thinking, so I can not give the process of thinking derivation, directly say the conclusion: greedy + dichotomy.
If we have to say how we think about it, we can think about it in terms of time complexity, in general n ^ 2 time complexity optimization will become nlogn, and a binary search is logn, so try to combine it.
If the value is greater than all the values in the stack, then the stack is pushed, otherwise the minimum value is replaced, and the final stack length is the answer:
First, explain the time complexity. Because of operation reasons, the numbers stored in the stack are all in ascending order, so we can use dichotomy comparison and insertion. The complexity is logn, and the outer N loop, so the overall time complexity is O(nlogn). Another problem with this scheme is that the length of the answer is correct, but the stack array may be wrong. If you want to fully understand that, you have to fully understand how the algorithm works, how you can improve it to get the right subsequence.
Now I want to explain the principle. It’s not complicated to think about at the beginning. You can watch it over a cup of tea. The first intuition is that in order to make the longest ascending subsequence as long as possible, we want to make sure that the number we pick grows as slowly as possible, and vice versa as fast as possible. For example, if we pick the numbers 0, 1, 2, 3, 4, then the greed is more stable, because it’s growing as slowly as possible, and we can put in the probability that we encounter later. But if we pick 0, 1, 100 then we should panic when we get to 100, because if we go up to 100, don’t we give up all the numbers below 100? At this time, asking for 100 May not be a wise choice. If you lose it, you may have more space in the future. This is actually greedy thinking, the so-called local optimal solution is the global optimal solution.
But that’s not the whole idea, so let’s just keep thinking, if we get to 0, 1, 100, if we run out of numbers, we can still put 100 in, because 100 is a big number, but it’s the last one, so it’s still useful. So if you’re going left to right, you’re going to have to put in larger numbers, but the point is, what if you keep going down, and you get a number less than 100?
At this point, if you can’t make a mental leap, analysis stops there. You might think, well, if you have a 5, obviously you have to squeeze out the 100, because 0, 1, 5 and 0, 1, 100 all have 3 lengths, but 0, 1, 5 has more potential than 0, 1, 100, so the same length, one has more potential, so you have to replace it! That’s the right idea, but if you have 3, 7, 11, 15, and you have 9, what do you do? If 3, 7, and 9 have the best potential for potential, but you sacrifice the length from 4 to 3, you don’t know if there’s nothing bigger than 9, and if there’s no more, it’s not as good as the length from 4; If you keep 3, 7, 11, 15 for the sake of length, you’ll be a bit shortsighted if 10, 12, 13, 14 follow.
So the question is how to deal with the next number so as not to be short-sighted in the future, and to “grasp the happiness of stability”. The answer is “if the value is greater than all of the values on the stack, then replace the smallest value greater than it”. This reflects the leap thinking, the core of realizing both the present and the future is: sacrificing the correctness of the stack content and ensuring the correct total length, each step can seize the best opportunities in the future. Only if the total length is correct, the longest sequence can be guaranteed. As for sacrificing the correctness of the stack content, it does pay a small price, but in exchange for the possibility of the future, at least the length can be correct. If the content is correct, we can add some auxiliary means to solve this problem, which will be discussed later. All in all, the sacrifice is well worth it. Here’s how sacrificing stack content correctness can lead to length correctness and future opportunities.
Let’s take an extreme example: 3, 7, 11, 15, 9, 11, 12. If you stick to the 3, 7, 11, 15 you have a length of 4, but if you drop 11, 15 and connect 3, 7, 9, 11, 12, you have a better length. If the greedy algorithm is used, we will first encounter 3, 7, 11, and 15 in sequence. Since each number is larger than the previous one, there is nothing to think about, so we just add it to the stack:
When we meet 9, it is wonderful. At this time, 9 is not the biggest. In order to seize the stable happiness, we simply replace 11 which is a little bigger than 9.
First of all, the length of the array doesn’t change, because the substitution doesn’t change the length of the array, so if there’s no value after 9, we’re still good, and the output length 4 is still the optimal answer. Let’s move on, and when we get to 11, we’ll replace 15, which is slightly larger:
At this point, we replaced the last number, and found that 3, 7, 9, and 11 were finally a reasonable order with the same length as 3, 7, 11, and 15, but with more potential. Then, 12 was naturally put at the end, and we got the final answer: 5.
I’m not really getting into the essence of the algorithm here, but let’s go back to 3, 7, 9, 15, and figure out why 9 can replace 11.
If 9 is followed by a large 99, then the next 99 is appended directly to it:
At this point we have 3, 7, 9, 15, 99, but if you look closely, in the original sequence, 9 comes after 15, because we inserted 9 in front of 15, so it’s obviously not the right answer, but it’s the right length, Because that’s the same answer as choosing 3, 7, 11, 15, 99! Why is that understandable? Because as long as we don’t get to the last number, the queue in our mind is still the original queue.
That is, as long as the stack is not replaced, the new insert value only ever have a placeholder effect, the purpose is to let the value of the new insert, but if you really don’t have the new value to insert, that although the content of the stack is wrong, but at least the length is right, because in the replacement of my time is not 9, it is just a placeholder, behind the value is 11. So no matter how you do it, the substitution is invalid unless you replace the last one. Let’s take another example:
So 1, 2, 3, 4 is not going to replace 7, 8, 9, 10, 11, so it’s going to be 1, 2, 3, 4, 11, but it doesn’t matter, as long as it’s not, it’s going to be 7, 8, 9, 10, 11, which we didn’t write down, but just looking at the length, There’s no difference between the two, so it’s okay. What if one, two, three, four, five, six? Let’s see what happens when we can replace it:
So, by the time we get to 5, the sequence is in the right order, because 1, 2, 3, 4, 5 is already fully capable of replacing 7, 8, 9, 10, 11, and it has more potential than that, and we have found the optimal local solution. So 1, 2, 3, 4, 11 here, 1, 2, 3, 4 is like an undercover, and while 11 is still there, he’s going to suck it up and call 7, 8, 9, 10, 11 boss, and so on, but when 5 comes in, One, two, three, four, five can go up against seven, eight, nine, ten, eleven, because it’s already more powerful than the old one.
The seemingly insignificant substitution in front of us, in fact, is to keep looking for the best possible solution in the future, until the day of the day, if not, it is good to be a little brother, the length is right; If it does, the maximum length is updated, so this greed can be both correct and efficient.
And finally, how do you find the right sequence while still finding the answer?
Find the correct sequence
Finding the correct sequence is not easy, so let’s look at the following case:
At the end of the greedy algorithm, the total length is right, but obviously the order is still wrong. To facilitate calculation, we convert to subscript when storing:
And it’s stored in a two-dimensional array, so the numbers that are replaced can be retained. When we’re done, we start at the last bit and move forward. Once we find a value that isn’t monotonically decreasing, we move up the array to the first node.
Thus, in the example above, the final order subscript is [0, 1, 2, 3, 4, 5, 9], and the corresponding number is [10, 20, 30, 40, 50, 60, 61], and this number is the most potentially first-order sequence.
conclusion
So how much did it cost Vue to finally greedy calculate the longest ascending subsequence? This is the relationship between O(n) and O(nlogn).
It can be seen that the increasing trend of O(nlogn) time complexity is barely acceptable, especially in engineering scenarios, when the number of children of a parent node is not too many, it will not occupy too much analysis time, and the benefit is the minimum DOM movement. It is a perfect combination of algorithm and engineering practice.
Close read DOM Diff’s Longest Ascending subsequence · Issue #310 · dT-fe /weekly
If you’d like to participate in the discussion, pleaseClick here to, with a new theme every week, released on weekends or Mondays. Front end Intensive Reading – Helps you filter the right content.
Pay attention to the front end of intensive reading wechat public account
Copyright Notice: Freely reproduced – Non-commercial – Non-derivative – Remain signed (Creative Commons 3.0 License)