只给一个异步加法函数 asyncAdd，怎样求多个数的和并尽量快？

简答

题目一般这样给：有一个 asyncAdd(a, b, callback)，它不立即返回结果，而是过一会儿通过 callback(err, result) 告诉你 a + b，可以想象成一次要等待的网络请求。要求只用它算出 sum(1, 2, 3, ...)。

第一步是把回调包成 Promise，写一个 add(a, b) 返回 Promise，后面就能用 await 和 Promise.all。最直接的写法是串行累加：先算 1 + 2，结果再加 3，以此类推。n 个数要调用 n-1 次，每次都得等上一次完成，总耗时是 n-1 次调用的时间。

优化的依据是加法满足结合律，先加哪两个都不影响结果。所以每一轮把数两两配对，[1,2,3,4] 同时算 1+2 和 3+4，用 Promise.all 等这一轮全部完成，下一轮再把结果两两相加。调用次数还是 n-1，但只要等约 log₂n 轮，8 个数从 7 轮降到 3 轮。

要注意，第一轮会同时发出约 n/2 次调用，如果 asyncAdd 背后是真实请求，数量大时要加并发上限。另外 Promise.all 只要有一个失败就整体失败，回调里的 err 一定要传给 reject，否则错误会被吞掉。

先把回调包成 Promise，再比较两种写法

示例里的 asyncAdd 用 Promise.resolve().then() 模拟异步，calls 记录它被调用了多少次，rounds 记录两两合并的写法等了几轮。

let calls = 0;
function asyncAdd(a, b, callback) {
  calls += 1;
  Promise.resolve().then(() => callback(null, a + b));
}

function add(a, b) {
  return new Promise((resolve, reject) => {
    asyncAdd(a, b, (err, result) => (err ? reject(err) : resolve(result)));
  });
}

async function sumSerial(nums) {
  if (nums.length === 0) return 0;
  let total = nums[0];
  for (let i = 1; i < nums.length; i += 1) total = await add(total, nums[i]);
  return total;
}

async function sumParallel(nums) {
  if (nums.length === 0) return 0;
  let rounds = 0;
  let current = nums;
  while (current.length > 1) {
    const tasks = [];
    for (let i = 0; i < current.length; i += 2) {
      tasks.push(i + 1 < current.length ? add(current[i], current[i + 1]) : current[i]);
    }
    current = await Promise.all(tasks);
    rounds += 1;
  }
  return { total: current[0], rounds };
}

const nums = [1, 2, 3, 4, 5, 6, 7, 8];
sumSerial(nums)
  .then((total) => {
    console.log(`串行：${total}，调用 ${calls} 次`); // 串行：36，调用 7 次
    calls = 0;
    return sumParallel(nums);
  })
  .then(({ total, rounds }) => {
    console.log(`两两合并：${total}，调用 ${calls} 次，${rounds} 轮`); // 两两合并：36，调用 7 次，3 轮
  });

两种写法调用 asyncAdd 的次数一样，都是 7 次，差别在等待的方式。串行写法里每次 await 都要等上一次结果回来，7 次调用一个接一个，要等 7 次。两两合并的写法第一轮同时发出 4 次调用，1+2、3+4、5+6、7+8，第二轮 2 次，第三轮 1 次，只需要等 3 轮。如果每次调用要 100 毫秒，串行大约 700 毫秒，两两合并大约 300 毫秒。

为什么调用次数省不下来？因为每次加法把两个数变成一个，n 个数变成 1 个，不管怎么安排都要做 n-1 次。能优化的只有“多少次调用可以同时进行”。

两两合并里的几个细节

奇数个数时怎么办？tasks.push 那一行判断，最后一个数没有搭档，就把它原样放进 tasks。Promise.all 接受普通值，会把它当成已经完成的结果，下一轮它再和别人配对。

为什么先包成 add？因为 Promise.all 只能等 Promise，回调形式的函数没法直接放进去。包装时要把回调里的 err 交给 reject，这样任何一次加法失败，Promise.all 都会立刻进入失败状态，外面可以 catch 到。Promise.all 的手写见《怎样实现保持输入顺序的 Promise.all 教学版本？》。

数量很多时加上并发上限

两两合并的第一轮会同时发出 n/2 次调用。如果 asyncAdd 其实是一次服务端请求，1000 个数就会一下子发出 500 个请求，浏览器和服务端都可能吃不消。

这时可以换一种调度方式：准备一个待加的数字队列，同时最多开 k 个任务，每个任务从队列里取两个数相加，结果放回队列；队列里只剩一个数、且没有正在进行的任务时就结束。每次一个任务完成，就有空位去取下一对，这和并发池的思路一样，见《怎样实现有明确失败语义的异步并发池？》。k 取 n/2 时就退化成上面的两两合并，k 取 1 就是串行。

常见追问

如果 asyncAdd 本身支持传多个数，比如 asyncAdd(a, b, c, callback)，怎么优化？

思路一样，只是每一轮不是两两分组，而是按它能接受的个数分组，每组一次调用。每轮剩下的数变成原来的几分之一，轮数会更少。

如果同样的两个数可能被反复计算，还能怎么优化？

可以按 a 和 b 做缓存，把 add(a, b) 返回的 Promise 存进 Map，键用两个数拼成的字符串。缓存 Promise 而不是结果，同一对数在计算中再次被请求时，会复用同一个正在进行的 Promise，不会重复调用。