【Q644】实现一个异步的 sum/add

[shfshanyue]

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

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

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

  add 函数已实现，模拟异步请求后端返回一个相加后的值
*/
function add(a, b) {
  return Promise.resolve(a + b);
}

function sum(arr) {

}

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

相关问题：

• 【Q088】如何实现 promise.map，限制 promise 并发数
• 【Q643】如何实现 chunk 函数，数组进行分组

[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)
    }()

[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

[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
}

[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)
    })
}

[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)
}

[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)})

[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)})

[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)

[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));

[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)));

[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) }) }

[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();
  });
}