这样的promise, 你能理解么
发布于 21 天前 作者 yongningfu 1298 次浏览 来自 分享

最近在找工作,翻看cnode招聘贴的过程中,想起看到的一个非常有意思的题目,特此分享给大家,当然不是为了做题而做题,主要还是给大家分享一下promise的理解和使用。 相信你花一点点时间阅读,会有一定的收获。原题地址

当然, 原题有点啰嗦,为了节约大家的时间, 我把题目做了一个抽象,大概的意思是,服务器上面有一棵树, 树的结构为如下类型

/**
 * tree set example
 * 
 * {
 *  id: 0,
 *  children: [
 *   {
 *     id: 2
 *     children: [{id: 4, children: []}, {id: 5, children: []}],
 *   },
 *   {
 *     id: 3,
 *     children: [{id: 6, children: []}, {id: 7, children: []}],
 *   },
 * ]
 * }

服务器提供了一下api, 能根据 id 取得 这个id对应的子id, 比如 发起 request/id/0 那么服务器返回[2, 3], 即发起0 返回 [2, 3], 发起 2, 返回[4, 5], 然后在客户端必须建立起和服务器一模一样的树,而且根id已知 为0. (加分项,控制并发为5)

如果是同步的情况下, 相信对大多数人来说,不是难题,一个递归就搞定了,而es7 提供了 async 和 await 确实可以怎么做, 代码也比较简单,对于async 和 await的代码我就不贴出了,主要想讲的是 promise 如何在异步递归的场景使用。

请求走的都是get方法, 每次访问服务器返回一个promise, 于是对服务器的模拟如下

function simuServerReturn(ids) {
  return new Promise((res) => {
    setTimeout(res, 3000, ids);
  });
}

function get(id) {
  if (id === 0) return simuServerReturn([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
  if (id === 1) return simuServerReturn([11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21]);
  if (id === 3) return simuServerReturn([22, 23, 24, 25, 26, 27, 28]);
  return simuServerReturn([]);
}

服务器对应的树为 tree

还是按照递归的思想, 进行异步编程

var result = {};

// container 为 当前这个id对应的对象
function travel(container, startID) {

  container.id = startID;
  container.children = [];
  //  整体返回一个promise 
  return get(startID).then((ids) => {
    // 并发请求所有孩子
    return Promise.all(ids.map(id => {
      var childContainer = {};
      // 将孩子加入到所属关系中
      container.children.push(childContainer);
      // 对孩子id对象进行属性补充 递归
      return travel(childContainer, id);
    }));
  });
}
// 得到结果
travel(result, 0).then(() => {
  console.log(JSON.stringify(result));
});

上面的 代码其实也比较短,可能很多小伙伴在这里就懵逼了。为何travel().then() 就是得到结果了。 我们可以慢慢分析一下这里算法的正确性和promise执行流程

第一个travel 函数会返回一个promise (即 这个promise实际为 get(0).then 返回的), 这个promise状态啥时候确定呢? 它必须等待.then 注册的函数返回的 Promise.all() 这个promise状态确定, Promise.all 又必须等待 .all()里面数组参数中,所有子promsie状态确定,它状态才能确定, 而 每个子promise 即为 递归 travel(childContainer, id) 返回的promsie, 也就是说,上层递归函数 travel(parent) 返回的promise状态必须等待,它里面调用的下层递归的travel(child)返回的promise状态确定, 即

travel(result, 0)  状态确定之时, 已经完成了 子[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 的每个请求,
1的请求成功,也意味着[11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21]的每个请求成功,依次类推

所以这道题就轻松的解出来了。 如果搞定加分项呢, 并发那里好像是把 子 id 全部并发出去了,那是不是把 子 id 切割一下, 每5个一组,就可以了呢


// 把数组按照 数目切割成几个子数组
//splitArrayByNum([1, 2, 3, 4], 2) -->[[1, 2], [3, 4]]
function splitArrayByNum(array, num) {
  var tmp = array.slice();
  var result = [];
  while(tmp.length > 0) {
    result.push(tmp.splice(0, num));
  }
  return result;
}
//  这个一个promise 生产函数,为啥会有这个函数出来?
//  实际是为了做promise的串行调用, 我们知道,一个promise一旦
//  生产出来后,它就立即执行了, 为了控制并发,我们只有利用函数延迟执行
//  类似于 thunk思想
// pContainer 为 子id数组ids的 父容器 
function promiseFac(pContainer, ids) {
  return Promise.all(ids.map(id => {
    var childContainer = {};
    pContainer.children.push(childContainer);
    return travel(childContainer, id);
  }));
}

function travel(container, startID) {

  container.id = startID;
  container.children = [];

  return get(startID).then((ids) => {
    // 做prommise串行调用的初始对象
    var result = Promise.resolve();
    // 先对返回的子数组切割, 返回进行串行调用 
    splitArrayByNum(ids, 5).forEach((childIds) => {
      //  为使用参数 外面套了一层function
      result = result.then(() => promiseFac(container, childIds));
    });
    return result;
  });
}

travel(result, 0).then(() => {
  console.log(JSON.stringify(result));
});

这里可能有些人会对 result = result.then(() => promiseFac(container, childIds)); 这句话有些不理解, 其实,为了控制并发,前一个result的状态确定后, 才执行 .then 注册的 () => promiseFac(container, childIds), 这个函数返回的promise状态确定后, .then本身返回的promise状态才确定,即后一个result状态才确定,依次类推,所以就形成了串行调用。

写到这里以为已经完美了,其实并不是,上面只是想让你们了解一下,promise如何控制串行调用的,上面的代码实际还不能真正控制并发量为5, 虽然我们在同级之间做了并发限制,但是,代码毕竟是深度递归调用的,不同级之间无法控制,既然直接深度遍历无法控制,那么我们就加上一点广度的思路,问题就完美解决了

var result = {id: 0, children: []};
//  利用队列进行存储中间使用的所有对象
var queue = [result];
function travel() {
  if (queue.length > 0) {
    const length = Math.min(5, queue.length);
    const reqObjs = queue.splice(0, length);
    //  这里异步调用很简单, 前一个promise 确定后,才往下递归
    Promise.all(reqObjs.map(req => get(req.id))).then((response) => {
      for (let i = 0; i < response.length; i++) {
        for (let j = 0; j < response[i].length; j++) {
          const childrenContainer = {id: response[i][j], children: []};
          reqObjs[i].children.push(childrenContainer);
          queue.push(childrenContainer);
        }
      }
      travel();
    });
  // 队列里面没有东西了, 自然就结束了
  } else {
    console.log(JSON.stringify(result));
  }
}

travel();

async 版本和所有代码 都在github

回到顶部