<jupyter_start><jupyter_text>Iterable 与 Iterator 在我们开始学习数据容器之前，先来学习 *iterable* 和 *iterator* 的概念。理解这两个概念就能理解 `for...in` 循环的本质，同时 *iterable* 也是所有数据容器的共性特征。  `for...in` 循环的本质 *Iterable* 和 *iterator* 这两个词，来源于动词 *iterate*，*iterate* 与其名词形式 *iteration* 的含义就是“重复”，重复做一件事或者重复一句话；在计算机领域通常翻译为“迭代”，对一组数据逐个执行特定操作都可以称为 *iteration*，比如你已经熟悉的 `for...in` 循环就是例子：<jupyter_code>for i in [1, 2, 3]:
    print(i)<jupyter_output>1
2
3<jupyter_text>上面的代码本质是这样：1. 取列表 `[1, 2, 3]` 中的第一个元素（`1`），令 `i = 1`；2. 执行 `print(i)`，打印出 `i` 的值；3. 取列表 `[1, 2, 3]` 中的“下一个”元素，令 `i` 的值等于该元素；4. 重复步骤 2 至 3，直到列表中没有元素（即“下一个”元素为空值）。 这个概念抽象一下，迭代的本质是对一组数据执行特定操作，确保所有数据都被操作正好一次，不重不漏。这是非常常用的一种场景，这里面有两个要素：* 被迭代处理的数据集 `X`，其中包含若干元素，可以通过“给我下一个元素”这样的指令逐个取出这些元素，确保不重不漏；* 需要对 X 的每个元素执行的操作 `f()`。只要具备这两个要素，我们就可以通过下面这样的代码来遍历操作 X 中的所有元素：```pythonfor x in X:    f(x)``` Python 中的 *iterable* 和 *iterator* 就是从上面描述的抽象模型里发展而来的设计，给出了在 Python 中做迭代的标准模式。* 一个对象 X 是“**可迭代的**（*iterable*）”，就是说这个对象支持一个名为 `__iter__()` 的方法，这个方法返回一种叫“**迭代器**（*iterator*）”的对象；* 一个**迭代器**（*ietrator*）必须支持一个名为 `__next__()` 的方法，这个方法每次返回 X 里的下一个元素，直到所有元素被遍历正好一次。 而我们用了好多次的 `for...in` 循环实际上是这么实现的：1. 获得 X 的迭代器 `iter = X.__iter__()`；2. 获得 X 中下一个元素 `x = iter.__next__()`；3. 如果 x 不为空，则执行 `f(x)` 然后重复步骤 2~3；否则结束。 这下我们终于可以揭晓了：**凡是 *iterable* 的东西，都可以放在 `for...in` 循环中进行迭代操作**。我们后面要介绍的数据容器（*list*、*tuple*、*dictionary*、*set*）都是 *iterable*，所以都可以用 `for-in` 来遍历。另外，X 可以同时支持 `__iter__()` 和 `__next__()`，这样 X 既是 *iterable* 也是自己的 *iterator*，可以省略取迭代器的步骤，直接用 `__next__()` 开始，上面列出的几种内置数据容器都是这么做的。下面我们创建一些自己的 *iterable* 试试。  迭代器例一：平方数序列 第一个例子我们返回自然数的平方数序列，也就是 `1, 4, 9, 16, 25, ...`*Iterator* 是一种对象，所以首先我们要使用 `class` 关键字来定义一个类：<jupyter_code>class squares:
    # 实例变量 self.base 用来记录当前平方数的基数，这个基数应该从 1 开始逐渐递增。
    # 然后定义了三个标准方法：
    #   __init__() 把 self.base 设置为初始值 0；
    #   __iter__() 返回迭代器，这里就是自己，我们直接返回 self；
    #   __next__() 是迭代器主方法，这里我们先把 self.base 加一，然后返回它的平方，由于初始为 0，第一次调用返回的是 1 的平方。
    # 最后定义 next 作为 __next__ 的别名，方便调用（也与 Python 2.x 兼容）。
    def __init__(self):
        self.base = 0
        
    def __iter__(self):
        return self

    def __next__(self):
        self.base += 1
        return self.base * self.base

    next = __next__

# 创建 squares 类的实例对象 iter，然后就可以调用其 next() 方法来迭代
iter = squares()
iter.next()
iter.next()
iter.next()<jupyter_output><empty_output><jupyter_text>注意到我们上面没有任何约束条件，这个迭代可以无限进行下去，如果我们把这个迭代器用在 `for...in` 循环中的话就会出现无限循环（直到计算机耗尽内存资源），所以通常我们会希望有个约束条件让迭代到一定程度就停下来，我们可以改写一下上面的代码：<jupyter_code>class squares:
    # 这次我们的初始化方法增加了一个参数 high
    # 初始化时将其保存在一个新增实例变量 self.high 中，限制迭代时 self.base 不能超过这个数
    def __init__(self, high):
        self.base = 0
        self.high = high
        
    def __iter__(self):
        return self

    # 在迭代器主方法里加入判断，如果 self.base 超过了 self.high 就扔出一个 StopIteration 异常
    def __next__(self):
        self.base += 1
        if self.base > self.high:
            raise StopIteration
        else:
            return self.base * self.base

    next = __next__

# 这次我们实例化时要传入一个参数来指定 self.high 的值
# 这将使得我们调用三次 next()，输出 1，4，9 之后再调用就不会有返回值
iter = squares(3)<jupyter_output><empty_output><jupyter_text>这次我们的迭代器有“边界”了，就可以将其直接用在 `for...in` 循环中，`for...in` 循环会在碰到 `StopIteration` 时自动终止：<jupyter_code>for n in squares(3):
    print(n)<jupyter_output>1
4
9<jupyter_text>迭代器例二：斐波那契数列 第二个例子我们来实现一个**斐波那契**（*Fibonacci*）数列，这个数列之前已经见过，其特点是每一个元素它前面两个元素之和，写下来大致是这个样子的：`1, 1, 2, 3, 5, 8, 13, 21, ...`基本的迭代器实现和例一没啥区别，如果前面的内容没有什么问题，这个也就很好理解：<jupyter_code>class fib:
    def __init__(self):
        self.prev = 0
        self.curr = 1

    def __iter__(self):
        return self

    def __next__(self):
        self.prev, self.curr = self.curr, self.prev + self.curr
        return self.prev<jupyter_output><empty_output><jupyter_text>可以看到我们这个实现也是可以无限迭代的，如果我们需要限制迭代次数，可以像例一那样改写，但是大多数情况下不需要，因为这种操作太常见了，早就有了标准化的通用解决方案——这也是学编程的一个窍门：凡是看上去很“常规”和“常见”的需求，一般都会有优秀的通用解决方案，我们找出来用比自己写好，这叫“**不重复发明轮子**（*Don't Reinvent The Wheel*）”原理。这些标准解决方案在 `itertools` 模块中，用于对无限迭代器进行切片的方法叫做 `islice()`。`islice()` 做的事情相当于从迭代器产生的无限序列中切出一段来，它返回的也是一个迭代器，返回的迭代器输出的就是有头有尾、有限的序列了。`islice()` 接受三个参数：一个迭代器实例，切片的起始和结束序号（序号从 0 开始算）；切的时候和 `range()` 函数的算法一样，包含起始序号那一项，但不包括结束序号的一项。比如 `islice(f, 0, 10)` 就是从迭代器 `f` 生成的序列中切出第 1 到第 10 项，返回这 10 项对应的有限迭代器。其实 `islice()` 还可以有第四个参数：步长 `step`，缺省值为 1，就是起始到结束范围内每一项都保留；如果指定了别的 `step` 值，那么就是每隔 `step-1` 项输出一项。基本逻辑和 `range()` 函数一样。因为 `islice()` 返回的还是迭代器，所以可以直接用于 `for...in` 循环中。<jupyter_code>from itertools import islice

f = fib()
for n in islice(f, 0, 10):
    print(n)<jupyter_output>1
1
2
3
5
8
13
21
34
55<jupyter_text>`islice()` 帮我们做了限界这样的事情，我们在写迭代器的时候就不用考虑了，只要把迭代的算法写清楚，要截取一段来用的话用 `islice()` 就好了。`itertools` 里还有不少很有用的东西，比如 `cycle()` 可以循环一个有限的迭代器得到一个无限版本：<jupyter_code>from itertools import cycle
# 数组既是 iterable 也是 iterator，cycle() 从输入的有限数组循环创建一个无限的 iterator
colors = cycle(['red', 'yellow', 'green'])
# 用 islice() 截取这个无限迭代器的前 10 个，然后用 list() 把输出的迭代器转换成列表
list(islice(colors, 0, 7))<jupyter_output><empty_output><jupyter_text>更多关于 `itertools` 库的说明可以参考 [官方文档](https://docs.python.org/3.7/library/itertools.html)。  One More Thing... 不知道你有没有在书写上面的代码时觉得每次要定义个 `class` 还有 `__iter__()` `__next__()` 这样的“八股”很啰嗦？恭喜你，很有优秀程序员的潜质，事实上上面代码里真正有价值的就是 `__next__()` 的实现部分，所以 Python 提供了一种特殊的迭代器（*iterator* ）写法，叫做“**生成器**（*generator*）”，更紧凑更精简。比如上面的 Fibonacci 数列，用生成器来写就是这样的：<jupyter_code>def fib():
    prev, curr = 0, 1
    while True:
        # 这个 yield 是一切魔法的核心，下面解释
        yield curr
        prev, curr = curr, prev + curr

f = fib()
list(islice(f, 0, 10))
type(fib())<jupyter_output><empty_output><jupyter_text>是不是清爽漂亮了很多？但是这个魔法的原理是啥呢？首先我们来看看 `fib()` 这个定义：* 一个 *generator* 定义就是一个函数的定义，但这是个特殊的函数，函数体里没有 `return`，取而代之的是特殊的关键字 `yield`；* 解释器会自动把任何包含 `yield` 的函数包装成 `generator`（一种特殊的 *iterator*）类型的对象，并将此对象作为函数的返回值，所以上面的 `f` 变量其实还是个 *iterator*。然后就是 `yield` 这个魔法的关键了。`yield` 和 `return` 相当，也会从函数中返回一些值，但不一样的是：`return` 返回值的同时彻底终止了函数，而 `yield` 则是“暂停”了函数执行，保存了函数当时的所有状态（比如所有局部变量的值），以后再返回到 `yield` 的下一行继续执行——这个“以后”到底是什么时候呢？聪明的你一定可以猜到，就是我们下一次调用 `__next__()` 的时候！小结一下，上面的代码定义了一个函数 `fib()`，调用这个函数会返回一个生成器（一种特殊的迭代器）：* 当我们第一次调用这个生成器的 `__next__()` 的时候，会执行 `fib()` 函数的函数体直到碰到 `yield` 语句，`yield` 的返回值就是这次调用 `__next__()` 的结果；同时解释器暂停函数 `fib()` 的运行并把状态保存下来；* 当我们再次调用生成器的 `__next__()` 的时候，解释器重新唤醒函数 `fib()`，恢复保存的状态，并从上次 `yield` 的下一行继续执行，直到再碰到 `yield`，`yield` 的返回值就是这次调用 `__next__()` 的结果；* 每次调用生成器的 `__next__()` 时重复上述操作。是不是略有点烧脑？在这里你一定要烧清楚。这次清楚了后面就简单，否则这一类的逻辑还会有很多，始终是要迈过的坎，而且生成器很有用，很多地方都会碰到。  练习 尝试定义可以生成素数的迭代器和生成器，并利用之输出前 10 个素数。  参考答案 我们先来看迭代器的写法，用到了我们之前写过的 `is_prime()` 算法：<jupyter_code>from math import sqrt
from itertools import islice

class primes:
    def __init__(self):
        self.next = 2

    def __iter__(self):
        return self

    def _is_prime(self, n):
        if n < 2:
            return False

        if n in (2, 3):
            return True

        for i in range(2, int(sqrt(n)) + 1):
            if n % i == 0:
                return False

        return True

    def __next__(self):
        n = self.next
        while not self._is_prime(n):
            n += 1

        self.next = n + 1
        return n
    
list(islice(primes(), 0, 10))<jupyter_output><empty_output><jupyter_text>参照前面的例子，将上面这个 `iterator` 类改写为 `generator` 应该也不难，我们把这个作业留给你。下面额外给出一种 *generator* 的写法，这个写法用到了著名的**埃拉托斯特尼筛法**（*Sieve Of Eratosthenes*），是快速计算素数的经典算法，关于筛法的基本介绍可以参考[维基百科](https://zh.wikipedia.org/zh-cn/%E5%9F%83%E6%8B%89%E6%89%98%E6%96%AF%E7%89%B9%E5%B0%BC%E7%AD%9B%E6%B3%95)。我们在代码的每一步都写了简要注释，主要戏法在函数体里定义的那个 `D`，这是一个 `dictionary` 类型的数据容器，如果看不明白也没关系，在学完后面几种数据容器之后再来看，就应该容易一些了。<jupyter_code>def primes():
    """Generator which yields the sequence of prime numbers via the Sieve of Eratosthenes."""
    D = {}  # map composite integers to primes witnessing their compositeness
    q = 2   # first integer to test for primality
    while 1:
        if q not in D:
            yield q        # not marked composite, must be prime
            D[q*q] = [q]   # first multiple of q not already marked
        else:
            for p in D[q]: # move each witness to its next multiple
                D.setdefault(p+q,[]).append(p)
            del D[q]       # no longer need D[q], free memory
        q += 1
from itertools import islice
list(islice(primes(), 0, 20))<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1408294248333745, 'fraction_numerical': 0.0182670945445569, 'mean_word_length': 4.775481111903065, 'pattern_counts': {'":': 0, '<': 39, '<?xml version=': 0, '>': 39, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '10', 'dir': 'jupyter-structured-clean-dedup', 'id': '117309', 'license': 'MIT', 'n_tokens_mistral': 5156, 'n_tokens_neox': 5425, 'n_words': 637, 'path': 'p2-7-iterable-iterator.ipynb', 'repo_name': 'honkersglory/pilot', 'size': '8102'}