Vertiefte Kenntnisse der Aufgabenplanungsalgorithmen in React

Dieser Artikel wird Ihnen helfen, React zu erlernen und ein tiefgreifendes Verständnis des Aufgabenplanungsalgorithmus in React zu erlangen. Ich hoffe, er wird Ihnen hilfreich sein!

Sie sollten über den Aufgabenpool in React Bescheid wissen.

Fiber-Aufgaben in React haben unterschiedliche Prioritäten, um Aufgaben mit hoher Priorität zuerst zu verarbeiten. Beispielsweise sind die Klicks und Eingaben des Benutzers Aufgaben mit hoher Priorität, da von den Vorgängen des Benutzers auf jeden Fall unmittelbare Auswirkungen erwartet werden, um das Benutzererlebnis zu verbessern. Beispielsweise muss die Priorität von Animationsereignissen niedriger sein. Nachdem eine neue Aufgabe mit hoher Priorität in die Warteschlange gelangt, muss React sie zuerst verarbeiten. [Verwandte Empfehlungen: Redis-Video-Tutorial]

Um diese Aufgaben zu speichern, gibt es in React zwei Aufgabenpools.

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

taskQueue und timerQueue sind beide Arrays. Ersteres speichert Aufgaben, die sofort ausgeführt werden sollen, während letzteres Aufgaben speichert, die verzögert werden können.

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

Sobald eine neue Aufgabe in React eintrifft, wird currentTime verwendet, um die aktuelle Zeit aufzuzeichnen (performance.now() oder Date.now()). Wenn die Aufgabe einen Verzögerungsparameter hat, ist die Ausführungszeit der Aufgabe startTime = aktuelle Zeit + Verzögerung; Wenn als nächstes startTime > currentTime festgelegt ist, wird bewiesen, dass die Aufgabe verschoben werden kann. Anschließend wird die Aufgabe in die timerQueue eingegeben, andernfalls in die taskQueue.

Aufgabenplanung in React

Wie findet React die Aufgabe mit der höchsten Priorität? Nehmen Sie taskQueue als Beispiel. Es handelt sich um einen dynamischen Aufgabenpool (Aufgabenwarteschlange) und die Datenform ist ein Array. Natürlich können Sie nach Priorität sortieren, d. h. Array.sort Wenn eine neue Aufgabe zur Warteschlange hinzugefügt wird, wird sie zuerst sortiert und dann wird die Aufgabe mit der höchsten Priorität gefunden und ausgeführt. Die durchschnittliche Zeitkomplexität von Array.sort beträgt jedoch O (nlogn), was nicht die beste Lösung ist.

Die neue Aufgabe von taskQueue verwendet sortIndex zum Sortieren. Dieser Wert wird aus der Ablaufzeit übernommen. Das heißt, je höher die Prioritätsaufgabe, desto mehr muss sie verstanden und ausgeführt werden, sodass die Ablaufzeit kürzer ist. Je höher die Priorität, desto kleiner die Ablaufzeit, desto kleiner ist natürlich der sortIndex. Tatsächlich Dies ist eine Art Prioritätswarteschlange.

Prioritätswarteschlange

Prioritätswarteschlange ist auch eine Warteschlange (Erstens ist es eine Warteschlange, zweitens ist es eine Warteschlange, zweitens ist es eine Warteschlange, zweitens ist es Tail-In und Head-Out), der einzige Unterschied besteht darin, dass die Reihenfolge beim Entfernen der Prioritätswarteschlange ist Je nach Priorität müssen Sie möglicherweise das kleinste oder größte Element im Elementsatz finden. Sie können den Vorgang mit der Prioritätswarteschlange ADT abschließen Wertoperationen (Minimumelement zurückgeben und löschen) oder Maximalwertoperation (Maximumselement zurückgeben und löschen) ausführen.

Wenn das kleinste Schlüsselwertelement die höchste Priorität hat, wird diese Prioritätswarteschlange als aufsteigende Prioritätswarteschlange bezeichnet (d. h. das kleinste Element wird immer zuerst gelöscht). Wenn das Element mit dem größten Schlüsselwert die höchste Priorität hat, wird diese Art von Prioritätswarteschlange ebenfalls als absteigende Prioritätswarteschlange bezeichnet (dh das größte Element wird immer zuerst gelöscht, da diese beiden Typen symmetrisch sind). um sich auf eine davon zu konzentrieren, beispielsweise auf eine aufsteigende Prioritätswarteschlange.

Zum Beispiel: Als wir Tickets kauften, standen wir alle in der Schlange und unsere Prioritäten waren die gleichen. Wer zuerst in der Warteschlange war, kaufte das Ticket, aber dann kam ein Soldat und der hatte eine höhere Priorität Priorität, also reihte er sich direkt an der Spitze des Teams ein.

Verwenden Sie Min-Heap (kleiner Root-Heap, kleiner Top-Heap ...), um diese Funktion in React zu erreichen. Das heißt, die TaskQueue wird in einen minimalen Heap umgewandelt, dann wird die oberste Aufgabe zur Ausführung herausgenommen, die TaskQueue wird gestapelt und als minimale Heap-Datenstruktur verwaltet. Beim Einfügen einer neuen Aufgabe in die TaskQueue muss diese ebenfalls gehäuft werden und immer als minimaler Heap beibehalten werden. Die Beziehung zwischen Prioritätswarteschlange und Heap. First Out

". Zweitens haben die Elemente in dieser Warteschlange Prioritäten, und diejenigen mit höheren Prioritäten werden zuerst eingestuft.

Um genau zu sein, ist der Heap eine Möglichkeit, eine Prioritätswarteschlange zu implementieren. Selbstverständlich können Priority Queues auch auf andere Art und Weise umgesetzt werden.

Minimaler Heap in React

Wir haben zuvor gesagt, dass die Heap-Sortierung eine instabile Sortierung ist, aber taskQueue hofft, dass dieser Prozess stabil ist, das heißt, wenn es möglich ist, dass die Ablaufzeit zweier Aufgaben gleich ist , dann Zu diesem Zeitpunkt hängt es davon ab, wer zuerst in den Aufgabenpool eintritt. Dies ist der Wert der ID von newTask. Jedes Mal, wenn eine neue Aufgabe eintrifft, wird die ID um 1 erhöht.

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

Bevor wir den Min Heap verstehen, werfen wir einen Blick auf die Grundkenntnisse.

Binärbaum

bezieht sich auf einen geordneten Baum, dessen Knotengrad nicht größer als 2 ist. Es handelt sich um den einfachsten und wichtigsten Baum.

Vollständiger Binärbaum

Ein Binärbaum, in dem alle Knoten auf jeder Ebene zwei untergeordnete Knoten haben, mit Ausnahme der letzten Ebene, die keine untergeordneten Knoten hat.

Aus grafischer Sicht sieht ein vollständiger Binärbaum wie ein Dreieck aus.

Wenn die Anzahl der Ebenen eines Binärbaums K beträgt und die Gesamtzahl der Knoten (2^k) -1 beträgt, dann handelt es sich um einen vollständigen Binärbaum.

Ein vollständiger Binärbaum ist eine „Tochter mit beiden Seiten“ und sehr perfekt, daher wird er als vollständiger Binärbaum bezeichnet.

Perfekter Binärbaum

Mit Ausnahme der Blattknoten beträgt der Grad aller Knoten 2. Mit anderen Worten: Der Grad aller Knoten kann nur 0 oder 2 sein.

Ein perfekter Binärbaum hat entweder keine Kinder oder beide Kinder.

Full Binary Tree VS Perfect Binary Tree

Der englische Originaltext von Full Binary Tree:
Ein Full Binary Tree (FBT) ist ein Baum, in dem jeder Knoten außer den Blättern zwei Kinder hat.

Der englische Originaltext Text des perfekten Binärbaums:

Ein perfekter Binärbaum (PBT) ist ein Baum, bei dem sich alle Blattknoten in der gleichen Tiefe befinden. Alle internen Knoten haben den Grad 2.

Alle ausländischen Bücher beziehen sich auf die frühesten übersetzten Lehrbücher über vollständige Binärbäume und perfekte Binärbäume, aber der früheste Der übersetzte Artikel wurde falsch übersetzt. Jetzt können wir in China nur dann Fehler machen, wenn sie falsch sind (jeder hat Unrecht, dann hat auch die falsche Person Recht. Zum Beispiel Lobbyisten...). Wenn Sie diese beiden Konzepte mit ausländischen Freunden besprechen möchten, sollten Sie aufmerksam sein.

Vollständiger Binärbaum

Ein vollständiger Binärbaum (CBT) ist ein Binärbaum, in dem jede Ebene, außer möglicherweise der letzten, vollständig gefüllt ist und alle Knoten so weit links wie möglich sind.

Ein Baum mit a Tiefe von k Ein Binärbaum mit n Knoten. Die Knoten im Baum sind von oben nach unten und von links nach rechts nummeriert. Wenn der Knoten mit der Nummer i (1≤i≤n) derselbe ist wie der Knoten mit der Nummer i (1≤ i≤n) im vollständigen Binärbaum. Die Positionen der Knoten i im Binärbaum sind gleich, dann wird dieser Binärbaum als vollständiger Binärbaum bezeichnet.

• Bis auf die letzte Ebene sind alle Ebenen perfekt gefüllt.
• Alle Blattknoten der letzten Ebene sind nach links ausgerichtet.

Heap .

Ein Heap erfüllt immer die folgenden Eigenschaften:

Ein Heap ist immer ein vollständiger Binärbaum

Der Wert eines Knotens im Heap ist immer nicht größer oder nicht kleiner als der Wert seines übergeordneten Knotens

• Sie müssen es auch zuerst verstehen. Unter dem großen Root-Heap und dem kleinen Root-Heap sind alle Knoten in einem vollständigen Binärbaum größer (oder kleiner als) seine untergeordneten Knoten. Daher gibt es hier zwei Situationen: den maximalen Heap und den maximalen Heap der minimale Heap.

Maximaler Heap

Wenn alle Knoten ** „größer als“ die Werte der untergeordneten Knoten sind, dann wird dieser Heap

„Maximaler Heap“** genannt und der maximale Wert des Heaps liegt am Wurzelknoten.

• Minimaler Heap

Wenn alle Knoten** „kleiner als“ untergeordnete Knotenwerte sind, dann wird dieser Heap „Minimaler Heap“** genannt und der Mindestwert des Heaps befindet sich am Wurzelknoten .

Ein Heap ist normalerweise ein Array-Objekt, das als

vollständiger Binärbaum

betrachtet werden kann. Natürlich können Binärbäume auch durch Arrays dargestellt werden.

Implementierung des Heaps

Die Kernidee besteht darin, zuerst den Heap zu erstellen und ihn dann anzupassen.

Erstellen Sie einen Heap

Für Binärbäume (Array-Darstellung) passen wir uns von unten nach oben an, beginnend mit **„dem ersten Nicht-Blattknoten“** und passen uns nach vorne an. Die Anpassungsregeln lauten wie folgt:

Build Heap ist ein O(n)-Zeit-Komplexitätsprozess.

① Beginnen Sie mit dem ersten Nicht-Blattknoten, um den Austausch nach unten (shiftDown) zu bestimmen, damit der aktuelle Knoten und das untergeordnete Element die Heap-Eigenschaften beibehalten können.

② Ein normaler Knotenaustausch stellt jedoch möglicherweise kein Problem dar, wenn der Austausch unterbrochen wird die Heap-Struktureigenschaften des untergeordneten Knotens. Dann muss der ausgetauschte Knoten wieder nach unten verschoben werden (shiftDown), bis er stoppt.

调整堆

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

① 所以索性把最后一个元素放到第一位。这样只需要判断交换下移(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>

Das obige ist der detaillierte Inhalt vonVertiefte Kenntnisse der Aufgabenplanungsalgorithmen in React. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!