JavaScript惰性扁平化生成器：优化多倍数求和代码

我已经完成了Exercism上的sum-of-multiples习题，现有两个实现版本，但现在想让代码具备更强的惰性求值特性——能不能扁平化range生成器，不用每次都把它转成数组[...range(n, limit_in, n)]？

现有版本代码 #

版本一

function sum(multiples, limit_in) {
  return [...multiples.map(n => [...range(n, limit_in, n)])
    .reduce((numbers, array) => {
      array.forEach(value => numbers.add(value));
      return numbers;
    }, new Set())
    .values()]
    .reduce((sum, n) => sum + n, 0);
}

function* range(start, stop, step = 1) {
  if (stop == null) {
    stop = start;
    start = 0;
  }

  for (let i = start; step > 0 ? i < stop : i > stop; i += step) {
    yield i;
  }
}

const result = sum([5, 6, 8], 150);
console.log(result); // The result is 4419

版本二

function sum(multiples, limit_in) {
  return [...multiples.flatMap(n => [...range(n, limit_in, n)])
    .reduce((numbers, value) => {
      numbers.add(value);
      return numbers;
    }, new Set())
    .values()]
    .reduce((sum, n) => sum + n, 0);
}

function* range(start, stop, step = 1) {
  if (stop == null) {
    stop = start;
    start = 0;
  }

  for (let i = start; step > 0 ? i < stop : i > stop; i += step) {
    yield i;
  }
}

const result = sum([5, 6, 8], 150);
console.log(result); // Result 4419

优化方案：全程惰性迭代，避免中间数组 #

当然可以！核心思路是直接遍历每个range生成器的迭代器，不用先转成数组。我们可以改写sum函数，直接迭代每个multiples对应的range生成器，把值加入Set，最后再迭代Set求和——全程没有中间数组，完全保持惰性。

优化后的代码：

function sum(multiples, limit_in) {
  const uniqueMultiples = new Set();
  // 直接遍历每个range生成器，惰性取值
  for (const n of multiples) {
    for (const value of range(n, limit_in, n)) {
      uniqueMultiples.add(value);
    }
  }
  // 迭代Set求和，同样惰性
  let total = 0;
  for (const num of uniqueMultiples) {
    total += num;
  }
  return total;
}

function* range(start, stop, step = 1) {
  if (stop == null) {
    stop = start;
    start = 0;
  }

  for (let i = start; step > 0 ? i < stop : i > stop; i += step) {
    yield i;
  }
}

const result = sum([5, 6, 8], 150);
console.log(result); // 输出 4419

为什么这更惰性？ #

• 原版本里的[...range(...)]会一次性把生成器的所有值都提取出来存入数组，提前占用内存；优化后只有在遍历到对应值时才会让生成器产生下一个值。
• 整个流程没有创建任何中间数组（比如map/flatMap返回的数组），内存效率更高，尤其是当limit_in很大的时候优势明显。

如果想保持函数式风格，也可以写一个扁平化生成器的生成器函数：

function* flatGenerate(generators) {
  for (const gen of generators) {
    yield* gen;
  }
}

function sum(multiples, limit_in) {
  const uniqueMultiples = new Set();
  for (const val of flatGenerate(multiples.map(n => range(n, limit_in, n)))) {
    uniqueMultiples.add(val);
  }
  return [...uniqueMultiples].reduce((a, b) => a + b, 0);
}

这个版本用yield*来扁平化多个生成器，同样避免了中间数组，保持惰性——唯一的数组是最后转Set求和时的[...uniqueMultiples]，如果想完全避免，还是用前面的for循环求和更彻底。

内容的提问来源于stack exchange，提问作者Laszlo