学习Virtual Dom笔记

栏目: JavaScript · 发布时间: 5年前

内容简介:把一个可以看到仅仅是第一层,真正

实现虚拟(Virtual) Dom

把一个 div 元素的属性打印出来,如下:

学习Virtual Dom笔记

可以看到仅仅是第一层,真正 DOM 的元素是非常庞大的,这也是 DOM 加载慢的原因。

相对于 DOM 对象,原生的 JavaScript 对象处理起来更快,而且更简单。 DOM 树上的结构、属性信息都可以用 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"]},
  ]
}

上面对应的 HTML 写法是:

<ul id='list'>
  <li class='item'>Item 1</li>
  <li class='item'>Item 2</li>
  <li class='item'>Item 3</li>
</ul>

DOM 树的信息可以用 JavaScript 对象表示出来,则说明可以用 JavaScript 对象去表示树结构来构建一棵真正的 DOM 树。

状态变更->重新渲染整个视图的方式可以用新渲染的对象树去和旧的树进行对比,记录这两棵树的差异。两者的不同之处就是我们需要对页面真正的 DOM 操作,然后把它们应用在真正的 DOM 树上,页面就变更了。这样可以做到:视图的结构确实是整个全新渲染了,但是最后操作 DOM 的只有变更不同的地方。

Virtual DOM算法,可以归纳为以下几个步骤:

  1. 用JavaScript对象结构表示 DOM 树的结构,然后用这个树构建一个真正的 DOM 树,插到文档当中
  2. 当状态变更的时候,重新构建一棵新的对象树。然后用新的树和旧的树进行比较,记录两棵树的差异
  3. 2 所记录的差异应用到步骤1所构建的的真正的 DOM 树上,视图就更新了

Virtual DOM 本质就是在JS和DOM之间做了一个缓存, JS 操作 Virtual DOM ,最后再应用到真正的 DOM 上。

难点-算法实现

步骤一:用 JS 对象模拟虚拟 DOM

JavaScript 来表示一个 DOM 节点,则需要记录它的节点类型、属性、子节点:

element.js

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)
}

上面的DOM结构可以表示为:

var el = require('./element')

var ul = el('ul', {id: 'list'}, [
  el('li', {class: 'item'}, ['Item 1']),
  el('li', {class: 'item'}, ['Item 2']),
  el('li', {class: 'item'}, ['Item 3'])
])

现在 ul 只是一个 JavaScript 对象表示的 DOM 结构,页面上并没有这个结构。可以根据这个 ul 构建真正的 <ul>

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
}

render 方法会根据 tagName 构建一个真正的 DOM 节点,然后设置这个节点的属性,最后递归地把自己的子节点也构建起来。所以需要:

var ulRoot = ul.render()
document.body.appendChild(ulRoot)

上面的 ulRoot 是真正的 DOM 节点,把它塞进文档中,这样 body 里面就有了真正的 <ul> 的DOM结构:

<ul id='list'>
  <li class='item'>Item 1</li>
  <li class='item'>Item 2</li>
  <li class='item'>Item 3</li>
</ul>

步骤二:比较两棵虚拟DOM树的差异

比较两棵 DOM 树的差异是 Virtual DOM 算法最核心的部分,就是 diff 算法。两棵树的完全 diff 算法是一个时间复杂度为 O(n^3) 的问题。但在前端中,很少会跨越层级地移动 DOM 元素。所以 Virtual DOM 只会对同一层级的元素进行对比:

学习Virtual Dom笔记

上面的 div 只会和同一层级的 div 对比,第二层级的只会跟第二层级对比。这样算法复杂度就可以达到 O(n)

a.深度优先遍历,记录差异

在实际的代码中,会对新旧两棵树进行一个深度优先的遍历,这样每个节点都会有一个唯一的标记:

学习Virtual Dom笔记

在深度优先遍历的时候,每遍历到一个节点就把该节点和新的树进行对比。如果有差异的话就记录到一个对象里面。

// 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
  })
}

例如,上面的div和新的div有差异,当前的标记是 0 ,那么:

patches[0] = [{difference}, {difference}, ...] // 用数组存储新旧节点的不同

同理 ppatches[1]ulpatches[3] ,以此类推

b.差异类型

DOM 操作会有的差异:

  1. 替换掉原来的节点,例如把上面的 div 换成了 section
  2. 移动、删除、新增子节点,例如上面的 div 的子节点,把 pul 顺序互换
  3. 修改了节点的属性
  4. 对于文本节点,文本内容可能会改变。例如修改上面的文本节点 2 内容为 Virtual DOM2

所以定义了几种差异类型:

var REPLACE = 0
var REORDER = 1
var PROPS = 2
var TEXT = 3

对于节点的替换,判断新旧节点的 tagName 和是不是一样,如果不一样就替换掉。如 div 换成 section ,记录如下:

patches[0] = [{
  type: REPALCE,
  node: newNode // el('section', props, children)
}]

如果给 div 新增了属性 idcontainer ,记录如下:

patches[0] = [{
  type: REPALCE,
  node: newNode // el('section', props, children)
}, {
  type: PROPS,
  props: {
    id: "container"
  }
}]

如果修改文本节点,如上面的文本节点 2 ,记录如下:

patches[2] = [{
  type: TEXT,
  content: "Virtual DOM2"
}]

c.列表对比算法

上面如果把 div 中的子节点重新排序,看如 puldiv 的顺序换成了 divpul 。按照同层进行顺序对比的话,它们都会被替换掉,这样 DOM 开销非常大。而实际上只需要通过节点移动就可以的了。

假设现在可以英文字母唯一得标志每一个子节点:

旧的节点顺序:

a b c d e f g h i

现在对节点进行删除、插入、移动的操作。新增j节点,删除e节点,移动h节点:

新的节点顺序:

a b c h d f g i j

现在知道了新旧的顺序,求最小的插入、删除操作(移动可以看成是删除和插入操作的结合)。这个问题抽象出来其实是字符串的最小编辑距离问题( Edition Distance ),最常见的算法是 Levenshtein Distance

通过动态规划求解,时间复杂度为 O(M*N) 。而我们只需要优化一些常见的移动操作,牺牲一定的 DOM 操作,让算法时间复杂度达到线性的 O((max(M,N)))

获取某个父节点的子节点的操作,就可以记录如下:

patches[0] = [{
  type: REORDER,
  moves: [{remove or insert}, {remove or insert}, ...]
}]

由于 tagName 是可以重复的,所以不能用这个来进行对比。需要给子节点加上一盒唯一标识 key ,列表对比的时候,使用 key 进行对比,这样就能复用旧的 DOM 树上的节点。

通过深度优先遍历两棵树,每层节点进行对比,记录下每个节点的差异。完整的 diff 算法访问: https://github.com/livoras/si...

步骤三:把差异应用到真正的 DOM 树上

因为步骤一所构建的 JavaScript 对象树和 render 出来的真正的 DOM 树的信息、结构是一样的。所以可以对那棵 DOM 树也进行深度优先遍历,遍历的时候从步骤二生成的 patches 对象中找出当前遍历的节点差异,然后进行 DOM 操作。

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操作
  }
}

applyPatches ,根据不同类型的差异对当前节点进行 DOM 操作:

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)
    }
  })
}

完整 patch 代码访问: https://github.com/livoras/si...

学习Virtual Dom笔记


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

妙趣横生的算法(C++语言实现)

妙趣横生的算法(C++语言实现)

胡浩 / 清华大学出版社 / 2014-10-1 / 59.80元

《妙趣横生的算法(C++语言实现)》内容丰富,生动有趣,寓教于乐,旨在帮助读者学习数据结构和算法的相关知识,从而开阔眼界,培养编程兴趣,提高编程能力,增强求职的竞争力。如果您想提高自己对算法和数据结构的理解能力,在程序设计之路上走得更远,那么请翻开《妙趣横生的算法(C++语言实现)》,仔细研读吧,它将助您一臂之力。 《妙趣横生的算法(C++语言实现)》以通俗易懂的语言深入浅出地介绍了常用的数......一起来看看 《妙趣横生的算法(C++语言实现)》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试