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

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

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

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

课程链接

实验原始文档

我的Github

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

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

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

Topics

Iterables and Iterators

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

for item in iteralbe:
    # do something

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

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

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

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实现函数！

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。那么我们有没有办法可以得到这个迭代对象呢？

当然是有的，就是使用map函数：

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

Q4: Trap

实现一个生成器函数，可以yield可迭代对象s中前k个元素。当s中没有元素时抛出ValueError异常。你可以假设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

答案

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

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

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，为了严谨起见，所以我们先创建迭代器，取出t中的第一个元素作为last

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获得更多信息

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时执行，然后我们依次判断两个元素是否有空，以及元素之间大小关系即可。

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的生成器，以此类推。

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

答案

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

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的集合。当最短的可迭代对象元素为空时停止

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会抛出异常，由于我们没有捕获异常，这个异常会继续往上抛出，实现停止的效果。

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