2018-3-2 面试题

parallel.ts

// 实现一个方法 parallel(tasks, concurrency)，让 tasks 并发执行（并控制并发数为 concurrency)
// 其中 tasks 为一个数组，每一个元素都是一个方法返回一个 promise
// 当所有 tasks 执行完成时，resolve 一个数组保存所有的结果
// 当任意一个 task 执行失败时，reject 这个错误

// 运行方法：
// $ tsc parallel.ts --target esnext && mocha parallel

declare const require
declare const describe
declare const it

const assert = require('assert')

type Task<T = any> = () => Promise<T>

function parallel<T> (tasks: Task<T>[], concurrency: number): Promise<T[]> {
  // 输入检查
  concurrency = Math.floor(concurrency)
  if (Number.isNaN(concurrency) || concurrency <= 0) {
    return Promise.reject(new Error('Invalid parameter'))
  }

  /** 储存并行任务结果 */
  const result: T[] = tasks.slice() as any[]

  /** 最后一个未开始的任务 */
  let index = 0

  // 并行执行任务
  const parallelTasksRunner = Array.from({ length: concurrency }, async () => {
    while (index < result.length) {
      const i = index++
      result[i] = await tasks[i]()
    }
  })

  // 确保所有任务执行完成，并返回结果
  return Promise.all(parallelTasksRunner).then(() => result)
}

describe('parallel', () => {
  function delayTask (input: any, ms: number): Task {
    return () => new Promise(resolve => {
      setTimeout(() => resolve(input), ms)
    })
  }

  function createDelayTasks (): Task[] {
    return [
      delayTask(1, 100),
      delayTask(2, 100),
      delayTask(3, 0),
      delayTask(4, 200),
      delayTask(5, 200)
    ]
  }

  function assertDelayTasks (values: any[]): void {
    assert.deepEqual(values, [1, 2, 3, 4, 5])
  }

  async function measureTime (task: Promise<any>): Promise<number> {
    const start = Date.now()
    await task
    return Date.now() - start
  }

  describe('保证所有任务完成，且顺序正确', () => {
    for (let i = 1; i <= 5; i++) {
      it(`concurrency = ${i}`, () => {
        return parallel(createDelayTasks(), i).then(assertDelayTasks)
      })
    }
  })

  describe('保证同时运行的任务数与设置的一致（允许 5% 误差）', () => {
    it('concurrency = 1', async () => {
      const time = await measureTime(parallel(createDelayTasks(), 1))
      assert(time >= 600 && time < 630)
    })

    it('concurrency = 2', async () => {
      const time = await measureTime(parallel(createDelayTasks(), 2))
      assert(time >= 300 && time < 315)
    })

    it('concurrency = 3', async () => {
      const time = await measureTime(parallel(createDelayTasks(), 3))
      assert(time >= 300 && time < 315)
    })

    it('concurrency = 4', async () => {
      const time = await measureTime(parallel(createDelayTasks(), 4))
      assert(time >= 200 && time < 210)
    })

    it('concurrency = 5', async () => {
      const time = await measureTime(parallel(createDelayTasks(), 5))
      assert(time >= 200 && time < 210)
    })
  })

  describe('其它情况', () => {
    it('没有任务时也能正常结束', () => {
      return parallel([], 5).then(result => assert.deepEqual(result, []))
    })

    it('任务没返回 Promise 也能正常结束', () => {
      return parallel([
        () => 1,
        () => 2,
        () => 3,
        delayTask(4, 200),
        delayTask(5, 200)
      ] as any, 2).then(assertDelayTasks)
    })

    it('并行数量过多时也能正确完成任务', () => {
      return parallel(createDelayTasks(), 10).then(assertDelayTasks)
    })

    it('并行数量无效时抛错', () => {
      return parallel(createDelayTasks(), 0).then(result => {
        assert.fail('并行数量无效时应抛错')
      }).catch(err => { /* noop */ })
    })

    it('任务无效时抛错', () => {
      return parallel([1, 2, 3] as any, 1).then(result => {
        assert.fail('任务无效时应抛错')
      }).catch(err => { /* noop */ })
    })
  })
})