react优先级调度,React的底层调度策略的名称
本文将带您了解React，并进一步了解React中的任务调度算法。希望对你有帮助！
React中的任务池
你应该知道React中所有的纤程任务，不同的纤程任务有不同的优先级。React需要首先处理高优先级的任务。比如用户的点击和输入，这些都是高优先级的任务，因为用户的操作肯定希望有立竿见影的效果，从而提高用户体验。例如，动画事件必须具有较低的优先级。在传入的高优先级任务进入队列后，React需要被赋予优先级。【相关推荐：Redis视频教程】
为了存储这些任务，React中有两个任务池。
//任务存储在最小堆上
var task queue=[]；
var timerQueue=[]；TaskQueue和timerQueue都是数组。前者存储要立即执行的任务，后者存储可以延迟的任务。
var newTask={
Id: taskidCounter，//标记任务Id
回调，//回调函数
PriorityLevel，//任务优先级
开始，//任务开始时间，时间点
ExpirationTime，//到期时间，时间点
SortIndex: -1，//任务排序，值来自到期时间，所以值越小优先级越高。
};一旦一个新任务进入React，它将首先用currentTime记录currentTime (performance.now()或Date.now())。如果任务有延迟参数，那么任务startTime=currentTime delay。接下来，如果startTime currentTime成立，证明任务可以延期，那么任务进入timerQueue，否则进入taskQueue。
React中的任务调度
React如何找到优先级最高的任务？以taskQueue为例。它是一个动态任务池(任务队列)，其数据形式是一个数组。当然也可以按优先级排序，也就是Array.sort当有新任务加入团队时，先进行排序，然后找出优先级最高的任务来执行。但Array.sort的平均时间复杂度为O(nlogn)，并不是最佳方案。
SortIndex用于在taskQueue的newTask中进行排序。这个值取自expirationTime，意味着优先级越高，需要理解和执行的任务越多，到期时间越短。也就是说，优先级越高，到期时间越短，sortIndex自然也就越小。其实这就是一种优先队列。
优先队列
优先级队列也是队列的一种(首先它是一个队列，其次是尾进头出)，但不同的是优先级队列的排队顺序是按优先级来的；在某些情况下，可能需要在元素集中找到最小或最大的元素，这可以通过使用优先级队列ADT来完成，优先级队列ADT是一种支持插入和删除最小值(返回和删除最小元素)或删除最大值(返回和删除最大元素)操作的数据结构。
如果最小的关键元素具有最高的优先级，那么这个优先级队列称为升序优先级队列(即最小的元素总是首先被删除)。同样，如果最大的关键元素具有最高的优先级，那么这个优先级队列称为降序优先级队列(即最大的元素总是首先被删除)；因为这两种类型是对称的，所以我们只需要关注其中的一种，比如升序优先级队列。
例如:买票的时候，我们都在排队，优先级一样。谁排在前面，谁就先买票，可就在这个时候，一个军人来了。他的优先级很高，直接排在队伍的最前面。
在React中使用最小堆(小根桩，小顶桩)。)来实现这个功能。就是把taskQueue变成最小堆，然后取出顶层任务，堆taskQueue维持其数据结构为最小堆。当您向taskQueue中插入一个新任务时，您也应该堆它，并始终保持它是一个最小堆。
优先队列和堆的关系
有些地方把堆叫做优先级队列(不准确)。首先，它是一个队列，具有队列的特征，即“先进先出”。其次，这个队列中的元素是有优先级的，优先级高的先来。
准确的说，堆是一种实现优先级队列的方式。当然，优先级队列也可以通过其他方式实现。
React中的最小堆
之前我们说堆排序是不稳定排序，但是taskQueue希望这个过程是稳定的。也就是说，如果有可能两个任务的到期时间相同，那么这个时候就要看谁先进入任务池，也就是newTask的id的值。每来一个新任务，id就加1。
函数比较(a，b) {
//首先比较排序索引，然后比较任务id。
const diff=a . sort index-b . sort index；
退货差异！==0 ?diff:a . id-b . id；
}
最小堆
在学习最小堆之前，我们先来温习一下基础知识。
二叉树
指节点度不大于2的有序树。它是最简单也是最重要的树。
满二叉树
除了最后一层没有任何子节点外，每一层上的所有节点都有一个二叉树，有两个子节点。
从图形形式上看，全二叉树在外观上是一个三角形。
如果一棵二叉树的层数为k，节点总数为(2 k)-1，则它是一棵完全二叉树。
全二叉树，也就是“两个女儿”，非常完整，所以叫全二叉树。
完美二叉树
除了叶子节点，所有节点的度都是2。也就是说，所有节点的度只能是0或2。
完美二叉树，要么没有孩子，要么都有孩子。
满二叉树 VS 完美二叉树
完整二叉树：
完全二叉树(FBT)是这样一种树，其中除了叶子之外的每个节点都有两个子节点。
完美二叉树英文原文：
完美二叉树(PBT)是所有叶节点深度相同的树。所有内部节点的度都是2。
国外的书都是参考最早翻译的关于满二叉树和完美二叉树的教材，但是最早翻译的文章是错误的。现在在家只能犯错(大家都有错，错的就是对的。比如说客。)。如果你想和外国朋友讨论这两个概念，就要注意了。
完全二叉树
完全二叉树(CBT)是这样一种二叉树，其中除了可能的最后一层之外，每一层都被完全填充，并且所有节点尽可能靠左。
一棵深度为k，节点数为n的二叉树，从上到下，从左到右编号。如果编号为i(1in)的节点与编号为I的节点在全二叉树中的位置相同，则此二叉树称为完全二叉树。
除了最后一层，所有层都被完美填充。最后一层中的所有叶节点都向左对齐。
堆
桩是一个完全二叉树。。
堆总是满足以下属性：
总是堆一个完整的二叉树；堆中节点的值总是不大于或不小于其父节点的值；首先要知道大根堆和小根堆。完整二叉树中的所有节点都比其子节点大(或小)，所以这里有两种情况，最大堆和最小堆。
最大堆
如果所有节点* * "都大于"孩子节点值，那么这个堆叫做"最大堆" * *，则最大堆值位于根节点。
最小堆
如果所有节点* *都“小于”孩子节点值，那么这个堆叫做“最小堆”* *，堆的最小值在根节点。
堆通常是一个可以被看做一棵完全二叉树的数组对象。当然二叉树也可以用数组来表示。
堆的实现
核心思想是先建堆，再调堆。
创建堆
对于二叉树(数组表示)，我们自下而上进行调整，从* *“第一个非叶节点”* *开始，调整的规则如下：
堆构建是一个O(n)时间复杂度的过程。
(1)从第一个非叶节点开始判断exchange的下移，使当前节点及其子节点保持堆属性。
不过普通的节点置换可能就可以了。如果交换破坏了子堆的结构性质，那么被交换的节点将再次下移，直到它停止。
调整堆
堆的构造完成，第一个堆顶元素取最小值(最大值)。剩下的子元素仍然满足堆的属性值，但是缺少一个堆顶元素，如果转移到子元素，可能会对堆结构造成过多的移动和破坏。
所以干脆把最后一个元素放在第一位。这个只需要判断exchange的shiftDown，但是需要注意的是，此时整个堆的大小已经发生了变化。我们在逻辑上不会使用废弃的位置，所以在设计函数时需要附加一个堆大小参数。
重复上述操作，直到堆中的所有元素都停止。
在堆算法的复杂度分析上，前次堆构建时间的复杂度为O(n)。每次删除堆顶都需要向下交换，每个数字都是logn。所以复杂度为O(nlogn)，总时间复杂度为O(n) O(nlogn)=O(nlogn)。
堆的应用场景
堆适合维护集合的最大值。
pop堆出一个元素后，再次调整顶层元素(也就是次高值)的成本相对较低，因为pop堆出一个元素后，堆的就是半成品，在一个半成品上获得次高值的成本当然相对较低，时间复杂度为O(logn)，但如果通过遍历找到次高值，时间复杂度为O(n)。
代码实现
代码是用Javascript ES6编写的。
代码
类堆{
构造器(数据，组件){
this.data=数据？数据：[]；
//比较规则：更灵活，可以比较值和对象。
this.compartor=comp？comp:(a-b)=a-b；
//调整到堆(优先级队列)
this . hea pify()；
}
heapify() {
if(this.size()=1)返回；
//从第一个非叶节点开始调整，或者从最后一个元素开始调整。
for(让I=math . floor((this . size()-2)/2)；I=0；我- ) {
//调整堆。向下调整也可以通过递归实现，这里是通过迭代实现。
this . shift down(I)；
}
}
//向下调整
下移(i) {
let left=2 * I 1；
let right=2 * i 2
设len=this . size()；
while(i len) {
设find index=I；
//左边的孩子“更大”
if(left len this . comparator(this . data[left]，this.data[findIndex]) 0) {
findIndex=left
}
//右边的孩子“更大”
if(right len this . comparator(this . data[right]，this.data[findIndex]) 0) {
findIndex=right
}
如果(我！==findIndex) {
//当前节点与更大的值交换
[this.data[i]，this . data[find index]]=[this . data[find index]，this . data[I]]；
//调整完这一层，可能会影响到下层堆的特性，所以要继续调整下层(迭代实现或者递归实现)。
i=findIndex
left=2 * I 1；
右=2 * I ^ 2；
}
否则{
//如果不需要调整，就跳出去(必须跳出去，否则循环无法结束)
打破；
}
}
}
//向上调整
上移(i){
//查找父级的下标
let parent index=math . floor((I-1)/2)；
//最高调整到0
while(parentIndex=0 ) {
设find index=I；
if(this . compartor(this . data[parent index]，this.data[findIndex]) 0) {
findIndex=parentIndex
}
if(findIndex！==i) {
[this.data[i]，this . data[find index]]=[this . data[find index]，this . data[I]]；
i=findIndex
parent index=math . floor((I-1)/2)；
}
否则{
打破；
}
}
}
//获取堆中所有元素的数量
size(){
返回this . data . length；
}
//获取堆头元素
peek(){
如果(！this.size())返回null
返回this . data[0]；
}
//向堆中添加元素
推动(x){
this . data . push(x)；
this . shift up(this . data . length-1)；
}
//从堆中弹出header元素
pop(){
如果(！this.size())返回null
设RES=this . data[0]；
if(this.size()==1) {
this . data . pop()；
}
否则{
this . data[0]=this . data[this . data . length-1]；
this . data . length=this . data . length-1；
这个。下移(0)；
}
返回表示留数
}
}
测试
let arr=[2，9，8，6，3，10，5，7，4，1]；
设comp=(a，b)=a-b；
let heap=new Heap(arr，comp)；
设RES=[]；
while(heap.size()) {
RES . push(堆。pop())；
}
控制台。日志(分辨率)；到达)里的元素也可以是一个对象。
React源码部分
反应源码中的目录包/调度程序，就是反应的任务调度模块相关的代码。
/**
*版权所有(三)脸书公司及其附属公司。
*
*此源代码在麻省理工学院许可证下获得许可，可在
*许可证文件位于该源树的根目录中。
*
* @流量严格
*/
类型Heap=ArrayNode
类型节点={
id:数字，
排序索引：数字，
};
导出函数推送(堆：堆，节点：节点):void {
常量索引=堆.长度
堆。推送(节点)；
siftUp(堆、节点、索引);
}
导出函数peek(heap: Heap): Node null {
const first=heap[0]；
先返回===未定义？空：第一；
}
导出函数pop(heap: Heap): Node null {
const first=heap[0]；
如果（先！==未定义){
const last=堆。pop()；
如果（最后！==第一){
heap[0]=last；
siftDown(heap，last，0)；
}
先退；
}否则{
返回空
}
}
函数siftUp(堆，节点，i) {
设index=I；
while (true) {
const父索引=(index-1)1；
const parent=heap[父索引]；
如果（家长！==未定义的比较（父节点，节点)0) {
//父级更大。交换位置。
heap[父索引]=node；
heap[index]=parent；
index=parentIndex
}否则{
//父级更小。退出。
返回；
}
}
}
函数siftDown(堆，节点，i) {
设index=I；
常量长度=堆.长度
而(索引长度){
const left index=(index 1)* 2-1；
const left=heap[左索引]；
const右索引=左索引1；
const right=heap[右索引]；
//如果左侧或右侧节点较小，则与其中较小的节点交换。
如果（左！==未定义的比较（左，节点)0) {
如果（对！==未定义的比较（右，左)0) {
堆[索引]=右；
heap[右索引]=node；
指数=右指数
}否则{
堆[索引]=左；
heap[左索引]=node；
指数=左指数
}
} else if(对！==未定义的比较（右，节点)0) {
堆[索引]=右；
heap[右索引]=node；
指数=右指数
}否则{
//两个孩子都不小。退出。
返回；
}
}
}
函数比较(a，b) {
//首先比较排序索引，然后比较任务身份证.
const diff=a .排序索引-b .排序索引；
退货差异！==0 ?diff:a . id-b . id；
}我们自己实现的最小堆和反应中的实现略有不同，但是思路是一样的，只是代码写法不同而已。
总结
反应中的任务调度是用最小堆来实现的，如果我们之前就对最小堆有一定了解，那在学习这块内容的时候就会更快一点。个人认为，前期知识积累是多么重要啊，但是这个过程可能会比较枯燥。这个时候，是不是觉得自己也会一些算法了，其实这些算法是入门级别的，甚至还没有入门。因为在反应的任务调度场景中，要实现的需求是非常明确的，而且要采用什么样的数据结构和算法也是明确的。在实际的一些场景中，我们知道了具体的需求，但是并不知道用什么数据结果和算法，就需要把需求抽象一下，根据抽象的数据模型来设计具体的数据结构和算法，这些才是重点。
更多编程相关知识，请访问：编程视频！以上就是深入了解反应中的任务调度算法的详细内容，更多请关注我们其它相关文章！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。