深度学习 Virtual DOM，Diff 算法

george-es commented 3 years ago

什么是Virtual DOM？

在 vue 和 react 框架中，我们经常会听到一个概念，Virtual DOM，diff 算法，被搞得云里雾里，比较好理解的说法是

Virtual DOM 是相对于真实 DOM 而言的，在Virtual DOM 还没有出来之前，我们要改变页面展示的内容只能通过DOM 操作函数遍历查询 DOM 树的方式找到 DOM 节点，然后修改样式或结构，再通过 innerHTML ，经历了无数次的渲染，来达到更新 ui 的目的，但有了Virtual DOM 以后，就可以通过 js 的方式来修改，最终只渲染一次，效率成倍提高呀

上面的话没理解，没关系，简要概述下就是，Virtual DOM 是对真实 DOM 的一层抽象，是通过 js 来表述的，操作Virtual DOM 就是操作 js 对象，因此Virtual DOM 在增删改查的操作上都更优于真实 DOM，渲染上，如果直接操作真实 DOM 要渲染无数次，而操作Virtual DOM 只需要在最后的时候渲染即可。

为什么Virtual DOM 的性能开销会小呢？

其实最核心的原因不是查找或修改真实 DOM 上面的开销，而是将真实 DOM 转换成 js，再进行数据通信这上面的开销。DOM 树的实现模块和 js 实现模块是两个不同的模块，在不同模块上操作是要增加成本的，就好比为什么汽油车要做到几秒破百需要很高成本，而电动车则轻轻松松，几 W 块的都可以实现。

Virtual DOM 解决了什么问题？

无论是 vue 框架还是 react 框架，解决一个问题的思路都是一样的，避免我们直接去操作 DOM，而是通过数据来驱动视图的更新，一旦状态发生了变化，就用模板引擎渲染整个视图，用新的视图替换调旧的视图。

通过上述表达，我们知道，每个框架只是用自己方式去解决同样的问题，维护状态，更新视图。而Virtual DOM 要解决的就是避免直接操作 DOM，降低渲染次数。

再打个比方，没有Virtual DOM，每一个状态的改变，都会发生真实 DOM 的渲染，这会浪费很多性能，这时候有了Virtual DOM，状态改变了，先修改 js 对象，过段时间发现，状态已经修改完了，再进行渲染。前者要渲染多次，后者只要渲染一次。

diff 算法又是什么？

diff 算法是用来优化Virtual DOM 操作的，你想想，每次状态改变，都要把整个 js 对象重写一次，再全部重新渲染，工程量太大了，没有变的地方其实不需要渲染的，有没有一种方法，找出修改的地方，只针对局部节点进行渲染呢？就好像 ajax 局部刷新一样。

没错啦，想到这点，就是 diff 算法的作用了，它就是用来找不同的，然后再配合Virtual DOM，对视图进行局部渲染。

Virtual DOM 和原生的区别是什么？怎么更新 DOM？

我们看看一个真实 DOM 携带的属性，仅仅一层就超级庞大了

我们再看看Virtual DOM 如何描述一个节点的

var element = {
    tagName: 'div', // 节点名称
    props: {
        id: 'box'
    }
    children: [
        {tagName: 'span', props: { class: 'item' }, children: ["1"]},
        {tagName: 'span', props: { class: 'item' }, children: ["2"]},
        {tagName: 'span', props: { class: 'item' }, children: ["3"]},
    ]
}

上面对应的 HTML 写法是：

<div>
    <span>1</span>
    <span>2</span>
    <span>3</span>
</div>

看吧，用Virtual DOM 表示是不是超级简单。

这样我们就可以通过 js 来抽象真实 DOM，我们把这个叫做 js 对象树。

好了，万事俱备，我们有了Virtual DOM 和 diff 算法怎么更新 DOM

我们先将真实 DOM 抽象出来，形成一个 js 对象树，状态变化后，生成新的 js 对象树，通过 diff 算法对比新旧树的差异，将不同点记录下来，这就是我们需要对页面真正的 DOM 操作，然后再把它们应用在真正的 DOM 树上，页面就变更了，这样就可以做到，视图的结构确实是整个全新渲染了，但最后操作 DOM 的时候确实只变更有不同的地方。

这就是Virtual DOM 算法，主体分为三部

1、用 js 描述新旧树
2、用 diff 算法对比新旧树，找出修改点，并记录下来
3、将修改点应用到旧树所构建的真实 DOM 上，进行局部修改，视图就更新了

Virtual DOM 本质就是在 js 和真实 DOM 之间做了一层缓存，js 进行快处理，等确定最后数据了，再来修改真实 DOM

diff 算法改变史

计算一棵树形结构转换成另一棵树形结构的最少操作，是一个复杂且值得研究的问题。传统 diff 算法通过循环递归对节点进行依次对比，效率低下，算法复杂度达到 O(n^3)，其中 n 是树中节点的总数。O(n^3) 到底有多可怕，这意味着如果要展示1000个节点，就要依次执行上十亿次的比较。这种指数型的性能消耗对于前端渲染场景来说代价太高了！CPU 按每秒钟执行大约30亿条指令来计算，即便是最高效的实现，也不可能在一秒内计算出差异情况。

如果 React 只是单纯的引入 diff 算法而没有任何的优化改进，那么其效率是远远无法满足前端渲染所要求的性能。

因此，想要将 diff 思想引入 Virtual DOM，就需要设计一种稳定高效的 diff 算法，而 React 做到了！

React 怎么实现的呢？

Virtual DOM 算法实现

1、用 js 抽象真实 DOM

js 来描述真实 DOM 结构只需要三个属性，tagName，props，children，我们封装一个构造函数来表示

function Element(tagName, props, children) {
    this.tagName = tagName
    this.props = props
    this.children = children
}

渲染函数，用于构建真实 DOM

Element.prototype.render = function () {
    const el = document.createElement(this.tagName) // 创建 DOM 节点
    const props = this.props

    for (let propName in props) { // 为节点添加属性
        const propValue = props[propName]
        el.setAttribute(propName, propValue)
    }

    const children = this.children || []
    children.forEach(child => {
        let childEl = (child instanceof Element) ?
            child.render() : // 通过递归方式构建子节点
            document.createTextNode(child)
        el.appendChild(childEl)
    })
    return el
}

构建Virtual DOM

var div = Element('div', { id: 'box ' }, [
    Element('span', {class: 'item'}, ['Index 1']),
    Element('span', {class: 'item'}, ['Index 2']),
    Element('span', {class: 'item'}, ['Index 3']),
])

将真实 DOM 挂载到 body 中

var root = div.render()
document.body.appendChild(root)

如果只讲Virtual DOM，那么以上代码就描绘出基本思路了，但是，我们还有个 diff 算法，下面看看我们如何将 diff 算法融入到里面

2、比较两棵树的差异 —— Diff 算法

diff 算法是用于比较两棵 DOM 树差异的，也是Virtual DOM 最核心的算法，两颗树完全的 diff 算法是一个时间复杂度为 O(n ^ 3) 的问题，但是在前端中我们分析了可能存在的场景

跨层级移动 DOM 元素操作特别少。
拥有相同类的两个组件将会生成相似的树形结构，拥有不同类的两个组件将会生成不同的树形结构。
对于同一层级的一组子节点，它们可以通过唯一 id 进行区分。

因此做了些牺牲，提升了性能，它只会对同一个层级的元素进行对比。

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

差异

在前端中，对于 DOM 的差异可能会

替换掉原来的节点，例如把上面的 div 换成 p
新增，删除，移动子节点
修改节点属性
修改文本节点内容

因此根据差异，我们定义了几种差异类型

var REPLACE = 0  // 节点替换
var REORDER = 1  // 子节点操作
var PROPS = 2    // 属性修改
var TEXT = 3     // 修改文本

对于节点替换，判断新旧节点的 tagName 是不是一样的，如果不一样，说明需要替换

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

给子节点增加新的属性 id，就记录

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

如果是修改了文本节点，就记录

patches[2] = [{
    type: TEXT,
    content: 'Virtual Dom'
}]

如果是子节点替换呢？例如 p，span，div 替换成了 div，p，span 该如何对比呢？这就有两种情况了，同层级和非同层级，无论是那种情况，三种节点都会被替换掉，这样是不可取的，因为只是简单的移动就可以达到效果，没必要全部推倒重来，这样对 DOM 的开销也会非常的大。下面就会用到列表对比算法来优化节点替换操作

列表对比算法

假设现在可以英文字母唯一地标识每个子节点

旧的顺序

a b c d e f g h i

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

新的顺序

a b c h d f g i j

现在知道了新旧节点的顺序，求最小的插入、删除操作（移动可以看成是删除和插入操作的结合）。这个问题抽象出来其实是字符串的最小编辑距离问题，最常见的解决算法是通过动态规划求解，时间复杂度为 O(M * N)。但是我们并不需要真的达到最小的操作，我们只需要优化一些比较常见的移动情况，牺牲一定 DOM 操作，让算法时间复杂度达到线性的 O(max(M, N))。

我们能够获取到某个父节点的子节点的操作，并记录下来

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

但是要注意，因为 tagName 是可重复的，不能用这个来进行对比，所以需要给子节点加上唯一标识 key，列表对比的时候，使用 key 进行对比，这样才能复用老的 DOM 树上的节点。

这样，我们就可以通过深度优先遍历两棵树，每层的节点进行对比，记录下每个节点的差异了。

深度优先遍历

diff 算法采用的是深度遍历，对新旧两棵树进行一个深度优先的遍历，这样每个节点都会有一个唯一的标记

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

// 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}, ...] // 用数组存储新旧节点的不同

3、把差异应用到真正的 DOM 树上

对 DOM 树进行深度优先遍历后，通过 diff 算法（步骤2）获取到差异点，然后进行 DOM 操作

function patch(node, patches) {
    var walker = {index: 0}
    dfsWalk(node, walker, patches)
}

function dfsWalk(node, walker, patcher) {
    var currentPatches = patches[walker.index] // 从 patches 拿出当前节点的差异
    var len = node.childNodes ? node.childNodes.length : 0
    for(let 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)
        }
    })
}

小结

Virtual DOM 主要是实现了三个函数，分为 5 个步骤

// 1.构建Virtual 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.通过Virtual DOM 构建真正的 DOM
var root = tree.render()
document.body.appendChild(root)

// 3.生成新的Virtual 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.比较两颗Virtual DOM 树的不同
var patches = diff(tree, newTree)

// 5.在真正的 DOM 元素上应用变更
patch(root, patches)

这只是大致的思想，实践使用中还需要加入事件监听等。

优缺点

优点

对 DOM 进行集中化操作：无需手动操作 DOM ，虚拟 DOM 的 diff 和 patch 都是在一次更新中自动进行的，在数据改变时先对 Virtual DOM 进行修改，再反应到真实 DOM 中，用最小的代价来更新 DOM，提高效率
跨平台：可以渲染到 DOM 以外的端，因为虚拟 DOM 本质是 JS 对象，而 DOM 和平台具有强关联，相比之下虚拟 DOM 可以更好的跨平台，比如移动端开发，React VR，服务端渲染等
保证了性能的下限：虚拟 DOM 可以通过 diff 算法找出最小差异，然后批量进行 patch，比起粗暴的 DOM 来说还说性能还是好很多的

缺点

首次渲染大量 DOM 时，由于多了一层虚拟 DOM 的计算，比 innerHTML 插入慢。
虚拟 DOM 需要在内存中的维护一份 DOM 的副本，多占用了部分内存。
如果虚拟 DOM 大量更改，这是合适的。但是单一的、频繁的更新的话，虚拟 DOM 将会花费更多的时间处理计算的工作。所以如果你有一个 DOM 节点相对较少页面，用虚拟 DOM，它实际上有可能会更慢，但对于大多数单页面应用，这应该都会更快。

参考深度剖析如何实现一个 Virtual DOM 算法

george-es commented 3 years ago

// diff.js 完整算法

var _ = require('./util')
var patch = require('./patch')
var listDiff = require('list-diff2')

function diff (oldTree, newTree) {
  var index = 0
  var patches = {}
  dfsWalk(oldTree, newTree, index, patches)
  return patches
}

function dfsWalk (oldNode, newNode, index, patches) {
  var currentPatch = []

  // Node is removed.
  if (newNode === null) {
    // Real DOM node will be removed when perform reordering, so has no needs to do anything in here
  // TextNode content replacing
  } else if (_.isString(oldNode) && _.isString(newNode)) {
    if (newNode !== oldNode) {
      currentPatch.push({ type: patch.TEXT, content: newNode })
    }
  // Nodes are the same, diff old node's props and children
  } else if (
      oldNode.tagName === newNode.tagName &&
      oldNode.key === newNode.key
    ) {
    // Diff props
    var propsPatches = diffProps(oldNode, newNode)
    if (propsPatches) {
      currentPatch.push({ type: patch.PROPS, props: propsPatches })
    }
    // Diff children. If the node has a `ignore` property, do not diff children
    if (!isIgnoreChildren(newNode)) {
      diffChildren(
        oldNode.children,
        newNode.children,
        index,
        patches,
        currentPatch
      )
    }
  // Nodes are not the same, replace the old node with new node
  } else {
    currentPatch.push({ type: patch.REPLACE, node: newNode })
  }

  if (currentPatch.length) {
    patches[index] = currentPatch
  }
}

function diffChildren (oldChildren, newChildren, index, patches, currentPatch) {
  var diffs = listDiff(oldChildren, newChildren, 'key')
  newChildren = diffs.children

  if (diffs.moves.length) {
    var reorderPatch = { type: patch.REORDER, moves: diffs.moves }
    currentPatch.push(reorderPatch)
  }

  var leftNode = null
  var currentNodeIndex = index
  _.each(oldChildren, function (child, i) {
    var newChild = newChildren[i]
    currentNodeIndex = (leftNode && leftNode.count)
      ? currentNodeIndex + leftNode.count + 1
      : currentNodeIndex + 1
    dfsWalk(child, newChild, currentNodeIndex, patches)
    leftNode = child
  })
}

function diffProps (oldNode, newNode) {
  var count = 0
  var oldProps = oldNode.props
  var newProps = newNode.props

  var key, value
  var propsPatches = {}

  // Find out different properties
  for (key in oldProps) {
    value = oldProps[key]
    if (newProps[key] !== value) {
      count++
      propsPatches[key] = newProps[key]
    }
  }

  // Find out new property
  for (key in newProps) {
    value = newProps[key]
    if (!oldProps.hasOwnProperty(key)) {
      count++
      propsPatches[key] = newProps[key]
    }
  }

  // If properties all are identical
  if (count === 0) {
    return null
  }

  return propsPatches
}

function isIgnoreChildren (node) {
  return (node.props && node.props.hasOwnProperty('ignore'))
}

module.exports = diff

george-es commented 3 years ago

// element.js

var _ = require('./util')

/**
 * Virtual-dom Element.
 * @param {String} tagName
 * @param {Object} props - Element's properties,
 *                       - using object to store key-value pair
 * @param {Array<Element|String>} - This element's children elements.
 *                                - Can be Element instance or just a piece plain text.
 */
function Element (tagName, props, children) {
  if (!(this instanceof Element)) {
    if (!_.isArray(children) && children != null) {
      children = _.slice(arguments, 2).filter(_.truthy)
    }
    return new Element(tagName, props, children)
  }

  if (_.isArray(props)) {
    children = props
    props = {}
  }

  this.tagName = tagName
  this.props = props || {}
  this.children = children || []
  this.key = props
    ? props.key
    : void 666

  var count = 0

  _.each(this.children, function (child, i) {
    if (child instanceof Element) {
      count += child.count
    } else {
      children[i] = '' + child
    }
    count++
  })

  this.count = count
}

/**
 * Render the hold element tree.
 */
Element.prototype.render = function () {
  var el = document.createElement(this.tagName)
  var props = this.props

  for (var propName in props) {
    var propValue = props[propName]
    _.setAttr(el, propName, propValue)
  }

  _.each(this.children, function (child) {
    var childEl = (child instanceof Element)
      ? child.render()
      : document.createTextNode(child)
    el.appendChild(childEl)
  })

  return el
}

module.exports = Element

george-es commented 3 years ago

// patch.js

var _ = require('./util')

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

function patch (node, patches) {
  var walker = {index: 0}
  dfsWalk(node, walker, patches)
}

function dfsWalk (node, walker, patches) {
  var currentPatches = patches[walker.index]

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

function applyPatches (node, currentPatches) {
  _.each(currentPatches, function (currentPatch) {
    switch (currentPatch.type) {
      case REPLACE:
        var newNode = (typeof currentPatch.node === 'string')
          ? document.createTextNode(currentPatch.node)
          : currentPatch.node.render()
        node.parentNode.replaceChild(newNode, node)
        break
      case REORDER:
        reorderChildren(node, currentPatch.moves)
        break
      case PROPS:
        setProps(node, currentPatch.props)
        break
      case TEXT:
        if (node.textContent) {
          node.textContent = currentPatch.content
        } else {
          // fuck ie
          node.nodeValue = currentPatch.content
        }
        break
      default:
        throw new Error('Unknown patch type ' + currentPatch.type)
    }
  })
}

function setProps (node, props) {
  for (var key in props) {
    if (props[key] === void 666) {
      node.removeAttribute(key)
    } else {
      var value = props[key]
      _.setAttr(node, key, value)
    }
  }
}

function reorderChildren (node, moves) {
  var staticNodeList = _.toArray(node.childNodes)
  var maps = {}

  _.each(staticNodeList, function (node) {
    if (node.nodeType === 1) {
      var key = node.getAttribute('key')
      if (key) {
        maps[key] = node
      }
    }
  })

  _.each(moves, function (move) {
    var index = move.index
    if (move.type === 0) { // remove item
      if (staticNodeList[index] === node.childNodes[index]) { // maybe have been removed for inserting
        node.removeChild(node.childNodes[index])
      }
      staticNodeList.splice(index, 1)
    } else if (move.type === 1) { // insert item
      var insertNode = maps[move.item.key]
        ? maps[move.item.key].cloneNode(true) // reuse old item
        : (typeof move.item === 'object')
            ? move.item.render()
            : document.createTextNode(move.item)
      staticNodeList.splice(index, 0, insertNode)
      node.insertBefore(insertNode, node.childNodes[index] || null)
    }
  })
}

patch.REPLACE = REPLACE
patch.REORDER = REORDER
patch.PROPS = PROPS
patch.TEXT = TEXT

module.exports = patch

george-es commented 3 years ago

// util.js

var _ = exports

_.type = function (obj) {
  return Object.prototype.toString.call(obj).replace(/\[object\s|\]/g, '')
}

_.isArray = function isArray (list) {
  return _.type(list) === 'Array'
}

_.slice = function slice (arrayLike, index) {
  return Array.prototype.slice.call(arrayLike, index)
}

_.truthy = function truthy (value) {
  return !!value
}

_.isString = function isString (list) {
  return _.type(list) === 'String'
}

_.each = function each (array, fn) {
  for (var i = 0, len = array.length; i < len; i++) {
    fn(array[i], i)
  }
}

_.toArray = function toArray (listLike) {
  if (!listLike) {
    return []
  }

  var list = []

  for (var i = 0, len = listLike.length; i < len; i++) {
    list.push(listLike[i])
  }

  return list
}

_.setAttr = function setAttr (node, key, value) {
  switch (key) {
    case 'style':
      node.style.cssText = value
      break
    case 'value':
      var tagName = node.tagName || ''
      tagName = tagName.toLowerCase()
      if (
        tagName === 'input' || tagName === 'textarea'
      ) {
        node.value = value
      } else {
        // if it is not a input or textarea, use `setAttribute` to set
        node.setAttribute(key, value)
      }
      break
    default:
      node.setAttribute(key, value)
      break
  }
}

george-es / Blog