search

shaozj / blog

blog
87 stars 4 forks source link

ES6 iterator 和 generator #33

Open shaozj opened 5 years ago

shaozj commented 5 years ago

ES6 iterator 和 generator

ES6 引入了新的遍历数据的机制 Iterator 迭代器。它是一种接口，为各种不同的数据结构提供统一的访问机制。任何数据结构只要部署 Iterator 接口，就可以完成遍历操作（即依次处理该数据结构的所有成员）。基于 iterator 机制，es6 提供了很多新的操作符，例如 for of 以及解构、展开操作符等。
Generator 是 ES6 提供的一种异步编程解决方案，类似于其他语言中的协程。它是的一个函数可以在执行过程中中止，之后重新回来继续执行，而不是一次性执行完。执行 Generator 函数会返回一个遍历器对象，也就是说，Generator 函数除了状态机，还是一个遍历器对象生成函数。返回的遍历器对象，可以依次遍历 Generator 函数内部的每一个状态。
本文将基于例子阐述 iterator 和 generator 的机制和用法，主要是用法😁。

实现 ArrayList 和 LinkedList

LinkedList 和 ArrayList 是两种基础的数据结构。它们都可以归类为 List 数据结构。不同处在于查询、插入、删除的复杂度不同。那么我们先实现一下两个数据结构试试，为了简单起见，只实现 get 方法，毕竟我们只要要阐述下 iterator 和 generator 的用法，意思一下即可：

class ArrayList {
  constructor(data) {
    this.list = [...data];
    this.size = data.length;
  }

  get(index) {
    return this.list[index];
  }
}
class LinkedList {
  constructor(data) {
    let last = null;
    for (let i = data.length - 1; i >= 0; i--) {
      const el = { data: { value: data[i] }, next: last };
      last = el;
    }
    this.head = last;
    this.size = data.length;
  }

  get(index) {
    let counter = 0;
    let el = this.head;

    while (counter < index) {
      el = el.next;
      counter++;
    }

    return el.data;
  }
}

可以看到，对于 LinkedList，其查找复杂度是 O(N) 的。
现在我们看下面一个例子，我们要从两个 List 对象中过滤出小于 3 的数：

const list1 = new ArrayList([1, 2, 3]);
const list2 = new LinkedList([1, 2, 3]);

const filtered1 = [];
for (let i = 0; i < list1.size; i++) {
  const element = list1.get(i);
  if (element.value < 3) {
    filtered1.push(element);
  }
}

const filtered2 = [];
for (let i = 0; i < list2.size; i++) {
  const element = list2.get(i);
  if (element.value < 3) {
    filtered2.push(element);
  }
}

乍一看好像没啥问题，但是对于 LinkedList，我们在遍历其元素时做了大量的重复工作，每次我们都重新遍历 list 去寻找 index 对应的值，这是非常低效的。为了解决这个问题，我们可以实现一个 forEach 方法：

class ArrayList {
  constructor(data) {
    this.list = data.map(value => ({ value }));
    this.size = data.length;
  }

  get(index) {
    return this.list[index];
  }

  forEach(fn) {
    for (let i = 0; i < this.list.length; i++) {
      fn(this.list[i]);
    }
  }
}

class LinkedList {
  constructor(data) {
    let last = null;
    for (let i = data.length - 1; i >= 0; i--) {
      const el = { data: { value: data[i] }, next: last };
      last = el;
    }
    this.head = last;
    this.size = data.length;
  }

  get(index) {
    let counter = 0;
    let el = this.head;

    while (counter < index) {
      el = el.next;
      counter++;
    }

    return el.data;
  }

  forEach(fn) {
    let element = this.head;

    while (element !== null) {
      fn(element.data);
      element = element.next;
    }
  }
}

看上去很完美，我们只要调用 forEach 方法来遍历 list 即可：

const filtered = [];
list.forEach((element) => {
  if (element.value < 3) {
    filtered.push(element);
  }
});

但是，这个方法还有两个缺点没有解决：

这个时候，就需要我们的 iterator 上场了。

实现 list 的 iterator

ES6 规定，默认的 Iterator 接口部署在数据结构的 Symbol.iterator 属性，或者说，一个数据结构只要具有 Symbol.iterator 属性，就可以认为是“可遍历的”（iterable）。Symbol.iterator 属性本身是一个函数，就是当前数据结构默认的遍历器生成函数。执行这个函数，就会返回一个遍历器。至于属性名 Symbol.iterator，它是一个表达式，返回 Symbol 对象的iterator 属性，这是一个预定义好的、类型为 Symbol 的特殊值。

class ArrayList {
  constructor(data) {
    this.list = data.map(value => ({ value }));
    this.size = data.length;
  }

  get(index) {
    return this.list[index];
  }

  forEach(fn) {
    for (let i = 0; i < this.list.length; i++) {
      fn(this.list[i]);
    }
  }

  [Symbol.iterator]() {
    const self = this;
    let i = 0;

    return {
      next() {
        let value;
        let done = true;
        if (self.list[i] !== undefined) {
          value = self.list[i];
          done = false;
          i += 1;
        }
        return {
          value,
          done
        };
      }
    };
  }
}

class LinkedList {
  constructor(data) {
    let last = null;
    for (let i = data.length - 1; i >= 0; i--) {
      const el = { data: { value: data[i] }, next: last };
      last = el;
    }
    this.head = last;
    this.size = data.length;
  }

  get(index) {
    let counter = 0;
    let el = this.head;

    while (counter < index) {
      el = el.next;
      counter++;
    }

    return el.data;
  }

  forEach(fn) {
    let element = this.head;

    while (element !== null) {
      fn(element.data);
      element = element.next;
    }
  }

  [Symbol.iterator]() {
    let el = this.head;

    return {
      next() {
        let value;
        let done = true;

        if (el !== null) {
          value = el.data;
          done = false;
          el = el.next;
        }
        return {
          value,
          done
        };
      }
    };
  }
}

此时，我们可以使用 for of 和展开操作符了：

const list = new LinkedList();

for (let element of list) {
    console.log(element);
}

console.log([...list]);

到此，我们发现的问题都用 iterator 解决了。然而我们实现的 next 方法是易出错的，而且看上去很不直观。这个时候，generator 就要派上用场了。

使用 generator

ES6 引入了 generator 函数，它和普通函数类似（不过函数前面需要加个 *），但是能在一次执行中多次返回。这是因为它内部会返回一个 generator 对象，这个对象实现了 iterator 协议，也就是说，它返回的也是一个迭代器对象。在 generator 函数中，提供了 yield 操作符。yield操作符表达式对应了每次调用 next 方法得到的结果。这意味着我们能像写 forEach 一样，直接在一个循环中调用 yield 来实现迭代器：

class ForEachLinkedListIterator {
  *[Symbol.iterator]() {
    let element = this.head;

    while (element !== null) {
      yield element.data;
      element = element.next;
    }
  }
}

class ForEachArrayListIterator {
  *[Symbol.iterator]() {
    for (let i = 0; i < this.list.length; i++) {
      yield this.list[i];
    }
  }
}

好，到此为止，我们基于 iterator 和 generator 实现了我们想要的数据结构。希望通过该例子，你能对 iterator 和 generator 有了一个直观的理解。当然，本文对于 iterator 和 generator 的基础阐述是相当不够的，这些可以去 mdn 上查看。

参考文献

nelling commented 5 years ago

好文 👍