日拱一卒,伯克利教你Python核心技术,迭代器和生成器
大家好,日拱一卒,我是梁唐。
我们继续伯克利CS61A公开课之旅,这一次我们讨论的是lab11,也就是第11次实验课。
这节课讲的内容是Python当中很重要的两个概念迭代器和生成器。这两个是Python当中非常重要的概念,在机器学习、深度学习的代码当中也经常使用,算是算法工程师必学必了解的基础技能之一。因此它有多重要,不用我多说相信大家也能感受到。
这门课每次实验的题目之前,都有大量的相关技术的说明。将学习和练习非常好得结合在了一起,技术说明和教程的部分质量也很高,虽然篇幅不算很长,但很能囊括重点。也因此,我每次写文都会将这部分翻译过来。如果觉得文档中不够清楚,或者是理解起来有些困难,那么可以考虑去B站看一下教学视频,会清晰很多。
首先,我们还是先去官方文档当中下载本次实验用到的文件。
我们要改动的只有lab11.py
和lab11_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
让我们来看看iter
和next
函数实际应用在一个我们熟悉的可迭代对象——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序列的一个快速回顾:
- 选择一个正整数
n
作为开始 - 如果
n
是偶数,将它除以2 - 如果
n
是奇数,将它乘3再加1 - 重复以上过程,直到
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)
,接收两个可迭代对象s0
和s1
,它们的元素都是有序的。merge
按顺序从s0
和s1
中yield
元素 ,消除重复。你可以假设s0
和s1
当中本身没有重复,并没有不为空。你不能假设元素是有限的,有可能其中一个是一个无穷的数据流。
你可能会用到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
生成器,它接收一系列可迭代对象。第n
次yield
的结果是一个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]
- 日拱一卒,麻省理工教你信息安全和密码学
- LeetCode周赛301,离大谱,手速场掉分,质量场掉大分……
- 日拱一卒,元编程不是元宇宙,麻省理工教你makefile、依赖管理和CI
- LeetCode周赛300,差点AK,刚拿到的勋章要丢了……
- 日拱一卒,麻省理工教你性能分析,火焰图、系统调用栈,黑科技满满
- 日拱一卒,麻省理工教你Debug,从此debug不再脱发
- 日拱一卒,麻省理工教你学Git,工程师必备技能
- 日拱一卒,配置开发环境不再愁,麻省理工手把手教你
- 日拱一卒,麻省理工CS入门课,命令行这样用也太帅了
- 日拱一卒,麻省理工YYDS,一节课让我学会用vim
- 日拱一卒,麻省理工教你CS基础,那些酷炫无比的命令行工具
- LeetCode周赛297,一小时AK你也可以
- 听说你入行好几年还只会cd和ls,麻省理工开了这门课……
- 日拱一卒,伯克利CS61A完结撒花
- 日拱一卒,伯克利教你用SQL处理数据
- LeetCode周赛296,难度较低的新手练习场
- 日拱一卒,伯克利教你Python核心技术,迭代器和生成器
- 日拱一卒,伯克利CS61A,教你用Python写一个Python解释器
- 日拱一卒,伯克利教你lisp,神一样的编程语言
- LeetCode周赛295,赛后看了大佬的代码,受益匪浅