我的前端故事----React算法又是个什么鬼？
WendySturdi
8年前
<p>一不小心就过去了半年了，这么久以来都没有更新博客了，这半年也从开始的页面仔逐渐的变成一个jser，之前有人和我说前端没必要看算法。。。那些是后端的事情，前端的需求没有那么复杂等等。。。但随着2015年前端圈爆炸式的增长，越来越多的框架开始层出不穷的冒了出来，而对于我们前端人员的要求也从开始的切切图拼页面到现在的关注性能，关注工程化了。</p> <p> 而对于2016年，对抢眼的莫过于ReactJS了，从0.11开始关注和使用到现在的v15，版本迭代了多次，API改了无数，但最根本的几点却依旧没变，虚拟DOM，单项数据流，这些从React开始便存在的特点，直到现在都没有改变过，然而当我在实际项目中使用的时候却发现虽然这些框架都很好，可是推广起来却着实头疼。。。很多新手发现接手的代码和自己之前印象里的前端代码完全不在一个次元。。。</p> <p> 今天，借着这次机会我就总结一下自己对于React的虚拟DOM这部分的理解～说真的。。千万不要以为数据结构对前端没用。。。</p> <p> 首先我们来谈谈什么是虚拟DOM，以及为什么要使用虚拟DOM，其实很多时候我们都在或多或少的有过接触这个概念，我们知道当我们需要直接操作DOM节点的时候会遇到如下几个问题：</p> <p> 1，频繁的对DOM树进行操作会导致性能下降严重。</p> <p> 2，当我们需要一次修改很多地方的时候总会有地方被我们忽略或者忘记修改。</p> <p> 那么针对上面我们最常遇到的两点问题我们该用什么思路去解决呢？</p> <p> 对于第一点，我们就需要先知道为什么频繁的操作会导致性能下降，说道这个就要不得不提到前端面试中经常问到的优化方式－－repaint(重绘)和reflow(渲染)，那么对于这一点该具体如何理解和优化这位<a href="http://www.open-open.com/lib/view/open1463885389802.html">博友</a>说的很好了，有兴趣的同学可以看看他的这篇文章，那么我们今天就要从js上面下手去解决频繁的操作这个问题了，那么我们该如何减少渲染次数和范围呢？最简单直接的方法就是只渲染改动的地方，那么怎么才能知道哪里是改动的地方呢？对于这个问题，熟悉angularJS的同学一定知道angularJS中使用的“脏检查”机制，就是拿前后的DOM树去做对比，然而angularJS一直以来被人诟病的也就是这个了，性能差，消耗资源高等等，无一不是硬伤，那么我们该怎么曲线救国呢？React告诉我们的是在内存中维护一颗和页面一样的DOM树，这颗DOM树不是真正渲染在html中的，而是放在内存中的，因此修改它将会特别的快，并且资源消耗也少很多，当我们render一个页面的时候首先先将我们最新的DOM去和内存中的这棵虚拟DOM树去做对比（<em>脏检查</em>），然后对比出差一点，然后再用这棵虚拟DOM去整体替换html中实际的那个DOM树，这样其实我们只是做了一次渲染，无论我们改了多少，改了什么，我们都只是渲染了一次（<em>类似重新渲染一次页面</em>）。</p> <p> 那么接下来我们知道了思路后就该动手去实践了，既然说到了虚拟DOM树是真实DOM树的一个镜像，那么我们该如何在内存中保存这棵树呢？又该用什么方式去存储呢？这个时候就是数据结构同学上线的时间了，相对于 DOM 对象，原生的 JavaScript 对象处理起来更快，而且更简单。因此DOM 树上的结构、属性信息我们都可以很容易地用 JavaScript 对象表示出来：</p> <p> </p> <pre> <code class="language-javascript">var element = { tagName: 'ul', // 节点标签名 props: { // DOM的属性，用一个对象存储键值对 id: 'list' }, children: [ // 该节点的子节点 {tagName: 'li', props: {class: 'item'}, children: ["Item 1"]}, {tagName: 'li', props: {class: 'item'}, children: ["Item 2"]}, {tagName: 'li', props: {class: 'item'}, children: ["Item 3"]}, ] }</code></pre> <p> </p> <p>而这样一个javascript对象代表的html代码是什么样的呢？</p> <pre> <code class="language-javascript"><ul id='list'> <li class='item'>Item 1</li> <li class='item'>Item 2</li> <li class='item'>Item 3</li> </ul></code></pre> <p>其实对比过来会发现每一种HTML结构都可以转变成对应的javascript结构的。 这就是所谓的 Virtual DOM 算法。包括几个步骤：</p> <p> 1，用 JavaScript 对象结构表示 DOM 树的结构；然后用这个树构建一个真正的 DOM 树，插到文档当中。</p> <p> 2，当状态变更的时候，重新构造一棵新的对象树。然后用新的树和旧的树进行比较，记录两棵树差异。</p> <p> 3，把2所记录的差异应用到步骤1所构建的真正的DOM树上，视图就更新了。</p> <p> <strong>Virtual DOM 本质上就是在 JS 和 DOM 之间做了一个缓存。这个概念就和我们当初学操作系统一样，可以类比 CPU 和硬盘，既然硬盘这么慢，我们就在它们之间加个缓存：既然 DOM 这么慢，我们就在它们 JS 和 DOM 之间加个缓存。CPU（JS）只操作内存（Virtual DOM），最后的时候再把变更写入硬盘（DOM）。</strong></p> <p>接下来我们说说算法的具体实现吧，既然整个过程大致可以分为三部，那我们就来一步步的讲，首先就是第一部，用js对象模拟DOM树，用javascript来表示一个DOM节点的话只需要记录它的一个节点类型，属性以及子节点就可以了。</p> <p> </p> <pre> <code class="language-javascript">function Element (tagName, props, children) { this.tagName = tagName this.props = props this.children = children } module.exports = function (tagName, props, children) { return new Element(tagName, props, children) }</code></pre> <p> </p> <p>例如上面刚刚的那个DOM节点就可以用这种结构来表示：</p> <pre> <code class="language-javascript">var ul = Element('ul', {id: 'list'}, [ Element('li', {class: 'item'}, ['Item 1']), Element('li', {class: 'item'}, ['Item 2']), Element('li', {class: 'item'}, ['Item 3']) ])</code></pre> <p>现在ul只是一个 JavaScript 对象表示的 DOM 结构，页面上并没有这个结构。我们可以根据这个ul构建真正的HTML元素了：</p> <p> </p> <pre> <code class="language-javascript">Element.prototype.render = function () { var el = document.createElement(this.tagName) // 根据tagName构建 var props = this.props for (var propName in props) { // 设置节点的DOM属性 var propValue = props[propName] el.setAttribute(propName, propValue) } var children = this.children || [] children.forEach(function (child) { var childEl = (child instanceof Element) ? child.render() // 如果子节点也是虚拟DOM，递归构建DOM节点 : document.createTextNode(child) // 如果字符串，只构建文本节点 el.appendChild(childEl) }) return el }</code></pre> <p> </p> <p>render 方法会根据传入的 tagName 来构建一个真正的DOM节点的，然后根据这个DOM节点的属性，递归的把自己的子节点也构建出来，因此只需要执行如下代码即可：</p> <pre> <code class="language-javascript">var ulRoot = ul.render() document.body.appendChild(ulRoot)</code></pre> <p>上面的 ulRoot 才是真正的DOM节点，最终会在页面中插入这个真正的DOM树：</p> <pre> <code class="language-javascript"><ul id='list'> <li class='item'>Item 1</li> <li class='item'>Item 2</li> <li class='item'>Item 3</li> </ul></code></pre> <p><strong> 第二步：比较两颗虚拟DOM树的差异：</strong></p> <p> 当然，对比两个DOM树的差异才是最核心的部分，这也就是所谓的diff算法了，两个DOM的算法是一个 <strong>O(n^3)</strong> 问题。 但是在前端的实际使用种我们很少去跨级的移动整个DOM树，所以我们可以简化成一层之间的移动，所以diff算法就变成了一个同级元素对比的算法了（<em>仅仅是说明用，真正的算法实现还是去看React的源代码吧</em>）。</p> <p><img alt="我的前端故事----React算法又是个什么鬼？" src="https://simg.open-open.com/show/6d64b0b7889e7f020bb020aea5947a09.png" width="912" height="471"><img alt="我的前端故事----React算法又是个什么鬼？" src="https://simg.open-open.com/show/c4ba535164d29fd46383d19512c37349.png" width="1018" height="513"></p> <p> 上面的图片中的移动其实只是同级 div 的对比，第二层级的 div 只会跟第二层级的 div 对比。这样算法复杂度就可以达到 <strong>O(n)</strong>。紧接着就是通过深度优先遍历来记录差异，在深度优先遍历的时候，每遍历到一个节点就把该节点和新的的树进行对比。如果有差异的话就记录到一个对象里面（<em>类似权重相加的概念</em>）。</p> <p> </p> <pre> <code class="language-javascript">// diff 函数，对比两棵树 function diff (oldTree, newTree) { var index = 0 // 当前节点的标志 var patches = {} // 用来记录每个节点差异的对象 dfsWalk(oldTree, newTree, index, patches) return patches } // 对两棵树进行深度优先遍历 function dfsWalk (oldNode, newNode, index, patches) { // 对比oldNode和newNode的不同，记录下来 patches[index] = [...] diffChildren(oldNode.children, newNode.children, index, patches) } // 遍历子节点 function diffChildren (oldChildren, newChildren, index, patches) { var leftNode = null var currentNodeIndex = index oldChildren.forEach(function (child, i) { var newChild = newChildren[i] currentNodeIndex = (leftNode && leftNode.count) // 计算节点的标识 ? currentNodeIndex + leftNode.count + 1 : currentNodeIndex + 1 dfsWalk(child, newChild, currentNodeIndex, patches) // 深度遍历子节点 leftNode = child }) }</code></pre> <p> </p> <p>例如，上面的div和新的div有差异，当前的标记是0，那么：</p> <pre> <code class="language-javascript">patches[0] = [{difference}, {difference}, ...] // 用数组存储新旧节点的不同</code></pre> <p>同理p是patches[1]，ul是patches[3]，以此类推。那差异类型是什么呢？ 对DOM操作可能会有下面几种：</p> <ul> <li><strong>替换掉原来的节点，例如把上面的div换成了section</strong></li> <li><strong>移动、删除、新增子节点，例如上面div的子节点，把p和ul顺序互换</strong></li> <li><strong>修改了节点的属性</strong></li> <li><strong>对于文本节点，文本内容可能会改变。例如修改上面的文本节点2内容为Virtual DOM 2。</strong></li> </ul> <p>所以我们需要定义几种差异类型：</p> <pre> <code class="language-javascript">var REPLACE = 0 var REORDER = 1 var PROPS = 2 var TEXT = 3</code></pre> <p>那对于节点的替换就很简单了，只要判断新旧节点的 tagName 的和是不是一样的，如果不一样就说明需要替换了，例如 div 替换成 section，就记作：</p> <pre> <code class="language-javascript">patches[0] = [{ type: REPALCE, node: newNode // el('section', props, children) }]</code></pre> <p>如果给 div 新增了属性 id 为 test ，就记作：</p> <p> </p> <pre> <code class="language-javascript">patches[0] = [{ type: REPALCE, node: newNode // el('section', props, children) }, { type: PROPS, props: { id: "test" } }]</code></pre> <p> </p> <p>如果是文本节点的话，就记作：</p> <pre> <code class="language-javascript">patches[2] = [{ type: TEXT, content: "Virtual DOM2" }]</code></pre> <p> 那如果把我div的子节点重新排序呢？例如p, ul, div的顺序换成了div, p, ul。这个该怎么对比？如果按照同层级进行顺序对比的话，它们都会被替换掉。如p和div的tagName不同，p会被div所替代。最终，三个节点都会被替换，这样DOM开销就非常大。而实际上是不需要替换节点，而只需要经过节点移动就可以达到，我们只需知道怎么进行移动。接下来是列表对比算法。</p> <p>假设现在可以英文字母唯一地标识每一个子节点：</p> <p><strong>旧的节点顺序：a b c d e f g h i </strong></p> <p>现在对节点进行了删除、插入、移动的操作。新增j节点，删除e节点，移动h节点：</p> <p><strong> 新的节点顺序：a b c h d f g i j</strong></p> <p> 现在知道了新旧的顺序，求最小的插入、删除操作（<em>移动可以看成是删除和插入操作的结合</em>）。这个问题抽象出来其实是字符串的最小编辑距离问题（<em>Edition Distance</em>），最常见的解决算法是 Levenshtein Distance，通过动态规划求解，时间复杂度为 <strong>O(M * N)</strong>。但是我们并不需要真的达到最小的操作，我们只需要优化一些比较常见的移动情况，牺牲一定DOM操作，让算法时间复杂度达到线性的（<strong>O(max(M, N)</strong>)。具体算法细节比较多，这里不累述。我们能够获取到某个父节点的子节点的操作，就可以记录下来：</p> <pre> <code class="language-javascript">patches[0] = [{ type: REORDER, moves: [{remove or insert}, {remove or insert}, ...] }]</code></pre> <p> 但是要注意的是，因为tagName是可重复的，不能用这个来进行对比。所以需要给子节点加上唯一标识key，列表对比的时候，使用key进行对比，这样才能复用老的 DOM 树上的节点。这样，我们就可以通过深度优先遍历两棵树，每层的节点进行对比，记录下每个节点的差异了。</p> <p> 接下来就是第三步，<strong>把差异应用到真正的DOM树上</strong>！因为步骤一所构建的 JavaScript 对象树和render出来真正的DOM树的信息、结构是一样的。所以我们可以对那棵DOM树也进行深度优先的遍历，遍历的时候从步骤二生成的patches对象中找出当前遍历的节点差异，然后进行 DOM 操作。</p> <p> </p> <pre> <code class="language-javascript">function patch (node, patches) { var walker = {index: 0} dfsWalk(node, walker, patches) } function dfsWalk (node, walker, patches) { var currentPatches = patches[walker.index] // 从patches拿出当前节点的差异 var len = node.childNodes ? node.childNodes.length : 0 for (var i = 0; i < len; i++) { // 深度遍历子节点 var child = node.childNodes[i] walker.index++ dfsWalk(child, walker, patches) } if (currentPatches) { applyPatches(node, currentPatches) // 对当前节点进行DOM操作 } }</code></pre> <p> </p> <p>applyPatches，根据不同类型的差异对当前节点进行 DOM 操作：</p> <p> </p> <pre> <code class="language-javascript">function applyPatches (node, currentPatches) { currentPatches.forEach(function (currentPatch) { switch (currentPatch.type) { case REPLACE: node.parentNode.replaceChild(currentPatch.node.render(), node) break case REORDER: reorderChildren(node, currentPatch.moves) break case PROPS: setProps(node, currentPatch.props) break case TEXT: node.textContent = currentPatch.content break default: throw new Error('Unknown patch type ' + currentPatch.type) } }) }</code></pre> <p> </p> <p>而virtual DOM 算法主要是实现上面步骤的三个函数：element，diff，patch。然后就可以实际的进行使用：</p> <p> </p> <pre> <code class="language-javascript">// 1. 构建虚拟DOM var tree = el('div', {'id': 'container'}, [ el('h1', {style: 'color: blue'}, ['simple virtal dom']), el('p', ['Hello, virtual-dom']), el('ul', [el('li')]) ]) // 2. 通过虚拟DOM构建真正的DOM var root = tree.render() document.body.appendChild(root) // 3. 生成新的虚拟DOM var newTree = el('div', {'id': 'container'}, [ el('h1', {style: 'color: red'}, ['simple virtal dom']), el('p', ['Hello, virtual-dom']), el('ul', [el('li'), el('li')]) ]) // 4. 比较两棵虚拟DOM树的不同 var patches = diff(tree, newTree) // 5. 在真正的DOM元素上应用变更 patch(root, patches)</code></pre> <p> </p> <p> 至此，全部的渲染过程都完成了，到此为止我想很多新入手的同学多少应该可以理解这个React了这篇博客中的算法实现我也是参考Github上面一位大神的实现，所以在这里我更多的是介绍整个流程的思路，希望对于React还一头雾水的同学能够仔细看过这篇说明后有所理解，不是算法不重要，无论是哪个岗位上的程序员，都需要熟悉数据结构，这是作为一个程序员理清思路的必备要素～～接下来的博客我会介绍一些前端工程化上面的理解，希望大家能喜欢～～</p> <p>来自：http://www.cnblogs.com/fuhuixiang/p/5505848.html</p> <p> </p>