React のタスク スケジューリング アルゴリズムについての深い理解

この記事では、React について説明し、React のタスク スケジューリング アルゴリズムについて詳しく説明します。お役に立てば幸いです。

React のタスク プール

React の Fiber タスクについて知っておく必要があります。Fibre タスクが異なれば優先順位も異なります。React優先度の高いタスクを最初に処理する必要があります。たとえば、ユーザーのクリックと入力は、ユーザー エクスペリエンスを向上させるために、ユーザーの操作が即座に効果をもたらすことが確実に求められるため、優先度の高いタスクです。たとえば、アニメーション イベントの優先順位は低くする必要があります。新しい優先度の高いタスクがキューに入ったら、React は最初にそれを処理する必要があります。 [関連する推奨事項: Redis ビデオ チュートリアル ]

これらのタスクを保存するために、React には 2 つのタスク プールがあります。

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

taskQueue と timerQueue はどちらも配列で、前者はすぐに実行するタスクを格納し、後者は遅延する可能性のあるタスクを格納します。

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

React に新しいタスクが来ると、currentTime を使用して現在時刻が記録されます (パフォーマンス.now() または Date.now())。タスクに遅延パラメーターがある場合、タスクが開始されます。実行時間 startTime = currentTime 遅延;。次に、startTime > currentTime が成立する場合、タスクを延期できることが証明され、タスクは timerQueue に入り、そうでない場合は taskQueue に入ります。

React でのタスク スケジューリング

React はどのようにして最も優先度の高いタスクを見つけますか? taskQueue を例にとります。これは動的タスク プール (タスク キュー) であり、形式的にはデータですそれは配列です。もちろん、優先度に従ってソートすることもできます (Array.sort)。新しいタスクがキューに追加されると、最初にソートされ、次に最も優先度の高いタスクが検索されて実行されます。ただし、Array.sort の平均時間計算量は O(nlogn) であり、これは最良の解決策ではありません。

TaskQueue の newTask は並べ替えに sortIndex を使用します。この値は有効期限から取得されます。つまり、優先度が高いタスクほど理解して実行する必要があるため、有効期限は短くなります。つまり、優先順位が高くなるほど有効期限は短くなり、当然、sortIndex も小さくなります。実際、これは優先キューです。

プライオリティ キュー

プライオリティ キューもキューです (最初はキューで、その後にテールインが続きます) -head out)、唯一の違いは、優先キューのデキュー順序が優先度に基づいていることです。場合によっては、要素セット内の最小または最大の要素を見つける必要があり、優先度を使用できます。キュー ADT は、操作を完了するためのキュー ADT です。優先キュー ADT は、挿入および削除の最小操作 (最小の要素を返して削除) または最大の削除操作 (最大の要素を返して削除) をサポートするデータ構造です。

最小のキー値要素の優先順位が最も高い場合、この優先キューは昇順優先キューと呼ばれます (つまり、最小の要素が常に最初に削除されます)。同様に、最大のキー値を持つ要素の優先順位が最も高い場合、このタイプの優先キューは降順優先キューと呼ばれます (つまり、最大の要素が常に最初に削除されます)。これら 2 つのタイプは対称であるため、必要なのは優先順位の高いキューなど、そのうちの 1 つに焦点を当てます。

例: チケットを購入するとき、私たちは全員列に並んでおり、優先順位は同じでした。列の前にいた人が最初にチケットを購入しますが、その後にチケットを購入します。兵士が来て、彼は優先順位が高く、列の先頭にいます。

React でこの機能を実現するには、minimum heap (小さなルート ヒープ、小さなトップ ヒープなど) を使用します。つまり、taskQueue を最小ヒープに変換し、実行のために最上位のタスクを取り出し、taskQueue をヒープし、それを最小ヒープ データ構造として維持します。新しいタスクを taskQueue に挿入するときは、タスクをヒープ化し、常に最小のヒープとして保持する必要があります。

プライオリティキューとヒープの関係

ヒープのことをプライオリティキューと呼ぶところもあります(正確ではありません)。キューの、つまり「FIFO」。次に、このキュー内の要素には優先順位があり、優先順位の高い要素が最初にランク付けされます。

正確に言うと、ヒープは優先キューを実装する方法です。もちろん、優先キューは他の方法でも実装できます。

React の最小ヒープ

ヒープ ソートは不安定なソートであると前に述べましたが、taskQueue はこのプロセスが安定していることを望んでいます。言い換えれば、2 つのタスクの有効期限が同じである可能性がある場合、それは誰が最初にタスク プールに入るのか、つまり newTask の ID の値に依存します。新しいタスクが来るたびに、ID は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;
}

最小ヒープ

最小ヒープを理解する前に、基本的な知識を確認してください。

バイナリ ツリー

は、ツリー内のノードの次数が 2 以下である順序付きツリーを指します。これは、最も単純で最も重要なツリーです。

完全なバイナリ ツリー

子ノードを持たない最後のレベルを除き、各レベルのすべてのノードが 2 つの子ノードを持つバイナリ ツリー。

グラフィカルな観点から見ると、完全なバイナリ ツリーは三角形のように見えます。

バイナリ ツリーのレベル数が K で、ノードの総数が (2^k) -1 の場合、それは完全なバイナリ ツリーです。

完全二分木は「両面を持った娘」であり、非常に完全であるため、完全二分木と呼ばれます。

完全二分木

葉ノードを除き、すべてのノードの次数は 2 です。つまり、すべてのノードの次数は 0 または 2 のみになります。

完璧なバイナリ ツリーには、子がないか、両方の子が存在します。

フル バイナリ ツリー VS パーフェクト バイナリ ツリー

フル バイナリ ツリーの英語原文:
フル バイナリ ツリー (FBT) は、他のすべてのノードが含まれるツリーです。

完璧なバイナリ ツリーの英語の原文:

パーフェクト バイナリ ツリー(PBT)は、すべての葉ノードが同じ深さにあるツリーです。すべての内部ノード学位は 2 です。

すべての外国の本は、完全二分木と完全二分木に関する最も初期に翻訳された教科書を参照していますが、最も初期に翻訳された記事は誤って翻訳されています。現在、中国では、間違いを犯すことができるのは、間違いが間違っている場合だけです（誰もが間違っているので、間違っている人も正しいことになります。たとえば、ロビイスト…）。外国人の友人とこれら 2 つの概念について話し合いたい場合は、注意する必要があります。

完全バイナリ ツリー

完全バイナリ ツリー (CBT) は、最後のレベルを除くすべてのレベルが完全に埋められ、すべてのノードが完全に満たされているバイナリ ツリーです。できるだけ左に。

深さ k の n 個のノードを持つバイナリ ツリー。ツリー内のノードには上から下、左から右の順に番号が付けられます。番号が i の場合、ノード (1≤i) ≤n) が完全二分木における i 番号のノードと二分木内で同じ位置にある場合、この二分木は完全二分木と呼ばれます。

• 最後のレイヤーを除いて、すべてのレイヤーは完全に塗りつぶされています
• 最後のレイヤーのすべてのリーフ ノードは左に揃えられています

ヒープ

ヒープは、完全なバイナリ ツリーです。

ヒープは常に次のプロパティを満たします:

• ヒープは常に完全なバイナリ ツリーです;
• ヒープ内のノードの値は次のとおりです。常に親ノードの値より大きくない、またはそれより小さくない;

また、最初に大きなルート ヒープと小さなルート ヒープについて理解する必要もあります。完全なバイナリ ツリー内のすべてのノードは、次の値より大きくなります。最大ヒープと最小ヒープの 2 つの状況があります。

最大ヒープ

• すべてのノード**が子ノードの値 より「大きい」場合、このヒープは と呼ばれます。最大ヒープ」* *、ヒープの最大値はルート ノードでの値です。

最小ヒープ

• すべてのノード ** が 子ノードの値より「小さい」場合、このヒープは と呼ばれます。 「最小ヒープ」**、ヒープの最小値はルート ノードにあります。

ヒープは通常、 完全なバイナリ ツリー として表示できる配列オブジェクトです。 もちろん、バイナリ ツリーは配列で表すこともできます。

ヒープの実装

中心となる考え方は、最初にヒープを構築してからそれを調整することです。

ヒープの作成

バイナリ ツリー (配列表現) の場合、**「最初の非リーフ ノード」** から開始して下から上に調整します。調整前の調整ルールは次のとおりです。

ヒープの構築は O(n) 時間かかるプロセスです。

①最初の非リーフ ノードから開始してスワップ ダウン (shiftDown) を決定し、現在のノードと子がヒープの性質を維持できるようにします。

②ただし、通常のノードの置換はできない場合があります。問題は、交換によって子ヒープ構造の性質が破壊された場合、交換されたノードを停止するまで再度シフトダウン (shiftDown) する必要がある場合です。

调整堆

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

① 所以索性把最后一个元素放到第一位。这样只需要判断交换下移(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 id="strong-总结-strong"><strong>总结</strong></h2>
<p>React中的任务调度是用最小堆来实现的，如果我们之前就对最小堆有一定了解，那在学习这块内容的时候就会更快一点。个人认为，前期知识积累是多么重要啊，但是这个过程可能会比较枯燥。 这个时候，是不是觉得自己也会一些算法了，其实这些算法是入门级别的，甚至还没有入门。因为在React的任务调度场景中，要实现的需求是非常明确的，而且要采用什么样的数据结构和算法也是明确的。在实际的一些场景中，我们知道了具体的需求，但是并不知道用什么数据结果和算法，就需要把需求抽象一下，根据抽象的数据模型来设计具体的数据结构和算法，这些才是重点。</p>
<p>更多编程相关知识，请访问：<a href="https://www.php.cn/course.html" target="_blank" textvalue="编程视频">编程视频</a>！！</p></node>

以上がReact のタスク スケジューリング アルゴリズムについての深い理解の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。