一纸简历更新更多的简历模板，如应届生模板与三年前端模板，点击查看 →
高级前端手写代码【Q644】实现一个异步的 sum/add

实现一个异步的 sum/add

更多描述 这是一道字节跳动的面试题目，见面经 某银行前端一年半经验进字节面经。山月认为这也是一道水平较高的题目，promise 串行，并行，二分，并发控制，层层递进。

请实现以下 sum 函数，只能调用 add 进行实现

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

追加问题：如何控制 add 异步请求的并发次数

相关问题：

Issue 欢迎在 Gtihub Issue 中回答此问题: Issue 662

Author 回答者: mtt3366

!(async function () {
  function add(a, b) {
    // return new Promise((resolve)=>{
    //     setTimeout(()=>{
    //         resolve(a+b)
    //     },1000)
    // })
    return Promise.resolve(a + b);
  }
  async function changeArr(arr) {
    //两两相加转化为新数组
    let reArr = [];
    for (let i = 0; i < arr.length; i += 2) {
      if (arr[i + 1] === undefined) {
        //如果是奇数个数组,只把最后一个push进去
        reArr.push(Promise.resolve(arr[i]));
      } else {
        reArr.push(add(arr[i], arr[i + 1]));
      }
    }
    return await Promise.all(reArr);
  }
  async function sum(arr) {
    if (arr.length < 2) {
      //数组长度小于2
      return arr[0];
    }
    let result = await changeArr(arr); //处理数组,两两相加转化为新数组
    if (result.length < 2) {
      //递归结束条件
      return result[0];
    } else {
      return sum(result); //递归两两相加
    }
  }
  const r = await sum([2, 2, 2, 2, 2]);
  console.log(r);
})();

Author 回答者: shfshanyue

初级实现: 串行方式

遇到这种题目，第一反应就是如同同步 sum 的实现一样，一个一个进行累加。

以下是一个借助于 Array.prototype.reduce 实现的 Promise 版本。

这里一个注意的点是：不能将 0 作为累加器的初始值，因此 add 为异步的，不能保证 add(x, 0) === x

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 的异步 sum 的实现，逻辑更为清楚，同样我们把初始值设置为数组中第一个数，而非 0。

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

代码片段

不管是基于 promise 还是 async 实现，这应该是大部分人的第一反应，然而还有很多同学，直接最简单的实现无法通过，很可能无法通过面试。

但是它有一个问题，在异步sum函数中，其中最为耗时的是 add()，因为他是一个异步 IO 操作，模拟的是服务器数据请求，假设 add 延时一秒，此时需要 N-1 秒，延时太长。

中级实现: 并行方式

关于上边的同步实现，有可能就会筛了一部分同学。面试官到了这里，就会继续增加难度。

接下来是并行的写法: 我们实现一个 chunk 函数，将数组两两分组，每两个计算一次，使用 chunk 二分，此时延时变为 logN 秒

关于 chunk 的 API 可以参考 lodash.chunk: _.concat(array, [values])，在平常工作中也会用到。

function chunk(list, size) {
  const l = [];
  for (let i = 0; i < list.length; i++) {
    const index = Math.floor(i / size);
    l[index] ??= [];
    l[index].push(list[i]);
  }
  return l;
}

在通过 chunk 进行两两分组时，有可能最后一项为单数，此时直接返回数值即可，在最终得到结果后，迭代该函数继续二分，直到最后只有一个数值。

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

代码片段

写到这里，感觉难度还不是很大，注意，此时使用的是 Promise.all，意味着不管 Promise.all 所接收的数组中有多少元素，将会同时进行处理。

此时面试官会进行扩展: 比如有10000个数据，那第一次就会发送5000个请求，网络拥堵了，我想控制成只能同时发送10个请求怎么办？

更进一步: 控制并行数

如果需要控制并行数，则可以先实现一个 promise.map 用以控制并发，这也是在面试中经常考察的一个点。使用 promise.map 来代替上一步的 promise.all。

关于 promise.map 的 API 可以参考 bluebird: new Promise(function(function resolve, function reject) resolver) -> Promise。

与上一步相同，使用 sum 迭代该函数继续二分，直到最后只有一个数值。

function pMap(list, mapper, concurrency = Infinity) {
  return new Promise((resolve, reject) => {
    let currentIndex = 0;
    let result = [];
    let resolveCount = 0;
    let len = list.length;
    function next() {
      const index = currentIndex++;
      Promise.resolve(list[index])
        .then((o) => mapper(o, index))
        .then((o) => {
          result[index] = o;
          if (++resolveCount === len) {
            resolve(result);
          }
          if (currentIndex < len) {
            next();
          }
        });
    }
    for (let i = 0; i < concurrency && i < len; i++) {
      next();
    }
  });
}
 
async function sum(arr, concurrency) {
  if (arr.length === 1) return arr[0];
  return pMap(
    chunk(arr, 2),
    ([x, y]) => {
      return y === undefined ? x : add(x, y);
    },
    concurrency,
  ).then((list) => sum(list, concurrency));
}

关于 promise.map 还有一个更简单的实现，可参考 async-pool

Author 回答者: Asarua

function add(a, b) {
  return Promise.resolve(a + b);
}
 
async function sum(arr) {
  let su = 0;
  for (const item of arr) {
    su = await add(su, item);
  }
  return su;
}

Author 回答者: heretic-G

Promise.map = function (queue = [], opt = {}) {
  let limit = opt.limit || 5;
  let queueIndex = 0;
  let completeCount = 0;
  let _resolve;
  let result = Array(queue.length);
 
  for (let i = 0; i < limit; i++) {
    next(queueIndex++);
  }
 
  function next(index) {
    if (queue.length === 0) return;
    let curr = queue.shift();
    if (typeof curr === "function") {
      curr = curr();
    }
    Promise.resolve(curr)
      .then(
        (res) => {
          result[index] = res;
        },
        (res) => {
          result[index] = res;
        },
      )
      .finally(() => {
        completeCount += 1;
        if (completeCount === result.length) {
          return _resolve(result);
        }
        next(queueIndex++);
      });
  }
  return new Promise((resolve) => {
    _resolve = resolve;
  });
};
 
function add(a, b) {
  return Promise.resolve(a + b);
}
 
function sum(arr) {
  if (arr.length <= 2) {
    return add(arr[0] || 0, arr[1] || 0);
  }
  let mid = (arr.length / 2) | 0;
  let promiseArr = [];
  for (let i = 0; i < mid; i++) {
    promiseArr.push(add(arr[i], arr[mid + i]));
  }
  return Promise.map(promiseArr).then((res) => {
    if (arr.length % 2 !== 0) {
      res.push(arr.pop());
    }
    return sum(res);
  });
}

Author 回答者: grace-shi

串行

const sum = (arr) =>
  arr.reduce(async (acc, item) => add(await acc, item), Promise.resolve(0));

并行

const sum = (arr) => {
  if (arr.length === 0) {
    return 0;
  }
 
  if (arr.length === 1) {
    return arr[0];
  }
 
  const promiseArr = arr
    .reduce((acc, item, index) => {
      if (index % 2 === 0) {
        acc.push(arr.slice(index, index + 2));
      }
      return acc;
    }, [])
    .map((chunk) =>
      chunk.length === 2 ? add(...chunk) : Promise.resolve(chunk[0]),
    );
 
  return Promise.all(promiseArr).then(sum);
};

Author 回答者: mahaoming

function add(a, b) {
  return Promise.resolve(a + b);
}
 
async function sum(arr) {
  let res = 0;
  if (arr.length === 0) return res;
  if (arr.length === 1) return arr[0];
 
  let a = arr.pop();
  let b = arr.pop();
  arr.push(await add(a, b));
  return sum(arr);
}
 
sum([2, 2, 2, 2]).then((res) => {
  console.log(res);
});

Author 回答者: shfshanyue

@mahaoming 这个思路眼前一亮啊！不过貌似是串行的

function add(a, b) {
  return Promise.resolve(a + b);
}
 
async function sum(arr) {
  let res = 0;
  if (arr.length === 0) return res;
  if (arr.length === 1) return arr[0];
 
  let a = arr.pop();
  let b = arr.pop();
  arr.push(await add(a, b));
  return sum(arr);
}
 
sum([2, 2, 2, 2]).then((res) => {
  console.log(res);
});

Author 回答者: lulusir

function add(a, b) {
  // return a+b
  return Promise.resolve(a + b);
}
 
async function sum(arr) {
  if (arr.length <= 2) {
    const r = await add(arr[0] || 0, arr[1] || 0);
    return r;
  } else {
    const len1 = Math.floor(arr.length / 2);
    const s1 = await sum(arr.slice(0, len1));
    const s2 = await sum(arr.slice(len1));
    return s1 + s2;
  }
}
sum([1, 2, 3, 4, 5]).then(console.log);

Author 回答者: haotie1990

const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
 
function add(a, b) {
  return Promise.resolve(a + b);
}
 
function sum(arr, add) {
  return arr.reduce((p, c) => {
    return p.then((acc) => {
      if (!acc) {
        acc = 0;
      }
      return add(acc, c);
    });
  }, Promise.resolve());
}
 
// 将数组拆分，分别计算，最后累加
function sumPoll(arr, add, concurrency = Infinity) {
  const chunks = [];
  const len = arr.length <= concurrency ? arr.length : concurrency;
  while (arr.length) {
    chunks.push(arr.splice(0, len));
  }
  const tasks = [];
  for (const chunk of chunks) {
    tasks.push(
      chunk.reduce(
        (p, c) =>
          p.then((acc) => {
            if (!acc) acc = 0;
            return add(acc, c);
          }),
        Promise.resolve(),
      ),
    );
  }
  return Promise.all(tasks).then((result) => {
    if (result.length === 1) {
      return result[0];
    }
    return sumPoll(result, add);
  });
}
 
sumPoll(arr, add, 3).then((result) => console.log(result));

Author 回答者: iceycc

// 这是一道字节跳动的面试题目，见面经 某银行前端一年半经验进字节面经。山月认为这也是一道水平较高的题目，promise 串行，并行，二分，并发控制，层层递进。
// 请实现以下 sum 函数，只能调用 add 进行实现
/*
    请实现一个 sum 函数，接收一个数组 arr 进行累加，并且只能使用add异步方法
    add 函数已实现，模拟异步请求后端返回一个相加后的值
  */
function add(a, b) {
  return new Promise((resolve) => {
    setTimeout(() => {
      resolve(a + b);
    }, 10);
  });
}
 
// 异步串行 迭代 + promise
function sum(arr) {
  // Promise.resolve传人一个promise会等传人的promise执行完毕再then
  return arr.reduce((pre, next) => {
    console.log(1);
    // 瞬间循环完，然后会将当前作为一个primise返回到下一个，
    //利用Promise.resolve入参是promise会等待的特点，异步线程会串行相加
    return Promise.resolve(pre).then((x) => add(x, next));
  }, 0);
}
// console.log(sum([1,2,3,4,5]).then(res=>console.log(res)))
 
// 异步串行 : async await 实现异步串行
async function sum2(arr) {
  let su = 0;
  for (let item of arr) {
    console.log(2); // 等待打印
    su = await add(su, item);
  }
  return su;
}
// console.log(sum2([1,2,3,4,5]).then(res=>console.log(res)))
// 异步串行: genrator实现
function sum3(arr) {
  let sumGen = function* () {
    let su = 0;
    for (let item of arr) {
      su = yield add(su, item);
    }
    return su;
  };
  let it = sumGen();
  function co(it) {
    return new Promise((resolve, reject) => {
      function next(val) {
        let { value, done } = it.next(val);
        if (done) {
          resolve(value);
        } else {
          Promise.resolve(value).then((data) => {
            next(data);
          }, reject);
        }
      }
      next();
    });
  }
  return co(it);
}
// console.log(sum3([1, 2, 3, 4, 5]).then((res) => console.log(res)));
 
// 并行
async function sum4(arr) {
  if (arr.length == 0) return add(0, 0);
  if (arr.length == 1) return add(0, arr[0]);
  if (arr.length == 2) return add(arr[0], arr[1]);
  let mid = Math.floor(arr.length / 2);
  let [l, r] = await Promise.all([
    sum4(arr.slice(0, mid)),
    sum4(arr.slice(mid)),
  ]);
  return sum4([l, r]);
}
console.log(sum4([1, 2, 3, 4, 5, 6, 7, 8]).then((res) => console.log(res)));

Author 回答者: shengrongchun

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

function sum(arr) { const promises = [] for(let i=0,j=arr.length;i<j;i=i+2) { promises.push(add(arr[i]||0,arr[i+1]||0)) } Promise.all(promises).then((arr)=> { const result = arr.reduce((total,item)=> { return total+item },0) }) }

Author 回答者: cloudGrin

并发计算，最小时间

function sum(arr: any[]) {
  return new Promise((resolve, reject) => {
    let rest = [...arr];
    let addIngCount = 0;
    function next() {
      if (addIngCount === 0 && rest.length <= 1) {
        resolve(rest[0] ?? 0);
        return;
      }
      for (let i = 0; i < rest.length - 1; i = i + 2) {
        addIngCount++;
        add(rest[i], rest[i + 1]).then((result) => {
          rest.push(result);
          addIngCount--;
          next();
        });
      }
      rest = rest.length % 2 === 1 ? [rest[rest.length - 1]] : [];
    }
    next();
  });
}
【Q643】如何实现 chunk 函数，数组进行分组【Q645】随机生成六位数的手机验证码(重复/不可重复)