xuzhengfu / pilot

进入编程世界的第一课
1 stars 0 forks source link

p2-7-iterable-iterator 第七章 Iterable 与 Iterator #37

Open xuzhengfu opened 4 years ago

xuzhengfu commented 4 years ago

1. 概述

在我们开始学习数据容器之前,先来学习 iterable 和 iterator 的概念。

理解这两个概念就能理解 for...in 循环的本质,同时 iterable 也是所有 数据容器 的共性特征。

2. for...in 循环的本质

Iterable 和 Iterator 这两个词,来源于动词 iterate,iterate 与其名词形式 iteration 的含义就是 “重复”,重复做一件事或者重复一句话;在计算机领域通常翻译为 “迭代”,对一组数据逐个执行特定操作都可以称为 iteration,比如你已经熟悉的 for...in 循环就是例子。

for i in [1, 2, 3]:
    print(i)

上面的代码本质是这样:

  1. 取列表 [1, 2, 3] 中的第一个元素(1),令 i = 1
  2. 执行 print(i),打印出 i 的值;
  3. 取列表 [1, 2, 3] 中的 “下一个” 元素,令 i 的值等于该元素;
  4. 重复步骤 2 至 3,直到列表中没有元素(即 “下一个” 元素为空值)。

这个概念抽象一下,迭代的本质是对 一组数据 执行 特定操作,确保所有数据都被操作正好一次,不重不漏。这是非常常用的一种场景,这里面有两个要素:

  1. 被迭代处理的数据集 X,其中包含若干元素,可以通过 “给我下一个元素” 这样的指令逐个取出这些元素,确保不重不漏;
  2. 需要对 X 的每个元素执行的操作 f()

只要具备这两个要素,我们就可以通过下面这样的代码来遍历操作 X 中的所有元素:

for x in X:
  f(x)

Python 中的 iterable 和 iterator 就是从上面描述的抽象模型里发展而来的设计,给出了在 Python 中做迭代的标准模式。

  • 一个对象 X 是 “可迭代的(iterable)”,就是说这个对象支持一个名为 __iter__() 的方法,这个方法返回一种叫 “迭代器(iterator)” 的对象;
  • 一个迭代器(iterator)必须支持一个名为 __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__() 开始,上面列出的几种 内置数据容器 都是这么做的。

下面我们创建一些自己的 Iterator 试试。

3. 迭代器例一:平方数序列

第一个例子我们返回自然数的平方数序列,也就是 1, 4, 9, 16, 25, ...

  1. 用一个实例变量 self.base 来记录当前平方数的基数,这个基数应该从 1 开始逐渐递增。
  2. 然后定义三个标准方法:
    • __init__() 把 self.base 设置为初始值 0;
    • __iter__() 返回迭代器,这里就是自己,我们直接返回 self;
    • __next__() 是迭代器主方法,这里我们先把 self.base 加一,然后返回它的平方。
    • 最后定义 next 作为 __next__ 的别名,方便调用(也与 Python 2.x 兼容)。
class squares:
    def __init__(self):
        self.base = 0

    def __iter__(self):
        return self

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

    next = __next__
> iter = squares()
> iter.next()

注意到我们上面没有任何约束条件,这个迭代可以无限进行下去,如果我们把这个 迭代器 用在 for...in 循环中的话就会出现无限循环(直到计算机耗尽内存资源),所以通常我们会希望有个 约束条件 让迭代到一定程度就停下来,我们可以改写一下上面的代码:

  1. 这次我们在初始化方法 __init__ 当中增加一个参数 high
  2. 初始化时将其保存在一个新增实例变量 self.high 中,限制迭代时 self.base 不能超过这个数
  3. 在迭代器主方法里加入判断,如果 self.base 超过了 self.high 就扔出一个 StopIteration 异常
class squares:
    def __init__(self, high):
        self.base = 0
        self.high = high

    def __iter__(self):
        return self

    def __next__(self):
        self.base += 1
        if self.base > self.high:
            raise StopIteration
        else:
            return self.base * self.base

    next = __next__
iter = squares(3)

这将使得我们调用三次 next(),输出 1,4,9 之后再调用就不会有返回值

这次我们的 迭代器 有 “边界” 了,就可以将其直接用在 for...in 循环中,for...in 循环会在碰到 StopIteration 时自动终止:

for n in squares(3):
    print(n)

4. 迭代器例二:斐波那契数列

第二个例子我们来实现一个斐波那契(Fibonacci)数列,这个数列之前已经见过,其特点是每一个元素是它前面两个元素之和,写下来大致是这个样子的:1, 1, 2, 3, 5, 8, 13, 21, ...

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

可以看到我们这个实现也是可以无限迭代的,如果我们需要限制迭代次数,可以像例一那样改写,但是大多数情况下不需要,因为这种操作太常见了,早就有了标准化的通用解决方案 —— 这也是学编程的一个窍门:凡是看上去很 “常规” 和 “常见” 的需求,一般都会有优秀的通用解决方案,我们找出来用比自己写好,这叫 “不重复发明轮子(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 循环中。

from itertools import islice

f = fib()
for n in islice(f, 0, 10):
    print(n)

islice() 帮我们做了 限界 这样的事情,我们在写迭代器的时候就不用考虑了,只要把迭代的算法写清楚,要截取一段来用的话用 islice() 就好了。itertools 里还有不少很有用的东西,比如 cycle() 可以循环一个有限的迭代器得到一个无限版本:

from itertools import cycle
# 数组既是 iterable 也是 iterator,cycle() 从输入的有限数组循环创建一个无限的 iterator
colors = cycle(['red', 'yellow', 'green'])
# 用 islice() 截取这个无限迭代器的前 7 个,然后用 list() 把输出的迭代器转换成列表
list(islice(colors, 0, 7))

更多关于 itertools 库的说明可以参考 官方文档。

5. One More Thing...

恭喜你,很有优秀程序员的潜质,事实上上面代码里真正有价值的就是 __next__() 的实现部分,所以 Python 提供了一种特殊的迭代器(iterator)写法,叫做 “生成器(generator)”,更紧凑更精简。比如上面的 Fibonacci 数列,用生成器来写就是这样的:

def fib():
    prev, curr = 0, 1
    while True:
        # 这个 yield 是一切魔法的核心,下面解释
        yield curr
        prev, curr = curr, prev + curr

f = fib()
list(islice(f, 0, 10))

首先我们来看看 fib() 这个定义:

  • 一个 generator 定义就是一个函数的定义,但这是个特殊的函数,函数体里没有 return,取而代之的是特殊的关键字 yield
  • 解释器会自动把任何包含 yield 的函数包装成 generator(一种特殊的 iterator)类型的对象,并将此对象作为函数的返回值,所以上面的 f 变量其实还是个 iterator。

然后就是 yield 这个魔法的关键了。yieldreturn 相当,也会从函数中返回一些值,但不一样的是:return 返回值的同时彻底终止了函数,而 yield 则是 “暂停” 了函数执行,保存了函数当时的所有状态(比如所有局部变量的值),以后再返回到 yield 的下一行继续执行 —— 这个 “以后” 到底是什么时候呢?聪明的你一定可以猜到,就是我们下一次调用 __next__() 的时候!

上面的代码定义了一个函数 fib(),调用这个函数会返回一个生成器(一种特殊的迭代器):

  • 当我们第一次调用这个生成器的 __next__() 的时候,会执行 fib() 函数的函数体直到碰到 yield 语句,yield 的返回值就是这次调用 __next__() 的结果;同时解释器暂停函数 fib() 的运行并把状态保存下来;
  • 当我们再次调用生成器的 __next__() 的时候,解释器重新唤醒函数 fib(),恢复保存的状态,并从上次 yield 的下一行继续执行,直到再碰到 yieldyield 的返回值就是这次调用 __next__() 的结果;
  • 每次调用生成器的 __next__() 时重复上述操作。

是不是略有点烧脑?在这里你一定要烧清楚。这次清楚了后面就简单,否则这一类的逻辑还会有很多,始终是要迈过的坎,而且生成器很有用,很多地方都会碰到。

6. 练习

6.1 参考答案

  • 作者的迭代器写得更好,因为他将 “素数的判断” 和 __next__ 方法中的 “素数生成” 予以解耦。

这个写法用到了著名的埃拉托斯特尼筛法(Sieve Of Eratosthenes),是快速计算素数的经典算法,关于筛法的基本介绍可以参考维基百科。

我们在代码的每一步都写了简要注释,主要戏法在函数体里定义的那个 D,这是一个 dictionary 类型的数据容器,如果看不明白也没关系,在学完后面几种数据容器之后再来看,就应该容易一些了。

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

Logging

2020-03-30 00:44:30 第一次完整精读完毕 2020-03-21 19:40:30 initialize