模拟实现
2023年11月30日
一、实现
1.1 /scheduler/src/SchedulerMinHeap.js
class MinHeap {
constructor() {
this.data = [];
}
compare(a, b) {
return a - b;
}
/**
* @description: 向小顶堆中添加元素
* @param {*} value
*/
push(value) {
const index = this.data.length;
this.data.push(value);
this.shiftUp(this.data, index);
}
/**
* @description: 通过 data 数组构建小顶堆
* @param {*} data
*/
build(data) {
this.data = [...data];
const halfLength = this.data.length >>> 1;
for (let i = halfLength - 1; i >= 0; i--) {
this.shiftDown(this.data, i, this.data.length);
}
return this.data;
}
pop() {
if (this.data.length === 0) {
return null;
}
const first = this.data[0];
const last = this.data.pop();
if (first !== last) {
this.data[0] = last;
this.shiftDown(this.data, 0, this.data.length);
}
return first;
}
peek() {
return this.data.length === 0 ? null : this.data[0];
}
/**
* @description: 小顶堆排序 --- 从大到小
*/
sort() {
let data = [...this.data];
// 1. 通过 data 数组构建小顶堆
data = this.build(data);
// 2. 从最后一个元素开始, 依次与堆顶元素进行交换, 然后重新调整堆
for (let i = data.length - 1; i > 0; i--) {
[data[0], data[i]] = [data[i], data[0]];
this.shiftDown(data, 0, i);
}
return data;
}
shiftUp(data, startIndex) {
let i = startIndex;
while (i > 0) {
const parentIndex = (i - 1) >>> 1;
const parent = data[parentIndex];
if (this.compare(parent, data[i]) > 0) {
[data[i], data[parentIndex]] = [data[parentIndex], data[i]];
i = parentIndex;
} else {
return;
}
}
}
shiftDown(data, startIndex, endIndex) {
let i = startIndex;
const halfLength = endIndex >>> 1;
while (i < halfLength) {
const leftIndex = (i + 1) * 2 - 1;
const left = data[leftIndex];
const rightIndex = leftIndex + 1;
const right = data[rightIndex];
if (this.compare(left, data[i]) < 0) {
if (rightIndex < endIndex && this.compare(right, left) < 0) {
[data[i], data[rightIndex]] = [data[rightIndex], data[i]];
i = rightIndex;
} else {
[data[i], data[leftIndex]] = [data[leftIndex], data[i]];
i = leftIndex;
}
} else if (rightIndex < endIndex && this.compare(right, data[i]) < 0) {
[data[i], data[rightIndex]] = [data[rightIndex], data[i]];
i = rightIndex;
} else {
return;
}
}
}
}
二、测试
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Synchronous Update Demo</title>
<style>
#span-container {
display: flex;
flex-wrap: wrap;
}
.span-1 {
color: green;
}
.span-2 {
color: purple;
}
.span-3 {
color: saddlebrown;
}
.span-4 {
color: orchid;
}
</style>
</head>
<body>
<div id="button-container"></div>
<div id="span-container"></div>
<script type="module">
import scheduler from 'https://cdn.jsdelivr.net/npm/scheduler@0.23.0/+esm';
const {
unstable_LowPriority: LowPriority,
unstable_shouldYield: shouldYield,
unstable_IdlePriority: IdlePriority,
unstable_NormalPriority: NormalPriority,
unstable_cancelCallback: cancelCallback,
unstable_scheduleCallback: scheduleCallback,
unstable_ImmediatePriority: ImmediatePriority,
unstable_getFirstCallbackNode: getFirstCallbackNode,
unstable_UserBlockingPriority: UserBlockingPriority
} = scheduler;
const workList = [];
let currentCallback = null;
let prevPriority = IdlePriority;
const spanContainer = document.querySelector('#span-container');
const buttonContainer = document.querySelector('#button-container');
/**
* @description: 模拟一些耗时的任务（与逻辑无关，只是为了看效果而已）
* @param {*} len
*/
function doSomeBusyWork(len) {
let result = 0;
while (len--) {
result += len;
}
}
function insertSpan(content) {
const span = document.createElement('span');
span.textContent = content;
span.className = `span-${content}`;
doSomeBusyWork(10000000);
spanContainer.appendChild(span);
}
function schedule() {
const callbackNode = getFirstCallbackNode();
const currentWork = workList.sort(
(work1, work2) => work1.priority - work2.priority
)[0];
if (!currentWork) {
currentCallback = null;
callbackNode && cancelCallback(callbackNode);
return;
}
const { priority: currentPriority } = currentWork;
if (prevPriority === currentPriority) {
return;
}
callbackNode && cancelCallback(callbackNode);
currentCallback = scheduleCallback(
currentPriority,
perform.bind(null, currentWork)
);
}
function perform(work, didTimeout) {
const needSync = work.priority === ImmediatePriority || didTimeout;
while ((needSync || !shouldYield()) && work.count) {
work.count--;
insertSpan(work.priority + '');
}
prevPriority = work.priority;
if (!work.count) {
const workIndex = workList.indexOf(work);
workList.splice(workIndex, 1);
prevPriority = IdlePriority;
}
const prevCallback = currentCallback;
schedule();
const newCallback = currentCallback;
if (newCallback && prevCallback === newCallback) {
return perform.bind(null, work);
}
}
const buttonList = [
LowPriority,
NormalPriority,
ImmediatePriority,
UserBlockingPriority
];
const buttonTestList = [
'LowPriority',
'NormalPriority',
'ImmediatePriority',
'UserBlockingPriority'
];
buttonList.forEach((priority, index) => {
const button = document.createElement('button');
button.textContent = buttonTestList[index];
button.addEventListener('click', () => {
workList.unshift({
priority,
count: 100
});
schedule();
});
buttonContainer.appendChild(button);
});
</script>
</body>
</html>