乐趣区

生成器与迭代器

jiezi

之前的文章 写到了 Generator 与异步编程的关系，其实简化异步编程只是 Generator 的“副业”，Generator 本身却不是为异步编程而存在。

生成器函数

我们看 Generator 自身的含义——生成器，就是产生序列用的。比如有如下函数：

function* range(start, stop) {for (let item = start; item < stop; ++item) {yield item;}
}

range 就是一个生成器函数，它自身是函数可以调用（typeof range === 'function' // true），但又与普通函数不同，生成器函数（GeneratorFunction）永远返回一个生成器（Generator）

注：我们通常所说的 Generator 实际上指 生成器函数 （GeneratorFunction），而把 生成器函数 返回的对象称作 迭代器（Iterator）。由于感觉“生成器函数”返回“生成器”这句话有些拗口，下文沿用生成器和迭代器的说法。

迭代器

初次调用生成器实际上不执行生成器函数的函数体，它只是返回一个迭代器，当用户调用迭代器的 next 函数时，程序才开始真正执行生成器的函数体。当程序运行到 yield 表达式时，会将 yield 后面表达式的值作为 next 函数的返回值（的一部分）返回，函数本身暂停执行。

const iterator = range(0, 10); // 获取迭代器
const value1 = iterator.next().value; // 获取第一个值 => 0
const value2 = iterator.next().value; // 获取第二个值 => 1

next 返回值是一个对象，包含两个属性 value 和 done。value 即为 yield 后面表达式的值，done 表示函数是否已经结束（return）。如果函数 return（或执行到函数尾退出，相当于 return undefined），则 done 为 true，value 为 return 的值。

for…of 是遍历整个迭代器的简单方式。

生成器的用处

上面说到，生成器就是生成序列用的。但是与直接返回数组不同，生成器返回序列是一项一项计算并返回的，而返回数组总是需要计算出所有值后统一返回。所以至少有两种情况应该考虑使用生成器。

  • 序列有无限多项，或者调用者不确定需要多少项

range(0, Infinity) 是允许的，因为生成器没生成一个值就会暂停执行，所以不会造成死循环，可以由调用者选择何时停止。

注意此时不能使用 for...of，因为迭代器永远不会 done

  • 计算每一项耗时较长

如果计算一项的值需要 1ms，那么计算 1000 项就需要 1s，如果不将这 1s 拆分，就会导致浏览器卡顿甚至假死。这时可以用生成器每生成几项就将控制权交还给浏览器，用于响应用户事件，提升用户体验（当然这里更有效的方法是将代码放到 Web Worker 里执行）

  • 节省内存

如果序列很长，直接返回数组会占用较大内存。生成器返回值是一项一项返回，不会一次性占用大量内存（当然生成器为了保留执行上下文比通常函数占用内存更多，但是它是个定值，不随迭代次数增加）

列：使用生成器实现懒加载的 map、filter

Array#map、Array#filter 是 ES5 引入的（绝对不算新的）两个非常常用的函数，前者将数组每一项通过回调函数映射到新数组（值变量不变），后者通过回调函数过滤某些不需要的项（量变值不变），他们都会生成新的数组对象，如果数组本身较长或者写了很长的 map、filter 调用链，就可能造成内存浪费。

这时就可以考虑使用生成器实现这两个函数，非常简单：

function* map(iterable, callback) {
  let i = 0;
  for (const item of iterable) {         // 遍历数组
    yield callback(item, i++, iterable); // 获取其中一项，调用回调函数，yield 返回值
  }
}

function* filter(iterable, callback) {
  let i = 0;
  for (const item of iterable) {         // 遍历数组
    if (callback(item, i++, iterable)) { // 获取其中一项，调用回调函数
      yield item;                        // 仅当回调函数返回真时，才 yield 值
    }
  }
}

可以看到我在代码中写的是“可迭代的”（iterable），而不限于数组（由于实现了 Symbol.iterator 所以数组也是可迭代对象）。比如可以这么用：

const result = map(// (1)
  filter(// (2)
    range(1, 10000),    // (3)
    x => x % 2 === 0,
  ),
  x => x / 2,
)
console.log(...result); // (4)

注意，程序在解构运算符 ...result 这一步才真正开始计算 result 的值（所谓的懒加载），而且它的值也是一个一个计算的：

  1. (3)生成迭代器，提供值给 (2)；(2) 提供值给(1)
  2. (1)中的 result 也是迭代器，在这一步所有函数都没有真正开始执行，因为没有任何代码问他们索要值。
  3. (4)中的扩展运算符对迭代器 result 进行了求值，生成器真正开始执行。
  4. result 的值来自于 (1)，于是 (1) 首先开始执行。
  5. (1)中 map 函数使用 for...of 遍历 (2) 提供的迭代器，于是 (2) 开始执行
  6. (2)中 filter 函数使用 for...of 遍历 (3) 提供的迭代器，于是 (3) 开始执行
  7. (3)中 range 函数开始执行，循环得到第一个值 1。遇到 yield 关键字，将值 1 输出给(4)
  8. (4)中的 for...of 获得一个值 1，执行函数体。callback 返回 false，忽略之。回到 for...of，继续问 (5) 索要下一个值
  9. range 输出第二个值 2
  10. (4)中的 for...of 获得一个值 2，执行函数体。callback 返回 true，将值 2 输出给 (3)
  11. (3)中的 for...of 获得一个值 2，执行函数体得到 1。将值 1 输出给(4)，console.log 获得第一个参数
  12. (3)检测 result 还没有结束（done 为 false），问 result 索要下一个值。
  13. 回到第 4 步循环，直至 (3) 中的循环结束函数体退出为止，(3)返回的迭代器被关闭
  14. (2)中 for...of 检测到迭代器已被关闭（done 为 true），循环结束，函数退出，(2)返回的迭代器被关闭
  15. 同理 (1) 返回的迭代器被关闭
  16. (4)中解构运算符检测到 result 已关闭，结构结束。将结构得到的所有值作为 console.log 的参数列表输出

总结一下，代码执行顺序大概是这样：(3) -> (2) -> (1) -> (4) -> (1) -> (2) -> (3) -> (2) -> (3) -> (2) -> (1) -> (4) -> (1) -> (2) -> (3) -> ……

是不是相当复杂？异步函数中“跳来跳去”的执行顺序也就是这么来的

生成器函数的链式调用

这样的代码 map(filter(range(1, 100), x => x % 2 === 0), x => x / 2) 似乎有些 d 疼，好像又看到了被回调函数支配的恐惧。虽然有人提出了管道符的提议，但这种 stage 1 的提议被标准接受直至有浏览器实现实在是遥遥无期，有没有其他办法呢？

普通函数可以简单的通过在类中返回 this 实现函数的链式调用（例如经典的 jQuery），但是这点在生成器中不适用。我们前面说过生成器函数本身永远返回一个迭代器，而生成器中的 return 语句实际上是关闭迭代器的标志，return this 实际代表 {value: this, done: true}。生成器中的 return 和普通函数用法相近但实际含义大大不同。

链式调用需要函数的返回值是个对象，并且对象中包含可链式调用的所有函数。生成器函数返回的迭代器本身就是一个对象，很容易想到改变对象的原型实现。

迭代器有如下原型继承链：

迭代器对象 -> 生成器.prototype -> 生成器.prototype.prototype（Generator）-> Object -> null

可以看到，生成器返回的迭代器对象就好像是被生成器 new 出来的一样（但是生成器不是构造函数不能被 new）。但是总之我们可以通过给生成器函数的 prototype 添加方法实现给迭代器添加方法的效果。实现如下

function* range(start, stop) {for (let item = start; item < stop; ++item) {yield item;}
}

function* map(callback) {
  let i = 0;
  for (const item of this) {yield callback(item, i++, this);
  }
}

function* filter(callback) {
  let i = 0;
  for (const item of this) {if (callback(item, i++, this)) {yield item;}
  }
}

[range, map, filter].forEach(x => Object.assign(x.prototype, { range, map, filter}));

// 使用
const result = range(1, 100)
  .filter(x => x % 2 === 0)
  .map(x => x / 2);

console.log(...result);

完

笔者业 (xian) 余(de)时 (dan) 间(teng)使用迭代器实现了几乎所有 ES7 中 Array 的成员方法和静态方法，广而告之，欢迎来喷：https://github.com/CarterLi/q…

退出移动版