React で diff アルゴリズムを実装する方法

今回は React で diff アルゴリズムを実装する方法を説明します。 React で diff アルゴリズムを実装する際の 注意事項 は何ですか。実際のケースを見てみましょう。

はじめに

前回の記事ではReactのコンポーネント機能を実装しましたが、機能面ではReactのコア機能を実装しました。

しかし、私たちの実装には大きな問題があります。アプリケーション全体またはコンポーネント全体が更新されるたびに再レンダリングされ、

DOM 操作は非常に高価で、パフォーマンスの損失は非常に大きくなります。

DOM の更新を減らすには、レンダリングの前後で実際に変更された部分を見つけて、DOM のこの部分のみを更新する必要があります。変更を比較し、更新する必要がある部分を見つけるアルゴリズムは diff アルゴリズムと呼ばれます。

比較戦略

前の 2 つの記事の後、仮想 DOM を実際の DOM にレンダリングできるレンダリング メソッドを実装しました。DOM 全体が愚かに再レンダリングされないようにする必要があります。ただし、実際に変更された部分を見つけるためです。

多くの React 系フレームワークは、この部分をさまざまな方法で実装しています。一部のフレームワークは、最後にレンダリングされた仮想 DOM を保存し、仮想 DOM の前後の変更を比較して一連の更新データを取得し、これらの更新を適用します。実際の DOM 上で。

ただし、仮想 DOM と実際の DOM を直接比較することを選択するフレームワークもあります。これにより、最後にレンダリングされた仮想 DOM を保存する必要がなく、比較中に更新できるようになります。これも私たちが選択する方法です。

DOM であっても仮想 DOM であっても、その構造はツリーです。2 つのツリー間の変更を完全に比較するアルゴリズムの時間計算量は O(n^3) ですが、DOM をレベル間で移動することはほとんどないことを考慮すると、同じレベルでの変更を比較する必要があります。

同じカラーボックス内のノードを比較するだけで済みます

つまり、差分アルゴリズムには 2 つの原則があります:

1. 現在の実際の DOM と仮想 DOM を比較し、比較プロセス中に実際の DOM を直接更新します。

2. 同じレベルの変更のみを比較してください

diff メソッドを実装する必要があります。その機能は、実際の DOM と仮想 DOM を比較し、最終的に更新された DOM を返すことです

/**
 * @param {HTMLElement} dom 真实DOM
 * @param {vnode} vnode 虚拟DOM
 * @returns {HTMLElement} 更新后的DOM
 */
function diff( dom, vnode ) {
  // ...
}

次のステップは実装ですこの方法。

その前に、仮想 DOM の構造を思い出してみましょう:

仮想 DOM の構造は、それぞれテキスト、ネイティブ

DOM ノード、コンポーネントを表す 3 つのタイプに分類できます。

// 原生DOM节点的vnode
{
  tag: 'p',
  attrs: {
    className: 'container'
  },
  children: []
}
// 文本节点的vnode
"hello,world"
// 组件的vnode
{
  tag: ComponentConstrucotr,
  attrs: {
    className: 'container'
  },
  children: []
}

テキスト ノードを比較する

まず、現在の DOM がテキスト ノードの場合はコンテンツを直接更新します。それ以外の場合は、新しいテキスト ノードを作成して元の DOM を削除します。

// diff text node
if ( typeof vnode === 'string' ) {
  // 如果当前的DOM就是文本节点，则直接更新内容
  if ( dom && dom.nodeType === 3 ) {  // nodeType: https://developer.mozilla.org/zh-CN/docs/Web/API/Node/nodeType
    if ( dom.textContent !== vnode ) {
      dom.textContent = vnode;
    }
  // 如果DOM不是文本节点，则新建一个文本节点DOM，并移除掉原来的
  } else {
    out = document.createTextNode( vnode );
    if ( dom && dom.parentNode ) {
      dom.parentNode.replaceChild( out, dom );
    }
  }
  return out;
}

テキスト ノードは非常に単純なので、属性や子要素がないため、このステップの直後に結果を返すことができます。

非テキスト DOM ノードを比較する

vnode が非テキスト DOM ノードを表す場合、いくつかの状況が考えられます:

現在の実際の DOM が次のように、実際の DOM と仮想 DOM のタイプが異なる場合p で、vnode のタグの値が 'button' の場合、元の p には使用値がありません。新しいボタン要素を直接作成し、p のすべての子ノードをボタンの下に移動し、replaceChild メソッドを使用して置き換えます。 pをボタンに押し込みます。

if ( !dom || dom.nodeName.toLowerCase() !== vnode.tag.toLowerCase() ) {
  out = document.createElement( vnode.tag );
  if ( dom ) {
    [ ...dom.childNodes ].map( out.appendChild );  // 将原来的子节点移到新节点下
    if ( dom.parentNode ) {
      dom.parentNode.replaceChild( out, dom );  // 移除掉原来的DOM对象
    }
  }
}

実際の DOM と仮想 DOM が同じ型の場合は、今のところ他に何もする必要はありません。後で属性の比較と子ノードの比較を待つだけで済みます。

属性の比較

実際、diff アルゴリズムはノード タイプの変更を検出するだけでなく、ノード属性とイベント リスニングの変更も検出します。比較属性をメソッドとして分離します:

function diffAttributes( dom, vnode ) {
  const old = dom.attributes;  // 当前DOM的属性
  const attrs = vnode.attrs;   // 虚拟DOM的属性
  // 如果原来的属性不在新的属性当中，则将其移除掉（属性值设为undefined）
  for ( let name in old ) {
    if ( !( name in attrs ) ) {
      setAttribute( dom, name, undefined );
    }
  }
  // 更新新的属性值
  for ( let name in attrs ) {
    if ( old[ name ] !== attrs[ name ] ) {
      setAttribute( dom, name, attrs[ name ] );
    }
  }
}

setAttribute メソッドの実装は最初の記事にあります

子ノードを比較します

ノード自体の比較が完了し、次のステップは子ノードを比較します。

这里会面临一个问题，前面我们实现的不同diff方法，都是明确知道哪一个真实DOM和虚拟DOM对比，但是子节点是一个数组，它们可能改变了顺序，或者数量有所变化，我们很难确定要和虚拟DOM对比的是哪一个。

为了简化逻辑，我们可以让用户提供一些线索：给节点设一个key值，重新渲染时对比key值相同的节点。

// diff方法
if ( vnode.children && vnode.children.length > 0 || ( out.childNodes && out.childNodes.length > 0 ) ) {
  diffChildren( out, vnode.children );
}

function diffChildren( dom, vchildren ) {
  const domChildren = dom.childNodes;
  const children = [];
  const keyed = {};
  // 将有key的节点和没有key的节点分开
  if ( domChildren.length > 0 ) {
    for ( let i = 0; i < domChildren.length; i++ ) {
      const child = domChildren[ i ];
      const key = child.key;
      if ( key ) {
        keyedLen++;
        keyed[ key ] = child;
      } else {
        children.push( child );
      }
    }
  }
  if ( vchildren && vchildren.length > 0 ) {
    let min = 0;
    let childrenLen = children.length;
    for ( let i = 0; i < vchildren.length; i++ ) {
      const vchild = vchildren[ i ];
      const key = vchild.key;
      let child;
      // 如果有key，找到对应key值的节点
      if ( key ) {
        if ( keyed[ key ] ) {
          child = keyed[ key ];
          keyed[ key ] = undefined;
        }
      // 如果没有key，则优先找类型相同的节点
      } else if ( min < childrenLen ) {
        for ( let j = min; j < childrenLen; j++ ) {
          let c = children[ j ];
          if ( c && isSameNodeType( c, vchild ) ) {
            child = c;
            children[ j ] = undefined;
            if ( j === childrenLen - 1 ) childrenLen--;
            if ( j === min ) min++;
            break;
          }
        }
      }
      // 对比
      child = diff( child, vchild );
      // 更新DOM
      const f = domChildren[ i ];
      if ( child && child !== dom && child !== f ) {
        if ( !f ) {
          dom.appendChild(child);
        } else if ( child === f.nextSibling ) {
          removeNode( f );
        } else {
          dom.insertBefore( child, f );
        }
      }
    }
  }
}

对比组件

如果vnode是一个组件，我们也单独拿出来作为一个方法:

function diffComponent( dom, vnode ) {
  let c = dom && dom._component;
  let oldDom = dom;
  // 如果组件类型没有变化，则重新set props
  if ( c && c.constructor === vnode.tag ) {
    setComponentProps( c, vnode.attrs );
    dom = c.base;
  // 如果组件类型变化，则移除掉原来组件，并渲染新的组件
  } else {
    if ( c ) {
      unmountComponent( c );
      oldDom = null;
    }
    c = createComponent( vnode.tag, vnode.attrs );
    setComponentProps( c, vnode.attrs );
    dom = c.base;
    if ( oldDom && dom !== oldDom ) {
      oldDom._component = null;
      removeNode( oldDom );
    }
  }
  return dom;
}

下面是相关的工具方法的实现，和上一篇文章的实现相比，只需要修改renderComponent方法其中的一行。

function renderComponent( component ) {
  
  // ...
  // base = base = _render( renderer );     // 将_render改成diff
  base = diff( component.base, renderer );
  // ...
}

完整diff实现看这个文件

渲染

现在我们实现了diff方法，我们尝试渲染上一篇文章中定义的Counter组件，来感受一下有无diff方法的不同。

class Counter extends React.Component {
  constructor( props ) {
    super( props );
    this.state = {
      num: 1
    }
  }
  onClick() {
    this.setState( { num: this.state.num + 1 } );
  }
  render() {
    return (
      <p>
        <h1>count: { this.state.num }</h1>
        <button onClick={ () => this.onClick()}>add</button>
      </p>
    );
  }
}

不使用diff

使用上一篇文章的实现，从chrome的调试工具中可以看到，闪烁的部分是每次更新的部分，每次点击按钮，都会重新渲染整个组件。

使用diff

而实现了diff方法后，每次点击按钮，都只会重新渲染变化的部分。

后话

在这篇文章中我们实现了diff算法，通过它做到了每次只更新需要更新的部分，极大地减少了DOM操作。React实现远比这个要复杂，特别是在React 16之后还引入了Fiber架构，但是主要的思想是一致的。

实现diff算法可以说性能有了很大的提升，但是在别的地方仍然后很多改进的空间：每次调用setState后会立即调用renderComponent重新渲染组件，但现实情况是，我们可能会在极短的时间内多次调用setState。

假设我们在上文的Counter组件中写出了这种代码

onClick() {
  for ( let i = 0; i < 100; i++ ) {
    this.setState( { num: this.state.num + 1 } );
  }
}

相信看了本文案例你已经掌握了方法，更多精彩请关注php中文网其它相关文章！

推荐阅读：

实现vue多页面开发与打包步骤详解

Vue实现proxy代理步骤详解

以上がReact で diff アルゴリズムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。