React의 작업 스케줄링 알고리즘에 대한 심층적인 이해
- 青灯夜游앞으로
- 2022-07-08 20:30:482192검색
이 글은 React를 배우고 React의 작업 스케줄링 알고리즘을 심층적으로 이해하는 데 도움이 되기를 바랍니다.
React의 작업 풀에 대해 알아야 합니다
Fiber 작업마다 React는 우선 순위가 높은 작업을 먼저 처리해야 합니다. 예를 들어, 사용자의 클릭과 입력은 우선순위가 높은 작업입니다. 왜냐하면 사용자의 작업은 확실히 즉각적인 효과를 가져서 사용자 경험을 향상시키기를 원하기 때문입니다. 예를 들어 애니메이션 이벤트의 우선순위는 낮아야 합니다. 우선순위가 높은 새로운 작업이 대기열에 들어간 후 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())을 기록합니다. 작업에 지연 매개변수가 있으면 작업 시작 실행 시간 startTime = 현재시간 + 지연; 다음으로, startTime > currentTime이 설정되면 작업을 연기할 수 있음을 증명하고 작업은 타이머큐에 들어가고, 그렇지 않으면 taskQueue에 들어갑니다.
React의 작업 예약
React는 어떻게 우선순위가 가장 높은 작업을 찾나요? taskQueue를 예로 들면, 동적 작업 풀(작업 대기열)이고 데이터 형식은 배열입니다. 물론 우선순위에 따라 정렬할 수도 있는데, 즉 Array.sort 처럼 새로운 작업이 큐에 추가되면 먼저 정렬한 뒤 우선순위가 가장 높은 작업을 찾아 실행한다. 그러나 Array.sort의 평균 시간 복잡도는 O(nlogn)이므로 최선의 해결책은 아닙니다.
taskQueue의 newTask는 정렬을 위해 sortIndex를 사용합니다. 이 값은 만료 시간에서 가져옵니다. 즉, 우선 순위가 높은 작업일수록 더 많은 이해와 실행이 필요하므로 만료 시간은 더 작아집니다. 우선 순위가 높을수록 만료 시간이 짧을수록 sortIndex는 자연스럽게 작아집니다. 사실 이것은 일종의 우선순위 대기열입니다.
우선순위 대기열
우선순위 대기열도 대기열입니다(먼저 대기열이고 두 번째로 tail in 및 head out입니다). 유일한 차이점은 우선순위 대기열에서 대기열을 빼는 순서가 우선순위에 따라 요소 세트에서 가장 작거나 가장 큰 요소를 찾아야 할 수도 있습니다. 우선순위 큐 ADT는 최소 삽입 및 삭제를 지원하는 데이터 구조입니다. value 연산(가장 작은 요소 반환 및 삭제) 또는 delete max 연산(가장 큰 요소 반환 및 삭제).
가장 작은 키 값 요소의 우선순위가 가장 높은 경우 이 우선순위 대기열을 오름차순 우선순위 대기열이라고 합니다(즉, 가장 작은 요소가 항상 먼저 삭제됩니다). 마찬가지로, 가장 큰 키 값을 가진 요소가 가장 높은 우선순위를 갖는 경우 이 유형의 우선순위 큐를 내림차순 우선순위 큐라고 합니다(즉, 가장 큰 요소가 항상 먼저 삭제됩니다). 이 두 유형은 대칭적이므로 사용자에게만 필요합니다. 오름차순 우선순위 큐와 같은 종류 중 하나에 집중합니다.
예를 들어: 우리가 티켓을 구매할 때 모두 줄을 서 있었고, 우선순위는 같았습니다. 줄 앞에 있는 사람이 먼저 티켓을 구매했는데, 그다음에 군인이 왔고 그 사람의 순위가 더 높았습니다. 그래서 그는 팀 맨 앞에 줄을 섰습니다.
React에서 이 기능을 구현하려면 min heap(작은 루트 힙, 작은 상단 힙...)을 사용하세요. 즉, taskQueue를 최소 힙으로 전환한 다음 실행을 위해 최상위 작업을 꺼내고 taskQueue를 힙하고 이를 최소 힙 데이터 구조로 유지하는 것입니다. taskQueue에 새 작업을 삽입할 때 힙도 있어야 하며 항상 최소 힙으로 유지해야 합니다.
우선순위 큐와 힙의 관계
힙을 우선순위 큐라고 부르는 곳도 있습니다(정확하지 않음). 우선 큐이며 큐의 특성을 가지고 있습니다. 즉, "first in, 먼저 나가". 둘째, 이 대기열의 요소에는 우선 순위가 있으며 우선 순위가 높은 요소가 먼저 순위가 매겨집니다.
정확하게 말하면 힙은 우선순위 큐를 구현하는 방법입니다. 물론 우선순위 큐는 다른 방식으로도 구현될 수 있습니다.
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;
}
Min Heap
최소 힙을 이해하기 전에 기본 지식을 복습해보겠습니다.
이진 트리
는 트리의 노드 차수가 2보다 크지 않은 정렬된 트리를 말합니다. 가장 단순하고 중요한 트리입니다.
완전 이진 트리
자식 노드가 없는 마지막 수준을 제외하고 각 수준의 모든 노드에 두 개의 자식 노드가 있는 이진 트리입니다.
그래픽 관점에서 보면 전체 이진 트리는 삼각형처럼 보입니다.
이진 트리의 수준 수가 K이고 총 노드 수가 (2^k) -1이면 완전 이진 트리입니다.
완전 이진 트리는 "양쪽을 가진 딸"이며 매우 완벽하므로 완전 이진 트리라고 합니다.
완전 이진 트리
잎 노드를 제외한 모든 노드의 차수는 2입니다. 즉, 모든 노드의 차수는 0 또는 2만 될 수 있습니다.
완벽한 이진 트리에는 자식이 없거나 둘 다 있습니다.
완전 이진 트리 VS 완전 이진 트리
완전 이진 트리(FBT)는 나뭇잎을 제외한 모든 노드에 두 개의 자식이 있는 트리입니다.
완전 이진 트리
완전 이진 트리(CBT)는 마지막 레벨을 제외한 모든 레벨이 완전히 채워지고 모든 노드가 최대한 왼쪽에 있는 이진 트리입니다. n개의 노드가 있는 이진 트리. 트리의 노드는 위에서 아래로, 왼쪽에서 오른쪽으로 번호가 매겨집니다. i(1≤i≤n)로 번호가 매겨진 노드가 전체 이진에서 번호가 매겨진 노드와 같습니다. 트리 이진 트리에서 노드 i의 위치가 동일하면 이 이진 트리를 완전 이진 트리라고 합니다.- 마지막 레이어를 제외한 모든 레이어는 완벽하게 채워집니다.
- 마지막 레이어의 모든 리프 노드는 왼쪽으로 정렬됩니다.
힙은
힙은완전한 이진 트리입니다. .
힙은 항상 다음 속성을 충족합니다.- 힙은 항상 완전한 이진 트리입니다.
- 힙에 있는 노드의 값은 항상 상위 노드의 값보다 크거나 작지 않습니다.
- 또한 먼저 이해해야 합니다. 큰 루트 힙과 작은 루트 힙 아래에서 완전한 이진 트리의 모든 노드는 자식 노드보다 크거나 작으므로 여기에는 최대 힙과 작은 루트 힙이라는 두 가지 상황이 있습니다. 최소 힙.
모든 노드 **가 "보다 큰"
- 하위 노드 값인 경우 이 힙을
- "최대 힙"**이라고 하며 힙의 최대 값은 루트 노드에 있습니다.
모든 노드**가 "미만"
- 하위 노드 값인 경우 이 힙을
- "최소 힙"**이라고 하며 힙의 최소값은 루트 노드에 있습니다. .
완전 이진 트리 로 볼 수 있는 배열 개체입니다. 물론 이진 트리는 배열로도 표현될 수 있습니다.
핵심 아이디어는 힙을 먼저 구축한 다음 조정하는 것입니다.
힙 만들기이진 트리(배열 표현)의 경우 **"첫 번째 비리프 노드"**부터 시작하여 아래에서 위로 조정하고 조정 규칙은 다음과 같습니다.
Build Heap은 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!