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

数据分析学习社
数据分析学习社
数据分析学习社
198
文章
0
评论
2021-05-2110:11:20 评论 29 7780字
摘要

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",    [1234],    set([1234]),    {11223344},    (1234)]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",    [1234],    set([1234]),    {11223344},    (1234)]for param in params:    param = iter(param)    print("----------")    print(f"{param}是否为可迭代对象? ", isinstance(param, Iterable))    print(f"{param}是否为迭代器对象? ", isinstance(param, Iterator))

运行结果:

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

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

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 = [1234]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 = [1234]for i in l:    print(i)

的本质等价于:

l = [1234]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(111)])print([x * x for x in range(111if x % 2 == 0])##还可以使用两层循环,可以生成全排列:print([m + n for m in "ABC" for n in "XYZ"])print([str(x)+str(y) for x in range(1,6for 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 = 001    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 = 001    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 = [1234]l_iter = iter(l)

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

l = [1234]l_iter = (i for i in l)

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

l = [1234]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/

  • 我的微信公众号
  • 微信扫一扫
  • weinxin
  • 我的微信公众号
  • 微信扫一扫
  • weinxin
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: