Python中神奇的迭代器和生成器

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

要解决这个问题，常规算法是贪心算法。我们维护两个指针指向两个字符串的开头，然后对第二个字符串一路扫过去，如果某个字符和第一个指针指的一样，那么就把第一个指针前进一步。第一个指针移出第一个序列最后一个元素的时候，返回 True，否则返回 False。

不过，这个算法正常写的话，写下来怎么也得八行左右：

def is_subsequence(s: str, t: str) -> bool:    n, m = len(s), len(t)    i = j = 0    while i < n and j < m:        if s[i] == t[j]:            i += 1        j += 1    return i == nprint(is_subsequence("ace", "abcde"))print(is_subsequence("aec", "abcde"))

但如果我们使用迭代器和生成器，代码量将大幅度减少：

def is_subsequence(s: str, t: str) -> bool:    t = iter(t)    return all(i in t for i in s) print(is_subsequence("ace", "abcde"))print(is_subsequence("aec", "abcde"))

而且运行结果正确与上面一样，都是：

TrueFalse

但如果你对python的生成器运行机制不太了解，一定会看的一脸懵逼。

不过不用担心，我今天分享的主题便是python的迭代器和生成器剖析。

本文目录

 

• 迭代器和可迭代对象

• 列表生成式与列表生成器

• 函数生成器(generator)

• 迭代器和生成器的关系

• 利用生成器判断子序列详解

• 总结

 

迭代器和可迭代对象

在 Python 中一切皆对象，对象的抽象就是类，而对象的集合就是容器。

列表（list: [0, 1, 2]），元组（tuple: (0, 1, 2)），字典（dict: {0:0, 1:1, 2:2}），集合（set: set([0, 1, 2])）都是容器。对于容器，可以认为是多个元素在一起的单元；而不同容器的区别，正是在于内部数据结构的实现方法。

所有的容器都是可迭代对象（iterable）：

from collections.abc import Iterableparams = [    1234,    "1234",    [1, 2, 3, 4],    set([1, 2, 3, 4]),    {1: 1, 2: 2, 3: 3, 4: 4},    (1, 2, 3, 4)]for param in params:    print(f"{param}是否为可迭代对象? ", isinstance(param, Iterable))

运行结果：

1234是否为可迭代对象?  False1234是否为可迭代对象?  True[1, 2, 3, 4]是否为可迭代对象?  True{1, 2, 3, 4}是否为可迭代对象?  True{1: 1, 2: 2, 3: 3, 4: 4}是否为可迭代对象?  True(1, 2, 3, 4)是否为可迭代对象?  True

可以看到所有的集合容器都是可迭代对象（iterable），字符串也是可迭代对象，唯有单个数字不是可迭代对象。

而可迭代对象，可以通过 iter() 函数返回一个迭代器，当然迭代器本身也属于可迭代对象：

from collections.abc import Iterable, Iteratorparams = [    "1234",    [1, 2, 3, 4],    set([1, 2, 3, 4]),    {1: 1, 2: 2, 3: 3, 4: 4},    (1, 2, 3, 4)]for param in params:    param = iter(param)    print("----------")    print(f"{param}是否为可迭代对象? ", isinstance(param, Iterable))    print(f"{param}是否为迭代器对象? ", isinstance(param, Iterator))

运行结果：

这意味着迭代器本身也可以获取它自己的迭代器，例如：

for i in iter(l):    print(i, end=",")print()for i in iter(iter(l)):    print(i, end=",")

运行结果：

1,2,3,4,1,2,3,4,

迭代器（iterator）提供了一个 __next__的方法。调用这个方法后，你要么得到这个容器的下一个对象，要么得到一个 StopIteration 的错误：

l = [1, 2, 3, 4]l = iter(l)while True:    print(l.__next__())

结果：

1234---------------------------------------------------------------------------StopIteration                             Traceback (most recent call last)<ipython-input-16-e106f3a7bd73> in <module>()      2 l = iter(l)      3 while True:----> 4     print(l.__next__())StopIteration: 

当然上面的l.__next__()应该改写成next(l)，next()方法的本质就是调用目标对象的__next__()方法。

实际上for循环：

l = [1, 2, 3, 4]for i in l:    print(i)

的本质等价于：

l = [1, 2, 3, 4]l_iter = iter(l)while True:    try:        i = next(l_iter)    except StopIteration:        break    print(i)

for in 语句将这个过程隐式化了。

 

列表生成式与列表生成器

列表生成式即List Comprehensions，是Python内置的非常简单却强大的可以用来创建list的生成式。

print([x * x for x in range(1, 11)])print([x * x for x in range(1, 11) if x % 2 == 0])##还可以使用两层循环，可以生成全排列：print([m + n for m in "ABC" for n in "XYZ"])print([str(x)+str(y) for x in range(1,6) for y in range(11,16)])##for循环其实可以同时使用两个甚至多个变量，比如dict的items()可以同时迭代key和value：d = {"x": "A", "y": "B", "z": "C" }print([k + "=" + v for k, v in d.items()])

结果：

[1, 4, 9, 16, 25, 36, 49, 64, 81, 100][4, 16, 36, 64, 100]["AX", "AY", "AZ", "BX", "BY", "BZ", "CX", "CY", "CZ"]["111", "112", "113", "114", "115", "211", "212", "213", "214", "215", "311", "312", "313", "314", "315", "411", "412", "413", "414", "415", "511", "512", "513", "514", "515"]["x=A", "y=B", "z=C"]

通过列表生成式，我们可以直接创建一个列表。但是，受到内存限制，列表容量肯定是有限的。而且，创建一个包含100万个元素的列表，不仅占用很大的存储空间，如果我们仅仅需要访问前面几个元素，那后面绝大多数元素占用的空间都白白浪费了。

所以，如果列表元素可以按照某种算法推算出来，那我们是否可以在循环的过程中不断推算出后续的元素呢？这样就不必创建完整的list，从而节省大量的空间。在Python中，这种一边循环一边计算的机制，称为生成器：generator。

只要把一个列表生成式的[]改成()，就创建了一个generator：

g = (x * x for x in range(10))

generator保存的是算法，每次调用next(g)，就计算出g的下一个元素的值，直到计算到最后一个元素，没有更多的元素时，抛出StopIteration的错误。

用一个示例，感受一下生成器相对生成式的优势，首先创建一个查看当前内存情况的方法：

import osimport psutil## 显示当前 python 程序占用的内存大小def show_memory_info(hint):    pid = os.getpid()    p = psutil.Process(pid)    info = p.memory_full_info()    memory = info.uss / 1024. / 1024    print(f"{hint}内存使用: {memory} MB")

测试一下列表生成式：

def test_iterator():    show_memory_info("initing iterator")    list_1 = [i for i in range(100000000)]    show_memory_info("after iterator initiated")    print(sum(list_1))    show_memory_info("after sum called")%time test_iterator()

结果：

initing iterator内存使用: 48.69140625 MBafter iterator initiated内存使用: 3936.2890625 MB4999999950000000after sum called内存使用: 3936.29296875 MBWall time: 9.39 s

测试一下列表生成器：

def test_generator():    show_memory_info("initing generator")    list_2 = (i for i in range(100000000))    show_memory_info("after generator initiated")    print(sum(list_2))    show_memory_info("after sum called")%time test_generator()

结果：

initing generator内存使用: 48.8515625 MBafter generator initiated内存使用: 48.85546875 MB4999999950000000after sum called内存使用: 49.11328125 MBWall time: 7.95 s

声明一个迭代器很简单，[i for i in range(100000000)]就可以生成一个包含一亿元素的列表。每个元素在生成后都会保存到内存中，你通过上面的代码可以看到，它们占用了巨量的内存，内存不够的话就会出现 OOM 错误。

不过，我们并不需要在内存中同时保存这么多东西，比如对元素求和，我们只需要知道每个元素在相加的那一刻是多少就行了，用完就可以扔掉了。

函数生成器(generator)

如果推算的算法比较复杂，用类似列表生成式的for循环无法实现的时候，还可以用函数来实现。

比如，著名的斐波拉契数列（Fibonacci），除第一个和第二个数外，任意一个数都可由前两个数相加得到：

1, 1, 2, 3, 5, 8, 13, 21, 34, ...

斐波拉契数列用列表生成式写不出来，但是用函数把它打印出来却很容易：

def fib(max):    n, a, b = 0, 0, 1    while n < max:        print(b)        a, b = b, a + b        n = n + 1fib(6)

打印结果：

112358

上面的函数和生成器(generator)仅一步之遥，只要把print(b)改为yield b，fib函数就会变成生成器(generator)：

def fib(max):    n, a, b = 0, 0, 1    while n < max:        yield b        a, b = b, a + b        n = n + 1

这就是除了列表生成器以外定义generator的另一种方法。

如果一个函数定义中包含yield关键字，那么这个函数就不再是一个普通函数，而是一个generator：

fib(6)

结果：

<generator object fib at 0x0000000005F04A98>

在前面的列表生成器中我已经讲过，对于生成器可以使用for循环进行遍历：

for i in fib(6):    print(i)

打印结果：

112358

这里，最难理解的就是generator和函数的执行流程不一样。函数是顺序执行，遇到return语句或者最后一行函数语句就返回。而变成generator的函数，在每次调用next()的时候执行，遇到yield语句返回，再次执行时从上次返回的yield语句处继续执行。

举个简单的例子，定义一个generator，依次返回数字1，3，5：

def odd():    print("step 1")    yield 1    print("step 2")    yield(3)    print("step 3")    yield(5)

调用该generator时，首先要生成一个generator对象，然后用next()函数不断获得下一个返回值：

o = odd()while True:    print(next(o))

结果：

step 11step 23step 35---------------------------------------------------------------------------StopIteration                             Traceback (most recent call last)<ipython-input-7-554c5fb505f8> in <module>()      1 o = odd()      2 while True:----> 3     print(next(o))StopIteration: 

可以看到，odd不是普通函数，而是generator，在执行过程中，遇到yield就中断，下次又继续执行。执行3次yield后，已经没有yield可以执行了，所以，第4次调用next()就抛出StopIteration异常。

对于函数生成器(generator)来说，遇到return语句就是结束generator的指令（函数体最后一行语句其实隐式执行了return None），for循环随之结束。

迭代器和生成器的关系

其实生成器就是一种特殊的迭代器，而迭代器包括了生成器并不等价于生成器，它们都可以通过next()方法不断的获取下一个对象，都具备记忆已经读取的位置的特点。

例如：

l = [1, 2, 3, 4]l_iter = iter(l)

完成可以理解为产生了一个列表生成器：

l = [1, 2, 3, 4]l_iter = (i for i in l)

也可以理解成产生了一个函数生成器：

l = [1, 2, 3, 4]def func_generator(l):    for i in l:        yield il_iter = func_generator(l)

利用生成器判断子序列详解

有了前面的基础知识，相信文章开头的代码还稍微有点眉目了。现在我们再回到文章开头的代码，详细分析一下：

def is_subsequence(s: str, t: str) -> bool:    t = iter(t)    return all(i in t for i in s) print(is_subsequence("ace", "abcde"))print(is_subsequence("aec", "abcde"))

首先t = iter(t)我们可以理解为产生了一个生成器：

t = (i for i in t)

而i in t基本上等价于：

while True:    val = next(t)    if val == i:        yield True

测试一下：

t = "abcde"t = (i for i in t)print("a" in t)print("c" in t)print(next(t))

结果：

TrueTrued

可以看到最后一行直接返回了匹配到c的下一个值"d"。

这样我们再测试：

t = "abcde"t = (i for i in t)print("a" in t)print("c" in t)print("b" in t)

结果：

TrueTrueFalse

于是就可以顺利的使用生成器计算子序列的每个元素是否满足条件：

t = iter("abcde")[i in t for i in "aec"]

结果：

[True, True, False]

而all()函数即可判断是否全部都满足条件：

print(all([True, True, False]), all([True, True, True]))

结果：

False True

而上述代码all(i in t for i in s)没有申明all([i in t for i in s])列表生成式形式则代表是对一个列表生成器进行all运算。

 

End.

作者：小小明

本文为转载分享，如果涉及作品、版权和其他问题，请联系我们第一时间删除（微信号：lovedata0520）

更多文章前往首页浏览http://www.itongji.cn/