极客时间返利平台,你可以在上边通过山月的链接购买课程,并添加我的微信 (shanyue94) 领取返现。

# 实现一个异步的 sum/add

更多描述

这是一道字节跳动的面试题目,见面经 某银行前端一年半经验进字节面经 (opens new window)。山月认为这也是一道水平较高的题目,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 (opens new window)

Author

回答者: mtt3366 (opens new window)

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

先来一个串行的写法:

function sum(arr) {
  if (arr.length === 1) return arr[0];
  return arr.reduce((x, y) => Promise.resolve(x).then((x) => add(x, y)));
}

接下来是并行的写法:

function add(x, y) {
  return Promise.resolve(x + y);
}

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

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

如果需要控制并发数,则可以先实现一个 pMap 用以控制并发

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

Author

回答者: Asarua (opens new window)

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

串行

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

@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 new window)

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);
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 new window)

// 这是一道字节跳动的面试题目,见面经 某银行前端一年半经验进字节面经。山月认为这也是一道水平较高的题目,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)));

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

Last Updated: 4/27/2022, 11:56:45 AM