实现一个异步的 sum/add
更多描述 这是一道字节跳动的面试题目，见面经 某银行前端一年半经验进字节面经 (opens in a new tab)。山月认为这也是一道水平较高的题目，promise 串行，并行，二分，并发控制，层层递进。
请实现以下 sum 函数，只能调用 add 进行实现
/*
请实现一个 sum 函数，接收一个数组 arr 进行累加，并且只能使用add异步方法
add 函数已实现，模拟异步请求后端返回一个相加后的值
*/
function add(a, b) {
return Promise.resolve(a + b);
}
function sum(arr) {}追加问题：如何控制 add 异步请求的并发次数
相关问题：
- 【Q088】如何实现 promise.map，限制 promise 并发数 (opens in a new tab)
- 【Q643】如何实现 chunk 函数，数组进行分组 (opens in a new tab)
Issue 欢迎在 Gtihub Issue 中回答此问题: Issue 662 (opens in a new tab)
Author 回答者: mtt3366 (opens in a new tab)
!(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 (opens in a new tab)
初级实现: 串行方式
遇到这种题目，第一反应就是如同同步 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 (opens in a new tab): _.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 (opens in a new tab)
Author 回答者: Asarua (opens in a new tab)
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 (opens in a new tab)
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 (opens in a new tab)
串行
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 (opens in a new tab)
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 (opens in a new tab)
@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 (opens in a new tab)
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 (opens in a new tab)
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 (opens in a new tab)
// 这是一道字节跳动的面试题目，见面经 某银行前端一年半经验进字节面经。山月认为这也是一道水平较高的题目，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 (opens in a new tab)
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 (opens in a new tab)
并发计算，最小时间
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();
});
}