Pemahaman mendalam tentang algoritma penjadualan tugas dalam React

Artikel ini akan mengajar anda tentang React dan memberi anda pemahaman yang mendalam tentang algoritma penjadualan tugas dalam React, saya harap ia akan membantu anda!

Komsil tugas dalam React

Anda harus tahu tentang tugas Fiber dalam React, dan tugas Fiber berbeza mempunyai Keutamaan, React yang berbeza perlu memproses tugasan dengan keutamaan yang tinggi terlebih dahulu. Sebagai contoh, klik dan input pengguna adalah tugas keutamaan tinggi, kerana operasi pengguna pastinya berharap untuk memberi kesan serta-merta, untuk meningkatkan pengalaman pengguna. Sebagai contoh, keutamaan acara animasi mestilah lebih rendah. Selepas tugas keutamaan tinggi baharu memasuki baris gilir, React perlu memprosesnya terlebih dahulu. [Cadangan berkaitan: Tutorial video Redis]

Untuk menyimpan tugasan ini, terdapat dua kumpulan tugasan dalam React.

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

TaskQueue dan timerQueue ialah kedua-dua tatasusunan menyimpan tugasan untuk dilaksanakan serta-merta, manakala yang terakhir menyimpan tugasan yang boleh ditangguhkan.

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

Sebaik sahaja tugasan baharu masuk dalam React, currentTime akan digunakan untuk merekodkan masa semasa (performance.now() atau Date.now() Jika tugasan mempunyai parameter kelewatan, maka tugas bermula masa pelaksanaan masa mulaMasa = kelewatan masa semasa;. Seterusnya, jika startTime > currentTime diwujudkan, ia membuktikan bahawa tugas itu boleh ditangguhkan, maka tugas itu memasuki timerQueue, jika tidak, ia memasuki taskQueue.

Penjadualan Tugas dalam React

Bagaimana React mencari tugasan keutamaan tertinggi sebagai contoh ia adalah tatasusunan. Sudah tentu, anda boleh mengisih mengikut keutamaan, iaitu, Array.sort Apabila tugasan baharu ditambahkan pada baris gilir, ia diisih dahulu, dan kemudian tugas dengan keutamaan tertinggi ditemui dan dilaksanakan. Tetapi purata kerumitan masa Array.sort ialah O(nlogn), yang bukan penyelesaian terbaik.

Task baru taskQueue menggunakan sortIndex untuk mengisih Nilai ini diambil daripada masa tamat tempoh, yang bermaksud semakin tinggi tugasan keutamaan, lebih banyak tugasan itu perlu difahami dan dilaksanakan, jadi masa tamat tempoh akan menjadi lebih kecil. Dalam erti kata lain, Semakin tinggi keutamaan, semakin kecil masa tamat tempoh, dan semakin kecil sortIndex secara semula jadi. Sebenarnya, ini adalah sejenis baris gilir keutamaan.

Barisan keutamaan

Baris gilir keutamaan juga merupakan sejenis baris gilir (Pertama baris gilir, kedua tail-in-head out ), satu-satunya perbezaan ialah susunan nyah gilir keutamaan adalah berdasarkan keutamaan, dalam sesetengah kes, anda mungkin perlu mencari elemen terkecil atau terbesar dalam set elemen, dan anda boleh gunakan baris gilir keutamaan ADT untuk menyelesaikan operasi , baris gilir keutamaan ADT ialah struktur data yang menyokong memasukkan dan memadam operasi minimum (kembali dan padam elemen terkecil) atau memadam operasi maksimum (kembali dan padam elemen terbesar).

Jika elemen kunci terkecil mempunyai keutamaan tertinggi, maka baris gilir keutamaan ini dipanggil baris gilir keutamaan menaik (iaitu, elemen terkecil sentiasa dipadamkan dahulu). Begitu juga, jika elemen dengan nilai kunci terbesar mempunyai keutamaan tertinggi, maka barisan keutamaan jenis ini dipanggil barisan keutamaan menurun (iaitu, elemen terbesar sentiasa dipadamkan dahulu kerana kedua-dua jenis ini adalah simetri, anda hanya perlu untuk memberi tumpuan kepada salah satu daripadanya, seperti barisan keutamaan menaik.

Contohnya: Semasa kami membeli tiket, kami semua beratur dan keutamaan adalah sama, siapa yang berada di hadapan barisan akan membeli tiket dahulu, tetapi kemudian seorang askar datang dan dia mempunyai keutamaan tinggi dan terus berada di hadapan barisan.

Gunakan timbunan minimum (timbunan akar kecil, timbunan atas kecil...) untuk mencapai fungsi ini dalam React. Iaitu untuk menukar taskQueue menjadi timbunan minimum, kemudian keluarkan tugas teratas untuk pelaksanaan, timbunkan taskQueue dan mengekalkannya sebagai struktur data timbunan minimum. Apabila memasukkan tugasan baharu ke dalam taskQueue, ia juga mesti ditimbun dan sentiasa menyimpannya sebagai timbunan minimum.

Hubungan antara baris gilir keutamaan dan timbunan

Sesetengah tempat memanggil timbunan baris gilir keutamaan (tidak tepat Pertama sekali, ia adalah baris gilir dan mempunyai ciri-ciri). baris gilir, iaitu, "Masuk dahulu, keluar dahulu". Kedua, elemen dalam baris gilir ini mempunyai keutamaan, dan mereka yang mempunyai keutamaan yang lebih tinggi akan diletakkan pada kedudukan pertama.

Tepatnya, timbunan ialah cara untuk melaksanakan baris gilir keutamaan. Sudah tentu, barisan keutamaan juga boleh dilaksanakan dengan cara lain.

Timbunan minimum dalam React

Kami berkata sebelum ini bahawa jenis timbunan adalah jenis yang tidak stabil, tetapi taskQueue berharap proses ini stabil Dengan kata lain, jika ada kemungkinan masa tamat dua tugasan adalah sama, maka ia bergantung kepada siapa yang memasuki kumpulan tugas dahulu, iaitu nilai id newTask Setiap kali tugasan baru datang, id akan meningkat sebanyak 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;
}

Timbunan Minimum

Sebelum memahami timbunan minimum, mari semak pengetahuan asas.

Pokok binari

merujuk kepada pokok tersusun di mana darjah nod dalam pokok itu tidak lebih daripada 2. Ia adalah pokok yang paling ringkas dan paling penting.

Pokok binari penuh

Pokok binari di mana semua nod pada setiap peringkat mempunyai dua nod anak kecuali tahap terakhir yang tidak mempunyai sebarang nod anak.

Dari perspektif grafik, pokok binari penuh kelihatan seperti segi tiga.

Jika bilangan aras pokok binari ialah K dan jumlah bilangan nod ialah (2^k) -1, maka ia adalah pokok binari penuh.

Pokok binari penuh ialah "anak perempuan dengan kedua-dua belah" dan sangat sempurna, jadi ia dipanggil pokok binari penuh.

Pokok binari sempurna

Tidak termasuk nod daun, darjah semua nod ialah 2. Dengan kata lain, darjah semua nod hanya boleh 0 atau 2.

Pokok binari yang sempurna tidak mempunyai anak atau kedua-dua anak.

Pokok Perduaan Penuh VS Pokok Perduaan Sempurna

Teks asal Bahasa Inggeris Pokok Perduaan Penuh:
Pokok Perduaan Penuh (FBT) ialah pokok di mana setiap nod selain daripada daun mempunyai dua anak.

Teks asal Bahasa Inggeris Pokok Binari Sempurna:

Pokok Binari Sempurna(PBT) ialah pokok dengan semua nod daun pada kedalaman yang sama nod dalaman mempunyai darjah 2.

Semua buku asing merujuk kepada buku teks terjemahan terawal pada pokok binari penuh dan pokok binari sempurna, tetapi artikel terjemahan terawal diterjemah secara salah. Sekarang di China, kita hanya boleh melakukan kesilapan apabila mereka salah (semua orang salah, maka orang yang salah juga betul. Contohnya, pelobi...). Jika anda ingin membincangkan dua konsep ini dengan rakan asing, anda harus berhati-hati.

Pokok Perduaan Lengkap

Pokok Perduaan Lengkap (CBT) ialah pokok perduaan di mana setiap peringkat, kecuali mungkin yang terakhir, diisi sepenuhnya, dan semua nod sejauh kiri yang mungkin.

Sebuah pokok binari dengan n nod kedalaman k Nod dalam pokok itu dinomborkan dari atas ke bawah dan dari kiri ke kanan Jika nombor itu i Nod (1≤i ≤n) mempunyai kedudukan yang sama dalam pokok binari seperti nod bernombor i dalam pokok binari penuh, maka pokok binari ini dipanggil pokok binari lengkap.

• Kecuali lapisan terakhir, semua lapisan diisi dengan sempurna
• Semua nod daun lapisan terakhir dijajarkan ke kiri

Timbunan

Timbunan ialah pokok binari lengkap.

Timbunan sentiasa memenuhi sifat berikut:

• Timbunan sentiasa pokok binari lengkap
• Nilai nod dalam timbunan ialah sentiasa tidak lebih besar daripada Atau tidak kurang daripada nilai nod induknya;

Kita mesti memahami timbunan akar besar dan timbunan akar kecil Semua nod dalam pokok binari yang lengkap adalah lebih besar daripada (atau kurang daripada) nod anaknya, jadi di sini kita bahagikan Terdapat dua situasi, timbunan maks dan timbunan min.

Timbunan maksimum

• Jika semua nod ** adalah "lebih besar daripada" nilai nod anak , maka timbunan ini dipanggil " timbunan maks"* *, nilai maksimum timbunan adalah pada nod akar.

Timbunan minimum

• Jika semua nod** adalah "kurang daripada" nilai nod anak, maka timbunan ini dipanggil "Timbunan min"**, nilai minimum timbunan adalah pada nod akar.

Timbunan biasanya merupakan objek tatasusunan yang boleh dilihat sebagai pokok binari lengkap . Sudah tentu, pokok binari juga boleh diwakili oleh tatasusunan.

Pelaksanaan timbunan

Idea teras ialah membina timbunan dahulu dan kemudian melaraskannya.

Buat timbunan

Untuk pokok binari (perwakilan tatasusunan), kami melaraskan dari bawah ke atas, bermula dari **"nod bukan daun pertama"** kepada Sebelum pelarasan, peraturan untuk pelarasan adalah seperti berikut:

Membina timbunan ialah proses kerumitan masa O(n).

① Mulakan dari nod bukan daun pertama untuk menilai swap ke bawah (shiftDown), supaya nod semasa dan kanak-kanak boleh mengekalkan sifat timbunan

② Tetapi penggantian nod biasa mungkin tidak menjadi masalah, jika Jika pertukaran memecahkan sifat struktur timbunan kanak-kanak, maka nod yang ditukar mesti dianjak ke bawah semula (shiftDown) sehingga ia berhenti.

调整堆

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

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

Atas ialah kandungan terperinci Pemahaman mendalam tentang algoritma penjadualan tugas dalam React. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!