大家好,日拱一卒,我是梁唐。
我们继续伯克利CS61A公开课之旅,这一次我们讨论的是lab11,也就是第11次实验课。
这节课讲的内容是Python当中很算法是指什么重要的两个概念迭代器和生成器。这两个是Python当中非常重要的概念,在机器学习、深度学习的代码算法分析的目的是当中也经常使用,算是算法工程师必学必了解的基础技能之一。因此它有多重要,不用我多说相信大家也能感受到。
这门课每次实验的github开放私库题目之前,都有大量的相关技术的说明。将学习和练习非常好得结合在了一起,技术说github是什么明和教程的部分质量也很高,虽然篇幅不算很长,但很能囊括GitHub重点。也因此,我每次写文都会将这部分翻译过来。如果觉得文档中不够清楚,或者是理解起来giticomfort是什么轮胎有些困难,那么可以考虑去B站看一下教学视频,会清晰很多。
课程链接giticomfort是什么轮胎
实验原始文档
我的Gigiti轮胎thub
首先,我们还python怎么读是先去官方文档当中下载本次实验用到的文件。
我们要改动的只有lab11.py
和lab11_extragit命令.py
,剩余的文件都是测试用途,保持原样即可。
下载完成之后, 让我们进入正题。
Topics
Iterables and Iterators
迭代器(iterator)是可以被迭代访问的对象。一种迭代迭代器当Git中所算法设计与分析有元素的Git方式是for循环:
for item in iteralbe:
# do something
for循环可以使用在任何可迭代对象(github永久回家地址iterable)中。我们之前描述for循环的时候,github中文社区说的是它可以用python安装教程在任何序列上——所有的序gitee列都是可迭代的。但除了序列之外也有其他对象也是可迭代的。实际上,for循环会被解释器转录成类似下面这样的代码:
iterator = iter(iterable)
try:
while True:
elem = next(iterator)
# do something
except StopIteration:
pass
我们简单看一下代码的细节:
- 首先,
iter
是一个内置函数,它应用在可迭代对象上,生成一个对应的迭代器。迭代器是一个可以在可github是什么迭代对象上迭代的对象,它会一直记录下一个被迭代的元素 -
next
函数应用在迭代器上,用来获取序列中的下python保留字一个元素 - 当序列中没有下一个元素时,会抛出
StopIteration
异常。在for循环当中,这个异常会被捕获,程序可以继续执行
这段描述看起来有一点python怎么读点乱,主要问题在于可迭代对象和迭代器是两个概念。比如一个a = [1, 2, 3]
,这里的a是一个可迭代对象,但不是迭代器。我们可以使用iter(a)
生成一个能够迭代agiticomfort是什么轮胎数组的迭代github中文官网网页器。然后用这python123平台登录个迭代器去访问a数组。
对同一个可迭代对Python象调用若干次iter
会得到多个迭代器,它们之间不会共算法工程师享状态(否则我们只能迭代一个可迭代对象一次)。你也可以对一个迭代器调用iter
,这会返回相同的迭代器,而不会发生任何变化。注意,你GitHub不能对一个可迭代对象使用next
让我们来看python编程看iter
和next
函数实际应用在一个我们熟悉的可github永久回家地址迭代对象——list上的例子。
因为我们可以对迭代器也使github中文官网网页用i算法导论ter
,这说明了迭giticomfort是什么轮胎代器本身也是可迭代对象。你可以对任何使用可迭代对算法导论象的地方使用迭代器,但要注意的是,迭代器会保存状态,你只能通过迭代器迭代一github官网登陆入口次。算法的时间复杂度取决于
推论:一个可迭代算法的五个特性对象就像是github下载一本书(可以在纸张之间翻动浏览)而迭代器就像是书签(保存位置,可以快速找到下一页)。对一本书调用iter
会得到一个书签,书签之间彼此互不影响。对书签本身调用iter
返回它自身,不会对书签停留的位置做任何改变。对书签调用next
将它移动到下一页,但不会改变书中的内容。python保留字对一本书GitHub调用next
没有意义,也不符合语法
Iterable uses
我们知道list是一个内置的iterable类型。你也应该用过range(start,git命令 end)Python
函数,它会根据start和end创建一个可迭代的升序整数序列GitHub。
在很多时候range非常有用,python怎么读包括重复执行若干次某个特定的操作,也可以很方便地得到一个下标序列。
除此之外,还有git教程很多其他内置的函数,接收一个iterable对象,返回一个有用的结果:
- map(f, iterable) – 创建一个迭代器,对iterable中的x,得到
f(x)
- filter(f, iterable) – 创建一个迭代器,对iterable中的x,得到所有
f(x) == True
的x - zip(iter1, iter2) – 对
iter1
中的github中文官网网页所有x和iter2
中的所有y,创建一个迭代器,得到所有的(x, y)
的pair - reversed(iterable) – 创建一个迭代器可以反向遍历
iterable
- list(iterable) – 创建一个list,得到
iterable
中的所有元素 - tuple(i算法设计与分析terable) – 创建一个tuple,包含
iterable
中的所有元素 - sorted(iterable) – 创建一个排好序的list,包含
iterable
中的所有元素
Generatpython语言ors
生成器
一个生成器函数返回一个特殊的迭代器类型,叫做生成器。生成器函数使算法的空间复杂度是指用yield
语句代替了returngithub
语句。调用一个生成器函数将会返回一个生成器对象,而不是执行函数中的代码。
比如,让我们看一下下面这个生成器的代码:
调用countdown
将会返回一个生成器对象,这个对象能够从n
数到0。因为生成器都是迭代器,所以我们可以对结果调用iter
,这会得到一个同样的对象。注意,函数的主体并没有执行,屏幕上什么也没有输出算法导论,也没有数字被返回。
那么,我们如何运行程序呢?因为生成器也是一种迭代器,所以我们可以对它们调用next
方法!
当github汤姆next
被调用的时候,程序会从giti轮胎函数主体的第一行开始执行,一直到遇到yielgithub中文官网网页d
语句。yieldgithub永久回家地址
语句之算法后的内容将被evaluate并返回。
和我们之前介绍的函数不同,生成器会记住状态。当我们执行多次next
的时候,生成器每次会从上一次的yield
语句继续执行。和第一次调用next
一样,程序会一直执行直到遇到下一个yield
语句。
你能预测我们继续对c
调算法是指什么用4次next
的结果吗?
对countdown
多Git次调用会创建不同python123平台登录的生成器,它们拥有专属的状态。通常,生成器不会重启。gitlab如果你想要重新得算法的时间复杂度取决于到一个序列,你可以创建另外一个生成器对象。
接下来是上面内容的一些总结:
-
生成器函数拥有
yield
语句,并且会返回一个生成器对象github下载 -
对生成器对象调用
iter
会得到一个同样的对象gitee,并且不会修改生成器的状态 -
生算法分析的目的是成器的函数主体不会被执行,直到调用
next
函数。对一个生成器对象调用next
函数,会运行并且返回序列中的下一个算法的时间复杂度取决于元素。如果序列已经giti结束了,抛出StopIteration
异常 -
生成器会记住下一次执行
next
时的状态。-
第一次调用
next
时:python是什么意思- 进入函数,运行程序知道遇到
yield
- 返回
yield
语句中的值,记住yield
语句的位置
- 进入函数,运行程序知道遇到
-
持续调用
next
时:- 从上一次
yield
语句的下一行开始执行github开放私库,遇见yield
停止 - 返回
yiepython怎么读ld
语句中的值,记住当前算法的时间复杂度取决于运行的位置
- 从上一次
-
另外一个很有用的工具是yield from
(Python 3.3及以后版python123本)。yield from
将会从另外一个迭代器或者是可迭代对象当中迭代所github永久回家地址有的元素。
Required Questions
WWPD
Q1github汤姆: WWPD: Iterators
阅读Pytgithub中文官网网页hon代码填写Python代码的输出。
使用ok命令python3 ok -q iterators -u
进行测试,如果你觉得会报错,输入Error
。如果会遇到StopIteration
异常,输入StopIteration
。如果得到一个迭代器,输入Iterator
>>> 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: Genepython123平台登录rators
阅读Python代码填写输出结果
使用ok命令进行测试:python3 ok -q generators -u
如果程序报错输入Error
,如果返回的是函数,输入Function
,如果是生成器,输入Generator
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())
______
关于生成器的基础问题,几乎没有难度。
Copython123ding Practice
Q3: Scale
实现生成器函数scale(s, kpython怎么读)
,它从给定的可迭代对象s
中yield元素,再乘上k
。作为特别挑战,试着使用ygithubield from
实现函数!
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
即可。
def scale(s, k):
for i in s:
yield i * k
如果要使用yield from
语句来完成,需要得到一个新的迭代对象,这个迭代对象里的结果是s
中的结果再乘上k
。那么我们有没有办法可以得到这个迭代对象呢?github
当然是有的,就是使用map
函数:
def scale(s, k):
yield from map(lambda x: x * k, s)
Q4: Trap
实现一个生成器函数,可以yield
可迭代对象s
中前k
个元素。当s
中没有元素时抛出ValueError
异常。你可以python基础教程假设s
至少有k
个元素。
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
答案
我们Git先对s
生成一个迭代器,然后使用循环yield``k
次,最后抛出异常即可。
def trap(s, k):
it = iter(s)
for _ in range(k):
yield next(it)
raise ValueError("no more values")
Optional Questions
选做题,这部分在lagithub官网登陆入口b11_extra.py
中
Q5: Hailstone
实现一个生成器,使得能够返回作业1中的hailstone序列。
下面是关于hgithub开放私库ailstone序列的一个快速python基础教程回顾:
- 选择一个正整数
n
作为开始 - 如果
n
是偶数,将它除以2 - 如果
n
是奇数,将它乘3再加1 - 重复以上过程,直到
n
等于1
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
答案
生成器的简单应用,照着题意实现即可。
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
次的元素。
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,为了严谨起见,所以我们先创建迭代器,取python基础教程出t
中的第一个元素作为la算法导论st
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
,它们的元素都是有序的github中文官网网页。merge
按顺序从s0
和s1
中yield
元素 ,消除重复。你可以假设sgithub开放私库0
和s1
当中本身没有重复,并没有不为空。你不能假设元算法设计与分析素是有限的,有可Git能其中一个是一个无穷的数据流。
你github官网可能会用到next(s, v)
和ngithubext
元素差不多,唯一不同的是当s
没有元素的时候,不会抛出异常,而是会返回v
。
查看doctest获得更多信息
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来进行测试:ppython安装教程ython3 ok -q merge
答案
本来想用递归来搞定,但是存在一个问题,就是已经next
取出来的元素没办法再放回去,递归求解会导致遗漏部分GitHub元素,所以只能使用迭代的方法。
最Git外层的循环条件时当两个元素不同时为None
时算法的五个特性执行,然后我们依次判断两个元素是否有空,以及元素之间大小关系即可。
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 Ge算法的空间复杂度是指nerator
就像函数一样,生成器也可以是高阶的。对于python语言这个问题,我们需要实现一个remainders_generator
函数,它从一系列生成器对象当中获取元素。
remapython语言inders_generator
读入一个整数m
,y算法设计与分析ield m
个不同的生成器。第一个生成器giti是m
的倍数(对m取模余数为0),第二个生成器是对mpython语言
取模余数为1的生成器,以此类推。
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))
4
8
1
5
9
2
6
10
3
7
11
"""
"*** YOUR CODE HERE ***"
注意,如果你实现正确的话,每一个通过remainder_generator
得到的生成github永久回家地址器都是无限的。你可以一直调用next
而不会得git命令到StopIteration
异常。
提示:考虑定义一个innder生成器函数,它应该读入什么参数?你在哪里调用它呢?
使用ok命令来进行测试:python3 ok -q remaigithub官网nders_generator
答案
我们在一个生成器内部实现一个生成器,然后在外部调用内部的生成器,返回生成器对象。
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_g机器学习enerator
生成器,它接收一系列可迭代对象。第n
次yield
的结果是一个list,是传入数据中下标n
的集github永久回家地址合。当最短的可迭代对象元素为空时停止
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
答案
传入的参python怎么读数是可迭代对象,而不是迭代器github下载,所以我们要先创建它们的迭代器。
之后我们使用while
无限循环,每次yield
所有迭代器执行next
之后的结果。当有迭代器没有元素时next
会抛出异常giticomfort是什么轮胎,由于我们没有捕python保留字获异常,giti这个异常会继续往上抛出,实现停止的效果。
def zip_generator(*iterables):
itors = [iter(it) for it in iterables]
while True:
yield [next(it) for it in itors]