深入了解React中的任務調度演算法

這篇文章帶大家學習React，深入了解下React中的任務調度演算法，希望對大家有幫助！

React中的任務池

React中的Fiber任務都應該知道吧，而且不同的Fiber任務有不同的優先級，React需要先處理優先順序高的任務。例如，使用者的點擊和輸入，這些都是高優先級的任務，因為使用者的操作肯定希望馬上就會有效果，這樣才能提升使用者體驗。而例如animation事件的優先順序肯定要低一點。新進來的高優先權任務進去佇列後，React需要優先處理。 【相關推薦：Redis影片教學】

為了儲存這些任務，React中有兩個任務池。

// 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記錄當前時間(performance.now()或Date.now())，如果任務有delay參數，那麼任務開始執行時間startTime = currentTime delay;。接下來透過startTime > currentTime如果成立，證明任務是可以延期的，那麼任務進入timerQueue，否則進入taskQueue。

React中的任務調度

React怎麼找到優先順序最高的任務呢，以taskQueue為例，它是動態的任務池（任務隊列），數據形式上就是一個數組。當然可以依照優先順序排序，也就是Array.sort，當有新任務入隊後，先排序，再找出優先順序最高的任務執行。但是Array.sort的平均時間複雜度是O(nlogn)，並不是最好的解決方案。

taskQueue的newTask中排序用的是sortIndex，這個值取自過期時間expirationTime，也就意味著優先權越高的任務越需要理解執行，那麼過期時間就越小，也就是說，優先順序越高，過期時間就越小，sortIndex自然越小。其實，這就是一種優先隊列。

優先隊列

優先隊列也是一個隊列（首先它是一個隊列，其次是尾進頭出），只不過不同的是，優先權佇列的出隊順序是按照優先權來的；在有些情況下，可能需要找到元素集合中的最小或最大元素，可以利用優先權佇列ADT來完成操作，優先隊列ADT是一種資料結構，它支援插入和刪除最小值操作（返回並刪除最小元素）或刪除最大值操作（返回並刪除最大元素）。

如果最小鍵值元素擁有最高的優先權，那麼這種優先權佇列叫做，升序優先佇列（即總是先刪除最小的元素）。類似的，如果最大鍵值元素擁有最高的優先權，那麼這種優先權佇列叫作降序優先權佇列（即總是先刪除最大的元素）；由於這兩種類型時對稱的，所以只需要關注其中一種，如昇序優先隊列。

例如：買車票的時候，我們都在排隊，優先順序是一樣的，誰在隊伍前面，誰就先買票，但是這時候來了個軍人，他的優先順序高，直接就排在了隊伍的最前面。

在React中用最小堆（小根堆，小頂堆。。。）來實現這種函數。就是把taskQueue變成最小堆，然後取出對頂任務執行，對taskQueue堆化，維持它依然是一個最小堆的資料結構。往taskQueue插入新任務的時候，也要進行堆化，始終保持它是一個最小堆。

優先隊列和堆的關係

有些地方稱堆為優先隊列（不準確），首先它是隊列，有隊列的特性，也就是「先進先出」。其次這個佇列中的元素是有優先權的，優先權高的會排在前面。

準確來說，堆是實現優先隊列的一種方式。當然優先隊列還可以用其他方式來實現。

React中的最小堆

#之前我們說過堆排序是不穩定排序，但taskQueue希望這個過程是穩定的，也就是說，如果有可能兩個任務的過期時間一樣，那這個時候就要看誰先進入的任務池了，也就是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的有序樹，它是一種最簡單且最重要的樹。

滿二元樹

除最後一層無任何子節點外，每一層上的所有結點都有兩個子結點的二元樹。

從圖形形狀來看，滿二叉樹外觀上是一個三角形。

如果一個二元樹的層數為K，且結點總數是(2^k) -1 ，則它就是滿二元樹。

滿二叉樹，是“女兒雙全”，非常圓滿，所以叫滿二元樹。

完美二元樹

除去葉子節點, 所有節點的度數都是 2。也就是說，所有的節點的度數只能是0或2。

完美二元樹，要嘛沒有孩子，要嘛兒女雙全。

滿二叉樹VS 完美二叉樹

滿二叉樹的英文原文：
A Full Binary Tree (FBT) is a tree in which every node other than the leaves has two children.

完美二元樹的英文原文：

A Perfect Binary Tree(PBT) is a tree with all leaf nodes at the same depth. All internal nodes have degree 2.

國外的所有書籍參考的是最早翻譯的關於滿二叉樹，和完美二元樹的教材，但是最早翻譯的文章翻譯錯了。現在國內的話，我們只能將錯就錯了（所有人都錯，那錯的也就是對的了。比如說客。。。）。如果要和外國友人討論這兩個概念，就要注意了。

完全二元樹

A Complete Binary Tree （CBT) is a binary tree in which every level,except possibly the last, is completely filled, and all nodes are as far left as possible.

一棵深度為k的有n個結點的二叉樹，對樹中的結點按從上至下、從左到右的順序進行編號，如果編號為i （1≤i≤n）的結點與滿二叉樹中編號為i的結點在二元樹中的位置相同，則這棵二元樹稱為完全二元樹。

• 除了最後一層外, 所有層都完美填充
• 最後一層所有葉子節點靠左對齊

堆

堆是一棵完全二元樹。

堆總是滿足下列性質：

• 堆總是一棵完全二元樹；
• 堆中某個節點的值總是不會大於或不小於其父節點的值；

還要先認識下大根堆和小根堆，完全二叉樹中所有節點均大於(或小於)它的孩子節點，所以這裡就分為兩種情況，最大堆和最小堆。

最大堆

• 如果所有節點**「大於」孩子節點值，那麼這個堆叫做「最大堆」* *，堆的最大值在根節點。

最小堆

• 如果所有節點**「小於」孩子節點值，那麼這個堆叫做「最小堆”**，堆的最小值在根節點。

堆通常是可以被看做一棵 完全二元樹 的陣列物件。 當然，二元樹也可以用陣列表示。

堆的實作

核心思想是，先建堆，然後再調整。

建立堆疊

對於二元樹(陣列表示)，我們從下往上進行調整，從**「第一個非葉子節點」**開始向前調整，對於調整的規則如下：

建堆是一個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 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>

以上是深入了解React中的任務調度演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！