沐光

记录在前端之路的点点滴滴

记一次任务调度算法题

前言

ES6 的 Promise 可以拓展很多比较好的调度算法,比如最近碰到的一个让人眼前一亮的简单任务调度实现的题目,这里我记录一下我的思考和实现。

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Scheduler {
add(promiseCreator) {
// 代码部分
}
}

const scheduler = new Scheduler();

function addTask(time, order) {
scheduler.add(() => {
return new Promise((res, rej) => {
setTimeout(() => {
console.log('order', order);
res();
}, time);
});
})
};

addTask(1000, '1');
addTask(500, '2');
addTask(300, '3');
addTask(400, '4');

// 结果要求 order 为: 2、3、1、4

思路&题解

分析:

  • 从结果来看,因为每次只能执行俩异步函数,因此数组处理逻辑大致为“队列”
  • 从 scheduler 的链式调用可发现每次返回的都是 Promise 函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
(function () {
class Scheduler {
constructor() {
this.eventList = [];
this.used = 0;
this.currentPos = 0;
}

add(promiseCreator) {
this.eventList.push(promiseCreator);

// 执行任务
return Promise.resolve(this.excute());
}

excute() {
if (this.used < 2 && this.currentPos < this.eventList.length) {
this.used++;

const currentFunc = this.eventList[this.currentPos++];

return Promise.resolve(currentFunc()).then(() => {
this.used--;
// 每次执行完查看是否继续执行后面的内容
this.excute();
});
}
}
}

const scheduler = new Scheduler();

function addTask(time, order) {
scheduler.add(() => {
return new Promise((res, rej) => {
setTimeout(() => {
console.log('order', order);
res();
}, time);
});
})
};

addTask(1000, '1');
addTask(500, '2');
addTask(300, '3');
addTask(400, '4');
})();

难度提升

先前的打印都是在 addTask 函数内部的,假如没有这个 addTask 函数,而且获取的函数结果需要在 then 链中打印出来,这个改怎么重写这个类。题解如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
(function () {
class Scheduler {
constructor(maxUsed = 2) {
this.eventList = [];
this.used = 0;
this.maxUsed = maxUsed;
this.currentPos = 0;
}

add(timeout, val) {
const excute = () => {
if (
this.currentPos < this.eventList.length &&
this.used < this.maxUsed
) {
const tarData = this.eventList[this.currentPos++];
const { res, rej, timeout, val } = tarData;
this.used++;

return new Promise((resolve, reject) => {
setTimeout(() => {
resolve(val);
}, timeout);
})
.then(res, rej)
.finally(() => {
this.used--;
excute();
});
}
};

// 执行任务
return new Promise((res, rej) => {
this.eventList.push({
res,
rej,
timeout,
val,
});

return excute();
});
}
}

const scheduler = new Scheduler();

scheduler.add(1000, '1').then((res) => {
console.log(res);
});
scheduler.add(500, '2').then((res) => {
console.log(res);
});
scheduler.add(300, '3').then((res) => {
console.log(res);
});
scheduler.add(400, '4').then((res) => {
console.log(res);
});
})();

小结

其实题目考察的是对于 Promise 函数以及链式调用的理解,了解过 Promise 实现机制其实在琢磨此题时还是有那么一点头痛,只要关键的类递归函数部分琢磨清楚了,整体也不是很难。