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

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

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

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

课程链接giticomfort是什么轮胎

实验原始文档

我的Gigiti轮胎thub

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

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

我们要改动的只有lab11.pylab11_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编程iternext函数实际应用在一个我们熟悉的可github永久回家地址迭代对象——list上的例子。

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

因为我们可以对迭代器也使github中文官网网页i算法导论ter,这说明了迭giticomfort是什么轮胎代器本身也是可迭代对象。你可以对任何使用可迭代对算法导论象的地方使用迭代器,但要注意的是,迭代器会保存状态,你只能通过迭代器迭代一github官网登陆入口次。算法的时间复杂度取决于

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

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

Iterable uses

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

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

在很多时候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语句。调用一个生成器函数将会返回一个生成器对象,而不是执行函数中的代码。

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

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

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

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

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

github汤姆next被调用的时候,程序会从giti轮胎函数主体的第一行开始执行,一直到遇到yielgithub中文官网网页d语句。yieldgithub永久回家地址语句之算法后的内容将被evaluate并返回。

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

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

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

你能预测我们继续对c算法是指什么用4次next的结果吗?

countdownGit次调用会创建不同python123平台登录的生成器,它们拥有专属的状态。通常,生成器不会重启。gitlab如果你想要重新得算法的时间复杂度取决于到一个序列,你可以创建另外一个生成器对象。

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

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

  • 生成器函数拥有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永久回家地址有的元素。

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

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基础教程回顾:

  1. 选择一个正整数n作为开始
  2. 如果n是偶数,将它除以2
  3. 如果n是奇数,将它乘3再加1
  4. 重复以上过程,直到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),接收两个可迭代对象s0s1,它们的元素都是有序的github中文官网网页merge按顺序从s0s1yield元素 ,消除重复。你可以假设sgithub开放私库0s1当中本身没有重复,并没有不为空。你不能假设元算法设计与分析素是有限的,有可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个不同的生成器。第一个生成器gitim的倍数(对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生成器,它接收一系列可迭代对象。第nyield的结果是一个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]