日拱一卒,伯克利教你Python核心技术,迭代器和生成器

语言: CN / TW / HK

大家好,日拱一卒,我是梁唐。

我们继续伯克利CS61A公开课之旅,这一次我们讨论的是lab11,也就是第11次实验课。

这节课讲的内容是Python当中很重要的两个概念迭代器和生成器。这两个是Python当中非常重要的概念,在机器学习、深度学习的代码当中也经常使用,算是算法工程师必学必了解的基础技能之一。因此它有多重要,不用我多说相信大家也能感受到。

这门课每次实验的题目之前,都有大量的相关技术的说明。将学习和练习非常好得结合在了一起,技术说明和教程的部分质量也很高,虽然篇幅不算很长,但很能囊括重点。也因此,我每次写文都会将这部分翻译过来。如果觉得文档中不够清楚,或者是理解起来有些困难,那么可以考虑去B站看一下教学视频,会清晰很多。

课程链接

实验原始文档

我的Github

首先,我们还是先去官方文档当中下载本次实验用到的文件。

我们要改动的只有lab11.pylab11_extra.py,剩余的文件都是测试用途,保持原样即可。

下载完成之后, 让我们进入正题。

Topics

Iterables and Iterators

迭代器(iterator)是可以被迭代访问的对象。一种迭代迭代器当中所有元素的方式是for循环:

python for item in iteralbe: # do something

for循环可以使用在任何可迭代对象(iterable)中。我们之前描述for循环的时候,说的是它可以用在任何序列上——所有的序列都是可迭代的。但除了序列之外也有其他对象也是可迭代的。实际上,for循环会被解释器转录成类似下面这样的代码:

python iterator = iter(iterable) try: while True: elem = next(iterator) # do something except StopIteration: pass

我们简单看一下代码的细节:

  • 首先,iter是一个内置函数,它应用在可迭代对象上,生成一个对应的迭代器。迭代器是一个可以在可迭代对象上迭代的对象,它会一直记录下一个被迭代的元素
  • next函数应用在迭代器上,用来获取序列中的下一个元素
  • 当序列中没有下一个元素时,会抛出StopIteration异常。在for循环当中,这个异常会被捕获,程序可以继续执行

这段描述看起来有一点点乱,主要问题在于可迭代对象和迭代器是两个概念。比如一个a = [1, 2, 3],这里的a是一个可迭代对象,但不是迭代器。我们可以使用iter(a)生成一个能够迭代a数组的迭代器。然后用这个迭代器去访问a数组。

对同一个可迭代对象调用若干次iter会得到多个迭代器,它们之间不会共享状态(否则我们只能迭代一个可迭代对象一次)。你也可以对一个迭代器调用iter,这会返回相同的迭代器,而不会发生任何变化。注意,你不能对一个可迭代对象使用next

让我们来看看iternext函数实际应用在一个我们熟悉的可迭代对象——list上的例子。

因为我们可以对迭代器也使用iter,这说明了迭代器本身也是可迭代对象。你可以对任何使用可迭代对象的地方使用迭代器,但要注意的是,迭代器会保存状态,你只能通过迭代器迭代一次。

推论:一个可迭代对象就像是一本书(可以在纸张之间翻动浏览)而迭代器就像是书签(保存位置,可以快速找到下一页)。对一本书调用iter会得到一个书签,书签之间彼此互不影响。对书签本身调用iter返回它自身,不会对书签停留的位置做任何改变。对书签调用next将它移动到下一页,但不会改变书中的内容。对一本书调用next没有意义,也不符合语法

Iterable uses

我们知道list是一个内置的iterable类型。你也应该用过range(start, end)函数,它会根据start和end创建一个可迭代的升序整数序列。

在很多时候range非常有用,包括重复执行若干次某个特定的操作,也可以很方便地得到一个下标序列。

除此之外,还有很多其他内置的函数,接收一个iterable对象,返回一个有用的结果:

  • map(f, iterable) - 创建一个迭代器,对iterable中的x,得到f(x)
  • filter(f, iterable) - 创建一个迭代器,对iterable中的x,得到所有f(x) == True的x
  • zip(iter1, iter2) - 对iter1中的所有x和iter2中的所有y,创建一个迭代器,得到所有的(x, y)的pair
  • reversed(iterable) - 创建一个迭代器可以反向遍历iterable
  • list(iterable) - 创建一个list,得到iterable中的所有元素
  • tuple(iterable) - 创建一个tuple,包含iterable中的所有元素
  • sorted(iterable) - 创建一个排好序的list,包含iterable中的所有元素

Generators

生成器

一个生成器函数返回一个特殊的迭代器类型,叫做生成器。生成器函数使用yield语句代替了return语句。调用一个生成器函数将会返回一个生成器对象,而不是执行函数中的代码。

比如,让我们看一下下面这个生成器的代码:

调用countdown将会返回一个生成器对象,这个对象能够从n数到0。因为生成器都是迭代器,所以我们可以对结果调用iter,这会得到一个同样的对象。注意,函数的主体并没有执行,屏幕上什么也没有输出,也没有数字被返回。

那么,我们如何运行程序呢?因为生成器也是一种迭代器,所以我们可以对它们调用next方法!

next被调用的时候,程序会从函数主体的第一行开始执行,一直到遇到yield语句。yield语句之后的内容将被evaluate并返回。

和我们之前介绍的函数不同,生成器会记住状态。当我们执行多次next的时候,生成器每次会从上一次的yield语句继续执行。和第一次调用next一样,程序会一直执行直到遇到下一个yield语句。

你能预测我们继续对c调用4次next的结果吗?

countdown多次调用会创建不同的生成器,它们拥有专属的状态。通常,生成器不会重启。如果你想要重新得到一个序列,你可以创建另外一个生成器对象。

接下来是上面内容的一些总结:

  • 生成器函数拥有yield语句,并且会返回一个生成器对象

  • 对生成器对象调用iter会得到一个同样的对象,并且不会修改生成器的状态

  • 生成器的函数主体不会被执行,直到调用next函数。对一个生成器对象调用next函数,会运行并且返回序列中的下一个元素。如果序列已经结束了,抛出StopIteration异常
  • 生成器会记住下一次执行next时的状态。

  • 第一次调用next时:

    • 进入函数,运行程序知道遇到yield
    • 返回yield语句中的值,记住yield语句的位置
  • 持续调用next时:

    • 从上一次yield语句的下一行开始执行,遇见yield停止
    • 返回yield语句中的值,记住当前运行的位置

另外一个很有用的工具是yield from(Python 3.3及以后版本)。yield from 将会从另外一个迭代器或者是可迭代对象当中迭代所有的元素。

Required Questions

WWPD

Q1: WWPD: Iterators

阅读Python代码填写Python代码的输出。

使用ok命令python3 ok -q iterators -u进行测试,如果你觉得会报错,输入Error。如果会遇到StopIteration异常,输入StopIteration。如果得到一个迭代器,输入Iterator

```python

s = [1, 2, 3, 4] t = iter(s) next(s)


next(t)


next(t)


iter(s)


next(iter(s))


next(iter(t))


next(iter(s))


next(iter(t))


next(t)


r = range(6) r_iter = iter(r) next(r_iter)


[x + 1 for x in r]


[x + 1 for x in r_iter]


next(r_iter)


list(range(-2, 4)) # Converts an iterable into a list


map_iter = map(lambda x : x + 10, range(5)) next(map_iter)


next(map_iter)


list(map_iter)


for e in filter(lambda x : x % 2 == 0, range(1000, 1008)): ... print(e) ...


[x + y for x, y in zip([1, 2, 3], [4, 5, 6])]


for e in zip([10, 9, 8], range(3)): ... print(tuple(map(lambda x: x + 2, e))) ...


```

题目不算难,但当中有一些题还是挺刁钻的,需要仔细想想。如果一直做不对可以放到Python解释器里执行一下。

Q2: WWPD: Generators

阅读Python代码填写输出结果

使用ok命令进行测试:python3 ok -q generators -u

如果程序报错输入Error,如果返回的是函数,输入Function,如果是生成器,输入Generator

```python def gen(): print("Starting here") i = 0 while i < 6: print("Before yield") yield i print("After yield") i += 1

next(gen)


gen


g = gen() g


g == iter(g)


next(g)


next(g)


next(g)


g2 = gen() next(g2)


iter(g2)


next(iter(g))


next(gen())


```

关于生成器的基础问题,几乎没有难度。

Coding Practice

Q3: Scale

实现生成器函数scale(s, k),它从给定的可迭代对象s中yield元素,再乘上k。作为特别挑战,试着使用yield from实现函数!

```python def scale(s, k): """Yield elements of the iterable s scaled by a number k.

>>> s = scale([1, 5, 2], 5)
>>> type(s)
<class 'generator'>
>>> list(s)
[5, 25, 10]

>>> m = scale(naturals(), 2)
>>> [next(m) for _ in range(5)]
[2, 4, 6, 8, 10]
"""
"*** YOUR CODE HERE ***"

```

使用ok进行测试:python3 ok -q scale

答案

我们可以使用for循环迭代一个可迭代对象,将拿到的结果yield即可。

python def scale(s, k): for i in s: yield i * k

如果要使用yield from语句来完成,需要得到一个新的迭代对象,这个迭代对象里的结果是s中的结果再乘上k。那么我们有没有办法可以得到这个迭代对象呢?

当然是有的,就是使用map函数:

python def scale(s, k): yield from map(lambda x: x * k, s)

Q4: Trap

实现一个生成器函数,可以yield可迭代对象s中前k个元素。当s中没有元素时抛出ValueError异常。你可以假设s至少有k个元素。

```python def trap(s, k): """Return a generator that yields the first K values in iterable S, but raises a ValueError exception if any more values are requested.

>>> t = trap([3, 2, 1], 2)
>>> next(t)
3
>>> next(t)
2
>>> next(t)
ValueError
>>> list(trap(range(5), 5))
ValueError
>>> t2 = trap(map(abs, reversed(range(-6, -4))), 2)
>>> next(t2)
5
>>> next(t2)
6
>>> next(t2)
ValueError
"""
"*** YOUR CODE HERE ***"

```

使用ok命令进行测试:python3 ok -q trap

答案

我们先对s生成一个迭代器,然后使用循环yield``k次,最后抛出异常即可。

python def trap(s, k): it = iter(s) for _ in range(k): yield next(it) raise ValueError("no more values")

Optional Questions

选做题,这部分在lab11_extra.py

Q5: Hailstone

实现一个生成器,使得能够返回作业1中的hailstone序列。

下面是关于hailstone序列的一个快速回顾:

  1. 选择一个正整数n作为开始
  2. 如果n是偶数,将它除以2
  3. 如果n是奇数,将它乘3再加1
  4. 重复以上过程,直到n等于1

python def hailstone(n): """ >>> for num in hailstone(10): ... print(num) ... 10 5 16 8 4 2 1 """ "*** YOUR CODE HERE ***"

使用ok命令进行测试:python3 ok -q hailstone

答案

生成器的简单应用,照着题意实现即可。

python def hailstone(n): while n != 1: yield n if n % 2 == 0: n //= 2 else: n = n * 3 + 1 yield n

Q6: Repeated

实现一个函数(不是生成器),返回可迭代对象t中第一个重复k次的元素。

```python def repeated(t, k): """Return the first value in iterable T that appears K times in a row.

>>> s = [3, 2, 1, 2, 1, 4, 4, 5, 5, 5]
>>> repeated(trap(s, 7), 2)
4
>>> repeated(trap(s, 10), 3)
5
>>> print(repeated([4, None, None, None], 3))
None
"""
assert k > 1
"*** YOUR CODE HERE ***"

```

使用ok命令进行测试:python3 ok -q repeated

答案

因为测试样例数组中的元素存在None,为了严谨起见,所以我们先创建迭代器,取出t中的第一个元素作为last

python def repeated(t, k): assert k > 1 "*** YOUR CODE HERE ***" it = iter(t) last, cnt = next(it), 1 for i in it: if i == last: cnt += 1 if cnt == k: return i else: last, cnt = i, 1

Q7: Merge

实现merge(s0, s1),接收两个可迭代对象s0s1,它们的元素都是有序的。merge按顺序从s0s1yield元素 ,消除重复。你可以假设s0s1当中本身没有重复,并没有不为空。你不能假设元素是有限的,有可能其中一个是一个无穷的数据流。

你可能会用到next(s, v)next元素差不多,唯一不同的是当s没有元素的时候,不会抛出异常,而是会返回v

查看doctest获得更多信息

```python def merge(s0, s1): """Yield the elements of strictly increasing iterables s0 and s1, removing repeats. Assume that s0 and s1 have no repeats. s0 or s1 may be infinite sequences.

>>> m = merge([0, 2, 4, 6, 8, 10, 12, 14], [0, 3, 6, 9, 12, 15])
>>> type(m)
<class 'generator'>
>>> list(m)
[0, 2, 3, 4, 6, 8, 9, 10, 12, 14, 15]
>>> def big(n):
...    k = 0
...    while True: yield k; k += n
>>> m = merge(big(2), big(3))
>>> [next(m) for _ in range(11)]
[0, 2, 3, 4, 6, 8, 9, 10, 12, 14, 15]
"""
i0, i1 = iter(s0), iter(s1)
e0, e1 = next(i0, None), next(i1, None)
"*** YOUR CODE HERE ***"

```

使用ok来进行测试:python3 ok -q merge

答案

本来想用递归来搞定,但是存在一个问题,就是已经next取出来的元素没办法再放回去,递归求解会导致遗漏部分元素,所以只能使用迭代的方法。

最外层的循环条件时当两个元素不同时为None时执行,然后我们依次判断两个元素是否有空,以及元素之间大小关系即可。

python def merge(s0, s1): i0, i1 = iter(s0), iter(s1) e0, e1 = next(i0, None), next(i1, None) "*** YOUR CODE HERE ***" while e0 is not None or e1 is not None: if e0 is None: yield e1 e1 = next(i1, None) elif e1 is None: yield e0 e0 = next(i0, None) else: if e0 == e1: yield e0 e0, e1 = next(i0, None), next(i1, None) elif e0 < e1: yield e0 e0 = next(i0, None) else: yield e1 e1 = next(i1, None)

Q8: Remainder Generator

就像函数一样,生成器也可以是高阶的。对于这个问题,我们需要实现一个remainders_generator函数,它从一系列生成器对象当中获取元素。

remainders_generator读入一个整数m,yield m个不同的生成器。第一个生成器是m的倍数(对m取模余数为0),第二个生成器是对m取模余数为1的生成器,以此类推。

```python def remainders_generator(m): """ Takes in an integer m, and yields m different remainder groups of m.

>>> remainders_mod_four = remainders_generator(4)
>>> for rem_group in remainders_mod_four:
...     for _ in range(3):
...         print(next(rem_group))
0
4
8
1
5
9
2
6
10
3
7
11
"""
"*** YOUR CODE HERE ***"

```

注意,如果你实现正确的话,每一个通过remainder_generator得到的生成器都是无限的。你可以一直调用next而不会得到StopIteration异常。

提示:考虑定义一个innder生成器函数,它应该读入什么参数?你在哪里调用它呢?

使用ok命令来进行测试:python3 ok -q remainders_generator

答案

我们在一个生成器内部实现一个生成器,然后在外部调用内部的生成器,返回生成器对象。

```python def remainders_generator(m): def inner(r): while True: yield r r += m

for i in range(m):
    yield inner(i)

```

Q9: Zip Generator

实现zip_generator生成器,它接收一系列可迭代对象。第nyield的结果是一个list,是传入数据中下标n的集合。当最短的可迭代对象元素为空时停止

python def zip_generator(*iterables): """ Takes in any number of iterables and zips them together. Returns a generator that outputs a series of lists, each containing the nth items of each iterable. >>> z = zip_generator([1, 2, 3], [4, 5, 6], [7, 8]) >>> for i in z: ... print(i) ... [1, 4, 7] [2, 5, 8] """ "*** YOUR CODE HERE ***"

使用ok命令进行测试:python3 ok -q zip_generator

答案

传入的参数是可迭代对象,而不是迭代器,所以我们要先创建它们的迭代器。

之后我们使用while无限循环,每次yield所有迭代器执行next之后的结果。当有迭代器没有元素时next会抛出异常,由于我们没有捕获异常,这个异常会继续往上抛出,实现停止的效果。

python def zip_generator(*iterables): itors = [iter(it) for it in iterables] while True: yield [next(it) for it in itors]