记一次任务调度算法题

前言

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

题目

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 函数

(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 链中打印出来，这个改怎么重写这个类。题解如下：

(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 实现机制其实在琢磨此题时还是有那么一点头痛，只要关键的类递归函数部分琢磨清楚了，整体也不是很难。