DOMdiff作为一个工程问题，需要一定的算法思维，所以在面试场景中经常出现。毕竟这是工程领域很少出现的算法问题。不管是面试还是深入学习，都需要了解这道题，所以我们会用前端精读的一章来理清这道题。精读Domdiff是现在所有框架都必须做的事情。这背后的原因是Jquery时代的面向操作的流程已经转变为数据驱动的视图。为什么Jquery时代不需要Domdiff？因为Domdiff是交给业务的，所以我们调用.append或.move等Dom操作函数来显式声明如何做Domdiff。这种方案是最高效的，因为只有业务才知道如何移动Dom。但这样的问题也很明显，就是商家心态包袱太重。对于复杂的系统，需要做Domdiff的地方太多了。不仅写起来麻烦，而且状态交错时，面向过程的手工Domdiff容易出现状态遗漏。导致边界错误，即使不写bug，代码的可维护性也肯定不好。该解决方案是数据驱动的。我们只需要关注数据是如何映射到UI上的。这样无论业务逻辑多么复杂，我们只需要解决局部状态的映射即可。这大大降低了复杂系统的维护复杂度。以前，一个老手写的Thelogic，现在新手也能搞定，这是一个很了不起的变化。但有优点也有缺点。在这背后，必须将Domdiff交给框架，所以Domdiff能否高效完成，是衡量一个数据驱动框架能否应用于生产环境的重要指标。接下来，让我们看一下Domdiff。diff是怎么做到的。理想的Domdiff如图所示。理想的Domdiff自然地重用所有可以重用而不会泄漏的东西。插入或删除只有在遇到新的添加或删除时才会执行。这种操作最接近我们在JQuery时代手写Domdiff的表现。可惜程序无法猜到你的想法，想要准确复用就得付出高昂的代价：时间复杂度为O(n3)的diff算法，这显然是不能接受的，所以理想的Domdiff算法不能使用。关于O(n3)的起源。由于左树中的任意一个节点都可能出现在右树中，因此需要在深度遍历左树的同时深度遍历右树，找到各个节点的对应关系。这里的时间复杂度是O(n2)，之后需要对树的每个节点进行增删改查。这个过程可以简单理解为加了一层遍历循环，所以乘以n。简化后的Domdiff如图所示，仅通过层比较就可以将时间复杂度降低到O(n)。逐层比较不是广度遍历。其实就是判断一个节点的子元素之间的diff，跨父节点的兄弟节点不需要比较。这样确实效率很高，但是代价就是判断有点傻，比如ac明明是移动操作，却误判为delete+add。好在实际业务场景中很少出现跨DOM复用，所以这种笨拙的情况发生的频率其实很低。这时候，学术思想不要过于严谨。毕竟，框架是针对实际项目的。对于实际项目中很少出现的场景，算法可以忽略。以下是同层diff可能出现的三种情况。很简单，看图就知道了：那么同层比较是如何做到O(n)时间复杂度的呢？下面来看具体框架的思路。Vue的DomdiffVue的Domdiff一共有5步。下面结合下图来看一下前三步：如图所示，第一步和第二步分别从头尾向中间逼近，尽量跳过首位相同的元素，因为我们的目标是尽量保证不会发生dom位移。该算法一般使用双指针。如果前两步完成后，发现老树的指针重叠了，而新树的指针没有重叠，什么意思呢？说明新树剩下的就是要添加的新节点，可以批量插入。很简单吧？反过来呢？如下图：第一步和第二步完成后，发现新树的指针重叠了，但是老树的指针没有重叠。这是什么意思？意思是旧树的其余部分在新树中不存在，批量删除即可。当然，如果指针在1、2、3、4步骤完成后还没有处理完，那么就会进入一个小算法时间，我们需要在O(n)时间复杂度内处理剩下的节点。熟悉算法的同学应该能很快反应过来，一个数组做一些检测操作的时候，时间复杂度必须控制在O(n)，必须用一个Map空间来改变时间，其实就是案件。具体看下图方法：如图，1、2、3、4步完成后，Old和New都剩下，所以第5步分为三个小步骤：??遍历Old创建一个Map，这个是时变空间消耗的，它记录了每个旧节点的索引下标，后面在New中很容易查到。遍历New，顺便用上面的Map记录下标，同时删除Old中不存在的描述，直接删除。在不存在的位置加0，我们得到一个数组如e:4d:3c:2h:0，下标0加，非零移动，可以转化为insert分批操作。优化的最后一步也很关键。我们不想看到差异就随便移动。为了获得最佳性能，我们必须确保移动次数尽可能少。那么我们如何才能尽可能少地移动呢？假设我们随意移动，如下图所示：但实际上最优的移动方式如下：为什么？因为在移动的时候，其他元素的位置也在相对变化。可以在满足B的效果的同时达到A的效果。也就是说，找到那些相对位置是有序的元素，保持不变，这样那些位置就明显错了。元素运动是最佳的。什么是相对顺序？ace三个字母按照Old的原始顺序abcde进行相对排序。我们只要把bd去掉，这三个字母的位置自然就正确了。所以我们只需要在New数组中找到最长的连续子串即可。具体怎么找可以看成一个算法小问题。由于每个元素的实际下标是已知的，比如在这个例子中，下标是这样的：[b:1,d:3,a:0,c:2,e:4]从肉眼看，连续自增子串包括bd和ace，由于ace较长，所以选择后者。在程序中做，可以用动态规划，令dp(i)为以第i个字符串结尾的最长连续子串的长度，一个O(n)循环就够了。//dp(i)=num[i]>num[i-1]?dp(i-1)+1:1React的Domdiff假设了这样一种情况，我们把a移动到c，那么frameworkfromthefinal如何以最快的方式找到这个动机呢？React采用只右移的策略，即当元素的位置发生变化时，只会向右移动，然后再向右移动，其他位置依次排列。我们看图说明一下：遍历OldstoresMap和Vue一样，接下来就是第二步遍历New，b下标由原来的1变成0，需要向左移动，但是我们并没有向左移动，我们只是向右移动，因为右移全部完成后，左移就相当于被自动移除了（前面的元素向右移动后，自然会被推到最前面，实现左移的效果）。同理，c的下标从2变成了1，需要向左移动，但是我们继续移动。a的下标从0变成了2，终于可以向右移动了！如果后面的d和e下标没有变化，则不需要移动它们。整体来看，我们可以发现b和c自然左移了，因为前面的a被拿走了。这是用一次右移代替两次左移的高效操作。同时，我们发现这确实找到了我们一开始提到的最优位移策略。这个算法真的那么聪明吗？显然不是，这个算法只是对错而已。有一种算法使用右移而不是左移，也有一种算法使用左移而不是右移。既然你选择了右移而不是左移，那么你肯定失去了左移而不是右移的效率。什么时候使用左移而不是右移最有效？就是把数组的最后一个位置移到第一个位置的场景：很明显，只需要向左移动一步，然后向右移动n-1步，也就是这个中的4步例子。我们看一下右移算法的图：先找到e，位置从4变成0，但是我们不能左移！所以我只能原地不动，悲剧就开始了。虽然算法不再是最优的，但该做的还是要做的。其实还有一个lastIndex的概念，之前没有提到，因为e已经在4的位置了，所以a从0移动到1是不够的，这时候a应该从0移动到5。方法是记录lastIndex=max(oldIndex,newIndex)=>lastIndex=max(4,0)，下次移动到lastIndex+1，也就是5：发现a从0变成了5（注意此时考虑lastIndex因子），所以右移。同样，b、c、d也是一样的。我们最终发现发生了4次右移，e也由于4次自然左移而到达了第一位，符合预期。所以这是一个有利有弊的算法。添加和删??除比较简单，类似于Vue。PS：如果更新了最新版本的ReactDomdiff算法，请在评论区指出，因为这个算法好像没有Vue效率高。总结domdiffsummary有几个考虑：完全比较O(n3)是不可接受的，所以降级为O(n)方案进行同级比较。为什么降级有效？因为跨级很少发生，所以可以忽略。同一个关卡并不简单，难的是如何高效的移动，也就是用最少的步数完成移动。Vue为了尽量不移动，先左右捏一下，跳过没有变化的，然后找最长的连续子串保持不动，移动其他元素。React仅使用右移方案，在大多数从左移到右的业务场景中，它获得了更好的性能。讨论地址为：Jingdu《DOM diff 原理详解》·Issue#308·dt-fe/weekly想参与讨论的请戳这里，每周都有新话题，周末或周一发布。前端精读——帮你过滤靠谱的内容。关注前端精读微信公众号版权声明：免费转载-非商业-非衍生-保留署名（知识共享3.0许可）
