Compréhension approfondie des algorithmes de planification de tâches dans React

Cet article vous aidera à apprendre React et à acquérir une compréhension approfondie de l'algorithme de planification des tâches dans React. J'espère qu'il vous sera utile !

Vous devez connaître le pool de tâches dans React

Les tâches Fibre dans React, et différentes tâches Fibre ont des priorités différentes pour que React traite en premier les tâches ayant une priorité élevée. Par exemple, les clics et les saisies de l'utilisateur sont des tâches hautement prioritaires, car les opérations de l'utilisateur espèrent certainement avoir des effets immédiats, afin d'améliorer l'expérience utilisateur. Par exemple, la priorité des événements d'animation doit être inférieure. Une fois qu’une nouvelle tâche hautement prioritaire entre dans la file d’attente, React doit d’abord la traiter. [Recommandations associées : Tutoriel vidéo Redis]

Afin de stocker ces tâches, il existe deux pools de tâches dans React.

// Tasks are stored on a min heap
var taskQueue = [];
var timerQueue = [];

taskQueue et timerQueue sont tous deux des tableaux. Le premier stocke les tâches à exécuter immédiatement, tandis que le second stocke les tâches qui peuvent être retardées.

  var newTask = {
    id: taskIdCounter++, // 标记任务id
    callback, // 回调函数
    priorityLevel, // 任务优先级
    startTime, // 任务开始时间，时间点
    expirationTime, // 过期时间，时间点
    sortIndex: -1, // 任务排序，取值来自过期时间，因此值越小，优先级越高
  };

Une fois qu'une nouvelle tâche arrive dans React, currentTime sera utilisé pour enregistrer l'heure actuelle (performance.now() ou Date.now()). Si la tâche a un paramètre de délai, alors l'heure d'exécution de la tâche startTime =). currentTime + délai ; Ensuite, si startTime > currentTime est établi, cela prouve que la tâche peut être reportée, alors la tâche entre dans timerQueue, sinon elle entre dans taskQueue.

Planification des tâches dans React

Comment React trouve-t-il la tâche avec la priorité la plus élevée ? Prenez taskQueue comme exemple. Il s'agit d'un pool de tâches dynamique (file d'attente de tâches) et le formulaire de données est un tableau. Bien sûr, vous pouvez trier par priorité, c'est-à-dire Array.sort Lorsqu'une nouvelle tâche est ajoutée à la file d'attente, elle est triée en premier, puis la tâche ayant la priorité la plus élevée est trouvée et exécutée. Mais la complexité temporelle moyenne d'Array.sort est O(nlogn), ce qui n'est pas la meilleure solution.

La newTask de taskQueue utilise sortIndex pour le tri. Cette valeur est tirée du délai d'expiration, ce qui signifie que plus la tâche prioritaire est élevée, plus elle doit être comprise et exécutée, donc le délai d'expiration sera plus petit, c'est-à-dire plus la priorité est élevée, plus le délai d'expiration est court, plus le sortIndex sera naturellement petit. En fait, C'est une sorte de file d'attente prioritaire.

File d'attente prioritaire

La file d'attente prioritaire est aussi une sorte de file d'attente (D'abord c'est une file d'attente, deuxièmement c'est une file d'attente et une tête de sortie), la seule différence est que l'ordre de sortie de la file d'attente de la priorité la file d'attente est selon la priorité Come; dans certains cas, vous devrez peut-être trouver l'élément le plus petit ou le plus grand dans l'ensemble d'éléments. Vous pouvez utiliser la file d'attente prioritaire ADT pour terminer l'opération. La file d'attente prioritaire ADT est une structure de données qui prend en charge l'insertion et. suppression des opérations de valeur minimale (retourner et supprimer l'élément minimum) ou suppression de l'opération maximale (retourner et supprimer l'élément maximum).

Si le plus petit élément de valeur clé a la priorité la plus élevée, alors cette file d'attente prioritaire est appelée file d'attente à priorité ascendante (c'est-à-dire que le plus petit élément est toujours supprimé en premier). De même, si l'élément avec la plus grande valeur de clé a la priorité la plus élevée, alors ce type de file d'attente prioritaire est appelé file d'attente à priorité décroissante (c'est-à-dire que l'élément le plus grand est toujours supprimé en premier puisque ces deux types sont symétriques, vous n'en avez besoin que) ; pour se concentrer sur l'un d'entre eux, comme la file d'attente prioritaire ascendante.

Par exemple : Lorsque nous achetions des billets, nous faisions tous la queue et nos priorités étaient les mêmes. Celui qui était devant la file d'attente achetait le billet en premier, mais ensuite un soldat est arrivé et il avait un prix plus élevé. priorité, il s'est donc aligné directement devant l'équipe.

Utilisez min tas (petit tas racine, petit tas supérieur...) pour réaliser cette fonction dans React. Cela consiste à transformer la taskQueue en un tas minimum, puis à supprimer la tâche principale pour l'exécution, à empiler la taskQueue et à la conserver en tant que structure de données de tas minimum. Lors de l'insertion d'une nouvelle tâche dans taskQueue, elle doit également être tassée et toujours conservée comme tas minimum.

La relation entre la file d'attente prioritaire et le tas

Certains endroits appellent le tas une file d'attente prioritaire (pas précis). Tout d'abord, il s'agit d'une file d'attente et a les caractéristiques d'une file d'attente, c'est-à-dire "premier entré". premier sorti". Deuxièmement, les éléments de cette file d'attente ont des priorités, et ceux ayant des priorités plus élevées seront classés en premier.

Pour être précis, le tas est un moyen d'implémenter une file d'attente prioritaire. Bien entendu, les files d’attente prioritaires peuvent également être mises en œuvre d’autres manières.

Tas minimum dans React

Nous avons déjà dit que le tri par tas est un tri instable, mais taskQueue espère que ce processus est stable, c'est-à-dire s'il est possible que le délai d'expiration de deux tâches soit le même , puis À ce stade, cela dépend de qui entre en premier dans le pool de tâches, qui est la valeur de l'identifiant de newTask. Chaque fois qu'une nouvelle tâche arrive, l'identifiant sera augmenté de 1.

function compare(a, b) {
  // Compare sort index first, then task id.
  const diff = a.sortIndex - b.sortIndex;
  return diff !== 0 ? diff : a.id - b.id;
}

Min Heap

Avant de comprendre le tas min, passons en revue les connaissances de base.

Arbre binaire

fait référence à un arbre ordonné dont le degré des nœuds dans l'arbre n'est pas supérieur à 2. C'est l'arbre le plus simple et le plus important.

Arbre binaire complet

Un arbre binaire dans lequel tous les nœuds de chaque niveau ont deux nœuds enfants, à l'exception du dernier niveau qui n'a aucun nœud enfant.

D'un point de vue graphique, un arbre binaire complet ressemble à un triangle.

Si le nombre de niveaux d'un arbre binaire est K et que le nombre total de nœuds est (2^k) -1, alors c'est un arbre binaire complet.

Un arbre binaire complet est une "fille avec les deux côtés" et est très parfait, c'est pourquoi on l'appelle un arbre binaire complet.

Arbre binaire parfait

À l'exception des nœuds feuilles, le degré de tous les nœuds est de 2. En d’autres termes, le degré de tous les nœuds ne peut être que 0 ou 2.

Un arbre binaire parfait n'a soit aucun enfant, soit les deux enfants.

Arbre binaire complet VS Arbre binaire parfait

Le texte anglais original de l'arbre binaire complet :
Un arbre binaire complet (FBT) est un arbre dans lequel chaque nœud autre que les feuilles a deux enfants.

L'arbre binaire complet (FBT) est un arbre dans lequel chaque nœud autre que les feuilles a deux enfants.

L'arbre binaire complet (FBT) est un arbre dans lequel chaque nœud autre que les feuilles a deux enfants. texte de l'arbre binaire parfait :

Un arbre binaire parfait (PBT) est un arbre avec tous les nœuds feuilles à la même profondeur. Tous les nœuds internes ont le degré 2.

Tous les livres étrangers font référence aux premiers manuels traduits sur les arbres binaires complets et. arbres binaires parfaits, mais le plus ancien L'article traduit a été mal traduit. Or, en Chine, on ne peut faire des erreurs que lorsqu’ils ont tort (tout le monde a tort, alors celui qui a tort a aussi raison. Par exemple, les lobbyistes…). Si vous souhaitez discuter de ces deux concepts avec des amis étrangers, vous devez y prêter attention.

Arbre binaire complet

Un arbre binaire complet (CBT) est un arbre binaire dans lequel chaque niveau, sauf peut-être le dernier, est complètement rempli et tous les nœuds sont aussi à gauche que possible.

Un arbre avec un profondeur de k Un arbre binaire à n nœuds. Les nœuds de l'arbre sont numérotés de haut en bas et de gauche à droite si le nœud numéroté i (1≤i≤n) est le même que le nœud numéroté i (1≤). i≤n) dans l'arbre binaire complet, les positions des nœuds i dans l'arbre binaire sont les mêmes, alors cet arbre binaire est appelé arbre binaire complet.
• À l'exception du dernier calque, tous les calques sont parfaitement remplis

Tous les nœuds feuilles du dernier calque sont alignés à gauche

Tas

Le tas est un

arbre binaire complet .

Un tas satisfait toujours les propriétés suivantes :
• Un tas est toujours un arbre binaire complet

La valeur d'un nœud dans le tas n'est toujours ni supérieure ni inférieure à la valeur de son nœud parent ;

Vous devez également d'abord le comprendre. Sous le grand tas racine et le petit tas racine, tous les nœuds d'un arbre binaire complet sont supérieurs (ou inférieurs) à ses nœuds enfants, il y a donc deux situations ici, le tas maximum et le tas minimum.

Tas maximum

• Si tous les nœuds ** sont "supérieurs aux" valeurs du nœud enfant, alors ce tas est appelé
"Tas maximum"**, et la valeur maximale du tas est au niveau du nœud racine.

Tas minimum

• Si tous les nœuds** sont "inférieurs à"valeurs du nœud enfant, alors ce tas est appelé
"Tas minimum"**, et la valeur minimale du tas est au niveau du nœud racine .

Un tas est généralement un objet tableau qui peut être considéré comme un arbre binaire complet .

Bien entendu, les arbres binaires peuvent également être représentés par des tableaux.

Implémentation du tas

L'idée principale est de construire d'abord le tas, puis de l'ajuster.

Créer un tas

Pour les arbres binaires (représentation matricielle), nous ajustons de bas en haut, en commençant par **"le premier nœud non-feuille"** et en ajustant vers l'avant. Les règles d'ajustement sont les suivantes :

Build Heap est un processus de complexité temporelle O(n).

① Commencez par le premier nœud non-feuille pour déterminer le swap vers le bas (shiftDown), afin que le nœud actuel et l'enfant puissent conserver les propriétés du tas

② Cependant, le remplacement ordinaire du nœud peut ne pas être un problème si l'échange est interrompu. les propriétés de la structure du tas de l'enfant, puis le nœud échangé doit être à nouveau déplacé vers le bas (shiftDown) jusqu'à ce qu'il s'arrête.

🎜

调整堆

堆构造完成，取第一个堆顶元素为最小(最大)，剩下左右孩子依然满足堆的性值，但是缺个堆顶元素，如果给孩子调上来，可能会调动太多并且可能破坏堆结构。

① 所以索性把最后一个元素放到第一位。这样只需要判断交换下移(shiftDown）,不过需要注意此时整个堆的大小已经发生了变化，我们在逻辑上不会使用被抛弃的位置，所以在设计函数的时候需要附带一个堆大小的参数。

② 重复以上操作，一直堆中所有元素都被取得停止。

而堆算法复杂度的分析上，之前建堆时间复杂度是O(n)。而每次删除堆顶然后需要向下交换，每个个数为logn个。这样复杂度就为O(nlogn)，总的时间复杂度为O(n)+O(nlogn)=O(nlogn)。

堆的应用场景

堆适合维护集合的最值。

堆pop出一个元素后，再次调整获取堆顶元素（也就是第二个最值）的花销比较低，因为pop出元素后，堆是一个半成品，在一个半成品上获取第二个最值的cost当然比较低，时间复杂度为O(logn)，但如果遍历一遍找到第二个最值的话，时间复杂度为O(n)。

代码实现

代码采用Javascript ES6的写法。

代码

class Heap {
    constructor(data, comp) {
       this.data = data ? data : [];
 
       // 比较规则：更加灵活，可以比较数值，也可以比较对象
       this.compartor = comp ? comp : (a-b) => a-b;
 
       // 调整为堆(优先队列)
       this.heapify();
    }
 
    heapify() {
       if(this.size() =0; i--) {
          // 调整堆, 向下调整也可以用递归来实现，这里用迭代来实现
          this.shiftDown(i);
       }
    }
 
    // 向下调整
    shiftDown(i) {
       let left = 2*i +1;
       let right = 2*i +2;
 
       let len = this.size();
       while(i =0 ) {
          let findIndex = i;
          if(this.compartor(this.data[parentIndex], this.data[findIndex]) > 0) {
             findIndex = parentIndex;
          }
 
          if(findIndex !== i) {
             [this.data[i], this.data[findIndex]] = [this.data[findIndex], this.data[i]];
             i = findIndex;
             parentIndex = Math.floor((i-1)/2);
          }
          else {
              break;
          }
       }
    }
 
    // 获取堆中所有元素的个数
    size(){
        return this.data.length;
    }
 
    // 获取堆首部元素
    peek(){
        if(!this.size()) return null;
 
        return this.data[0];
    }
 
    // 往堆中添加一个元素
    push(x){
       this.data.push(x);
       
       this.shiftUp(this.data.length-1);
    }
 
    // 从堆里弹出堆首元素
    pop(){
      if(!this.size()) return null;
 
      let res = this.data[0];
 
      if(this.size() == 1) {
         this.data.pop();
      }
      else {
          this.data[0] = this.data[this.data.length-1];
          this.data.length = this.data.length-1;
          this.shiftDown(0);
      }
 
      return res;
    }
 }

测试

 let arr = [2,9,8,6,3,10,5,7,4,1];
 let comp = (a, b) => a-b;
 let heap = new Heap(arr, comp);
 
 let res = [];
 while(heap.size()) {
    res.push(heap.pop());
 }

 console.log(res);

arr里的元素也可以是一个对象。

React源码部分

React源码中的目录packages/scheduler，就是React的任务调度模块相关的代码。

https://github.com/facebook/react/blob/17.0.2/packages/scheduler/src/Scheduler.js

https://github.com/facebook/react/blob/17.0.2/packages/scheduler/src/SchedulerMinHeap.js

/**
 * Copyright (c) Facebook, Inc. and its affiliates.
 *
 * This source code is licensed under the MIT license found in the
 * LICENSE file in the root directory of this source tree.
 *
 * @flow strict
 */

type Heap = Array<node>;
type Node = {|
  id: number,
  sortIndex: number,
|};

export function push(heap: Heap, node: Node): void {
  const index = heap.length;
  heap.push(node);
  siftUp(heap, node, index);
}

export function peek(heap: Heap): Node | null {
  const first = heap[0];
  return first === undefined ? null : first;
}

export function pop(heap: Heap): Node | null {
  const first = heap[0];
  if (first !== undefined) {
    const last = heap.pop();
    if (last !== first) {
      heap[0] = last;
      siftDown(heap, last, 0);
    }
    return first;
  } else {
    return null;
  }
}

function siftUp(heap, node, i) {
  let index = i;
  while (true) {
    const parentIndex = (index - 1) >>> 1;
    const parent = heap[parentIndex];
    if (parent !== undefined && compare(parent, node) > 0) {
      // The parent is larger. Swap positions.
      heap[parentIndex] = node;
      heap[index] = parent;
      index = parentIndex;
    } else {
      // The parent is smaller. Exit.
      return;
    }
  }
}

function siftDown(heap, node, i) {
  let index = i;
  const length = heap.length;
  while (index <p>我们自己实现的最小堆和React中的实现略有不同，但是思路是一样的，只是代码写法不同而已。</p>
<h2 data-id="heading-22"><strong>总结</strong></h2>
<p>React中的任务调度是用最小堆来实现的，如果我们之前就对最小堆有一定了解，那在学习这块内容的时候就会更快一点。个人认为，前期知识积累是多么重要啊，但是这个过程可能会比较枯燥。 这个时候，是不是觉得自己也会一些算法了，其实这些算法是入门级别的，甚至还没有入门。因为在React的任务调度场景中，要实现的需求是非常明确的，而且要采用什么样的数据结构和算法也是明确的。在实际的一些场景中，我们知道了具体的需求，但是并不知道用什么数据结果和算法，就需要把需求抽象一下，根据抽象的数据模型来设计具体的数据结构和算法，这些才是重点。</p>
<p>更多编程相关知识，请访问：<a href="https://www.php.cn/course.html" target="_blank" textvalue="编程视频">编程视频</a>！！</p></node>

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!