Home Web Front-end JS Tutorial How to implement diff algorithm in React

How to implement diff algorithm in React

Apr 27, 2018 pm 03:45 PM
diff react algorithm

This time I will show you how to implement the diff algorithm in React. What are the precautions for implementing the diff algorithm in React? The following is a practical case, let's take a look.

Preface

In the previous article, we have implemented the component function of React. From a functional perspective, we have implemented React core functions.

But our implementation has a big problem: every time it is updated, the entire application or the entire component is re-rendered,

DOM operations are very expensive, and the performance loss is very large.

In order to reduce DOM updates, we need to find the parts that really changed before and after rendering, and only update this part of the DOM. The algorithm that compares changes and finds out the parts that need to be updated is called the diff algorithm.

Comparison Strategy

After the previous two articles, we implemented a render method that can render virtual DOM into real DOM , we need to improve it now so that it no longer stupidly re-renders the entire DOM tree, but finds out the parts that really changed.

Many React-like frameworks implement this part in different ways. Some frameworks will choose to save the last rendered virtual DOM, and then compare the changes before and after the virtual DOM to obtain a series of updated data, and then These updates are applied to the real DOM.

But there are also some frameworks that choose to directly compare the virtual DOM and the real DOM, so that there is no need to save the last rendered virtual DOM and can be updated while comparing. This is also the method we choose.

Whether it is DOM or virtual DOM, their structure is a tree. The time complexity of the algorithm that completely compares the changes between the two trees is O(n^3), but considering that we rarely cross levels Move the DOM, so we only need to compare changes at the same level.

Only need to compare nodes in the same color box

In short, our diff algorithm has two principles:

  1. Compare the current real DOM and virtual DOM, and directly update the real DOM during the comparison process

  2. Only compare changes at the same level

We need to implement a diff method, which is used to compare the real DOM and the virtual DOM, and finally return the updated DOM

/**
 * @param {HTMLElement} dom 真实DOM
 * @param {vnode} vnode 虚拟DOM
 * @returns {HTMLElement} 更新后的DOM
 */
function diff( dom, vnode ) {
  // ...
}
Copy after login
The next step is to implement this method.

Before that, let’s recall the structure of our virtual DOM:

The structure of virtual DOM can be divided into three types, representing text, native

DOM nodes and components. .

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

Compare text nodes

First consider the simplest text node. If the current DOM is a text node, update the content directly, otherwise Just create a new text node and remove the original 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;
}
Copy after login
The text node is very simple. It has no attributes and no child elements, so the result can be returned directly after this step.

Compare non-text DOM nodes

If vnode represents a non-text DOM node, then there are several situations:

If the types of the real DOM and the virtual DOM are different, for example, the current real DOM is a p, and the value of the vnode tag is 'button', then the original p has no use value, and a new button element is created directly. , and move all the child nodes of p under button, and then use the replaceChild method to replace p with button.

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对象
    }
  }
}
Copy after login
If the real DOM and the virtual DOM are of the same type, then we don’t need to do anything else for the time being, we just need to wait for the comparison of attributes and comparison of child nodes later.

Compare attributes

In fact, the diff algorithm not only finds changes in node types, it also finds out the attributes and events of nodes Listen for changes. We separate the comparison attribute as a method:

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 ] );
    }
  }
}
Copy after login
For the implementation of the setAttribute method, please refer to the first article

Compare child nodes

The comparison of the node itself is completed, and the next step is to compare its child nodes.

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

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

// diff方法
if ( vnode.children && vnode.children.length > 0 || ( out.childNodes && out.childNodes.length > 0 ) ) {
  diffChildren( out, vnode.children );
}
Copy after login
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 );
        }
      }
    }
  }
}
Copy after login

对比组件

如果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;
}
Copy after login

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

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

完整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>
    );
  }
}
Copy after login

不使用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 } );
  }
}
Copy after login

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

推荐阅读:

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

Vue实现proxy代理步骤详解

The above is the detailed content of How to implement diff algorithm in React. For more information, please follow other related articles on the PHP Chinese website!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Best Graphic Settings
2 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. How to Fix Audio if You Can't Hear Anyone
2 weeks ago By 尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

CLIP-BEVFormer: Explicitly supervise the BEVFormer structure to improve long-tail detection performance CLIP-BEVFormer: Explicitly supervise the BEVFormer structure to improve long-tail detection performance Mar 26, 2024 pm 12:41 PM

Written above &amp; the author’s personal understanding: At present, in the entire autonomous driving system, the perception module plays a vital role. The autonomous vehicle driving on the road can only obtain accurate perception results through the perception module. The downstream regulation and control module in the autonomous driving system makes timely and correct judgments and behavioral decisions. Currently, cars with autonomous driving functions are usually equipped with a variety of data information sensors including surround-view camera sensors, lidar sensors, and millimeter-wave radar sensors to collect information in different modalities to achieve accurate perception tasks. The BEV perception algorithm based on pure vision is favored by the industry because of its low hardware cost and easy deployment, and its output results can be easily applied to various downstream tasks.

Implementing Machine Learning Algorithms in C++: Common Challenges and Solutions Implementing Machine Learning Algorithms in C++: Common Challenges and Solutions Jun 03, 2024 pm 01:25 PM

Common challenges faced by machine learning algorithms in C++ include memory management, multi-threading, performance optimization, and maintainability. Solutions include using smart pointers, modern threading libraries, SIMD instructions and third-party libraries, as well as following coding style guidelines and using automation tools. Practical cases show how to use the Eigen library to implement linear regression algorithms, effectively manage memory and use high-performance matrix operations.

Explore the underlying principles and algorithm selection of the C++sort function Explore the underlying principles and algorithm selection of the C++sort function Apr 02, 2024 pm 05:36 PM

The bottom layer of the C++sort function uses merge sort, its complexity is O(nlogn), and provides different sorting algorithm choices, including quick sort, heap sort and stable sort.

Can artificial intelligence predict crime? Explore CrimeGPT's capabilities Can artificial intelligence predict crime? Explore CrimeGPT's capabilities Mar 22, 2024 pm 10:10 PM

The convergence of artificial intelligence (AI) and law enforcement opens up new possibilities for crime prevention and detection. The predictive capabilities of artificial intelligence are widely used in systems such as CrimeGPT (Crime Prediction Technology) to predict criminal activities. This article explores the potential of artificial intelligence in crime prediction, its current applications, the challenges it faces, and the possible ethical implications of the technology. Artificial Intelligence and Crime Prediction: The Basics CrimeGPT uses machine learning algorithms to analyze large data sets, identifying patterns that can predict where and when crimes are likely to occur. These data sets include historical crime statistics, demographic information, economic indicators, weather patterns, and more. By identifying trends that human analysts might miss, artificial intelligence can empower law enforcement agencies

Improved detection algorithm: for target detection in high-resolution optical remote sensing images Improved detection algorithm: for target detection in high-resolution optical remote sensing images Jun 06, 2024 pm 12:33 PM

01 Outlook Summary Currently, it is difficult to achieve an appropriate balance between detection efficiency and detection results. We have developed an enhanced YOLOv5 algorithm for target detection in high-resolution optical remote sensing images, using multi-layer feature pyramids, multi-detection head strategies and hybrid attention modules to improve the effect of the target detection network in optical remote sensing images. According to the SIMD data set, the mAP of the new algorithm is 2.2% better than YOLOv5 and 8.48% better than YOLOX, achieving a better balance between detection results and speed. 02 Background & Motivation With the rapid development of remote sensing technology, high-resolution optical remote sensing images have been used to describe many objects on the earth’s surface, including aircraft, cars, buildings, etc. Object detection in the interpretation of remote sensing images

Integration of Java framework and front-end React framework Integration of Java framework and front-end React framework Jun 01, 2024 pm 03:16 PM

Integration of Java framework and React framework: Steps: Set up the back-end Java framework. Create project structure. Configure build tools. Create React applications. Write REST API endpoints. Configure the communication mechanism. Practical case (SpringBoot+React): Java code: Define RESTfulAPI controller. React code: Get and display the data returned by the API.

PHP, Vue and React: How to choose the most suitable front-end framework? PHP, Vue and React: How to choose the most suitable front-end framework? Mar 15, 2024 pm 05:48 PM

PHP, Vue and React: How to choose the most suitable front-end framework? With the continuous development of Internet technology, front-end frameworks play a vital role in Web development. PHP, Vue and React are three representative front-end frameworks, each with its own unique characteristics and advantages. When choosing which front-end framework to use, developers need to make an informed decision based on project needs, team skills, and personal preferences. This article will compare the characteristics and uses of the three front-end frameworks PHP, Vue and React.

Application of algorithms in the construction of 58 portrait platform Application of algorithms in the construction of 58 portrait platform May 09, 2024 am 09:01 AM

1. Background of the Construction of 58 Portraits Platform First of all, I would like to share with you the background of the construction of the 58 Portrait Platform. 1. The traditional thinking of the traditional profiling platform is no longer enough. Building a user profiling platform relies on data warehouse modeling capabilities to integrate data from multiple business lines to build accurate user portraits; it also requires data mining to understand user behavior, interests and needs, and provide algorithms. side capabilities; finally, it also needs to have data platform capabilities to efficiently store, query and share user profile data and provide profile services. The main difference between a self-built business profiling platform and a middle-office profiling platform is that the self-built profiling platform serves a single business line and can be customized on demand; the mid-office platform serves multiple business lines, has complex modeling, and provides more general capabilities. 2.58 User portraits of the background of Zhongtai portrait construction

See all articles