首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >前端编码题中的集大成者,异步sum/add

前端编码题中的集大成者,异步sum/add

作者头像
虎妞先生
发布2023-05-07 21:08:48
2540
发布2023-05-07 21:08:48
举报

最近刷各个大厂面试题,反复出现一道题,让我印象深刻。

废话不多,我们直接上题目

请实现一个 sum 函数,接收一个数组 arr 进行累加,并且只能使用add异步方法

add 函数已实现,模拟异步请求后端返回一个相加后的值

/*
  请实现一个 sum 函数,接收一个数组 arr 进行累加,并且只能使用add异步方法
  
  add 函数已实现,模拟异步请求后端返回一个相加后的值
*/
function add(a, b) {
  return Promise.resolve(a + b);
}

function sum(arr) {
  
}

这道题在问什么?

add 函数是返回一个promise, 异步输出a+b 的值,

我们使用add 模拟接口请求,a,b 是给接口的参数,a+b 是接口返回的值。

sum 函数输入一个数组例如[1,2,3,4,5],进行累加,使用add异步方法。

转换成我们业务中的场景就是,

  • 调用接口执行1+2, 接口返回3,
  • 调用接口再执行3+3, 接口返回6
  • 调用接口再执行6+4,接口返回10
  • 调用接口再执行10+5,接口返回15

简单实现

不用多考虑,遍历执行累加就好

  • 借助数组方法 reduce方法实现累加
function add(a, b) {
  return Promise.resolve(a + b);
}

function sum(arr) {
  if (arr.length === 1) return arr[0];
  return arr.reduce((x, y) => Promise.resolve(x).then((x) => add(x, y)));
}
  • 借助async/await 实现,原理一样,代码更加清晰
function add(a, b) {
  return Promise.resolve(a + b);
}

async function sum(arr) {
  let s = arr[0]
  for (let i = 1; i < arr.length; i++) {
    s = await add(s, arr[i])
  }
  return s
}

问题

如果add 函数调用接口,假设接口执行完毕返回需要1s,那么一个长度为n 的数组,需要执行n-1次累加,需要的时间为n-1 s

面试官继续问了,有没有什么优化空间呢?

优化实现

既然是异步操作,还是累加操作,也就是说,只要输入的数组是确定的,返回的累加值也就是确定的。

之前从前往后累加,一个一个加。

我现在可以借助Promise.all() 改成并行请求,数组两两一组,进行累加,然后再把和累加。

比如输入[1,2,3,4,5]

第一次请求[1,2] [3,4],拿到接口返回3,7

第二次请求[3,7],拿到接口返回 10

第三次请求[10,5], 拿到接口返回 15

function add(a, b) {
  return Promise.resolve(a + b);
}
// chunk 函数把输入数组两两分组
// 输入[1,2,3,4,5]
// 返回[[1,2],[3,4],5]
function chunk(arr){
  const res = []
  for(let i =0;i<arr.length;i++) {
    const index = Math.floor(i/2)
    res[index] ??= []
    res[index].push(arr[i])
  }
  return res
}

async function sum(arr) {
  if (arr.length === 1) return arr[0];
  const promises = chunk(arr).map(([x, y]) =>
    // 注意此时单数的情况
    y === undefined ? x : add(x, y)
  );
  return Promise.all(promises).then((list) => sum(list));
}

有点类似归并思想,把数组分成两两一组,最后一项如果是单数,直接输出就好,直到数组长度为1.

时间复杂度也降低了logN

问题

这种是代码code的思路,但是实践生产能写这样的代码?

promise.all 中可以写100个,1000个元素,一起发起请求,但是浏览器起能同时发起100个1000个请求吗?

于是面试官继续问了, 比如有1000个数据,那第一次就会发送500个请求,网络拥堵了,我想控制成只能同时发送10个请求怎么办?

再次优化

要控制成只能同时发送10个请求,就要对promise.all进行修改。

function add(a, b) {
  return Promise.resolve(a + b);
}


function chunk(arr){
  const res = []
  for(let i =0;i<arr.length;i++) {
    const index = Math.floor(i/2)
    res[index] ??= []
    res[index].push(arr[i])
  }
  return res
}

async function pMap(list, mapper, concurrency = Infinity) {
  const results = [];

  const batches = chunk(list, Math.min(concurrency, list.length));

  await Promise.all(
    batches.map(async (batch) => {
      const batchResults = await Promise.all(batch.map(mapper));
      results.push(...batchResults);
    })
  );

  return results;
}

async function sum(arr, concurrency) {
  if (arr.length === 1) return arr[0];

  const mapped = await pMap(
    chunk(arr, 2),
    ([x, y]) => (y === undefined ? x : add(x, y)),
    concurrency
  );

  return sum(mapped, concurrency);
}

pMap 函数中,先调用 chunk 函数将原数组按照指定大小切割成多个子数组(每个子数组大小不超过并发数),然后使用 Promise.all 将每个子数组中的数据并发地传递给 mapper 函数进行处理,最后将每个子数组的处理结果拼接成一个新数组返回。

sum 函数则使用了 pMap 函数,将原数组切割成两两一组的子数组,对每个子数组调用 add 函数求和,最终递归地将求和后的结果作为新数组再次传入 pMap 函数中继续处理。

这样实现可以提高代码的并发性能,加速数据处理的速度。

以下是一个使用例子,测试用例将一个长度为 10 的数组按照每个元素加 1 的方式进行异步处理,并发数为 3:

const arr = [1, 2, 3, 4, 5];

sum(arr, 2)
  .then(result => console.log(result))
  .catch(error => console.error(error));

总结

上述一个代码题考查了哪些部分

  • promise串行,并行
  • 二分
  • 并发控制

考察技术深度广度都有了,但是大部分人题目都看不懂,其实我也是,我连答案也没明白。 但是这些题目看不懂,给了答案也得理解,告诉你思路,下手实现却写不出代码,往往是最有区分度的地方。 人们精通并擅长为自己的行为找原因,但却非常不善于做我们已经找到原因的事。 要完全弄懂,还需花时间思考啊。

参考链接https://github.com/shfshanyue/Daily-Question/issues/662


本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2023-05-04,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 这道题在问什么?
  • 简单实现
    • 问题
    • 优化实现
      • 问题
      • 再次优化
      • 总结
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档