19-深入理解迭代器和生成器
你好,我是悦创。
在第一次接触 Python 的时候,你可能写过类似 for i in [2, 3, 5, 7, 11, 13]: print(i)
这样的语句。for in
语句理解起来很直观形象,比起 C++ 和 java 早期的 for (int i = 0; i < n; i ++) printf("%d\n", a[i])
这样的语句,不知道简洁清晰到哪里去了。
但是,你想过 Python 在处理 for in
语句的时候,具体发生了什么吗?什么样的对象可以被 for in
来枚举呢?
这一节课,我们深入到 Python 的容器类型实现底层去走走,了解一种叫做迭代器和生成器的东西。
你肯定用过的容器、可迭代对象和迭代器
容器这个概念非常好理解。我们说过,在 Python 中一切皆对象,对象的抽象就是类,而对象的集合就是容器。
列表(list: [0, 1, 2]
),元组(tuple: (0, 1, 2)
),字典(dict: {0:0, 1:1, 2:2}
),集合(set: set([0, 1, 2])
)都是容器。
对于容器,你可以很直观地想象成多个元素在一起的单元;而不同容器的区别,正是在于内部数据结构的实现方法。
然后,你就可以针对不同场景,选择不同时间和空间复杂度的容器。
所有的容器都是可迭代的(iterable)。这里的迭代,和枚举不完全一样。迭代可以想象成是你去买苹果,卖家并不告诉你他有多少库存。这样,每次你都需要告诉卖家,你要一个苹果,然后卖家采取行为:要么给你拿一个苹果;要么告诉你,苹果已经卖完了。你并不需要知道,卖家在仓库是怎么摆放苹果的。
严谨地说,迭代器(iterator)提供了一个 next 的方法。调用这个方法后,你要么得到这个容器的下一个对象,要么得到一个 StopIteration 的错误(苹果卖完了)。你不需要像列表一样指定元素的索引,因为字典和集合这样的容器并没有索引一说。比如,字典采用哈希表实现,那么你就只需要知道,next 函数可以不重复不遗漏地一个一个拿到所有元素即可。
而可迭代对象,通过 iter()
函数返回一个迭代器,再通过 next()
函数就可以实现遍历。for in
语句将这个过程隐式化,所以,你只需要知道它大概做了什么就行了。
我们来看下面这段代码,主要向你展示怎么判断一个对象是否可迭代。当然,这还有另一种做法,是 isinstance(obj, Iterable)
。
def is_iterable(param):
try:
iter(param)
return True
except TypeError:
return False
params = [
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('{} is iterable? {}'.format(param, is_iterable(param)))
########## 输出 ##########
1234 is iterable? False
1234 is iterable? True
[1, 2, 3, 4] is iterable? True
{1, 2, 3, 4} is iterable? True
{1: 1, 2: 2, 3: 3, 4: 4} is iterable? True
(1, 2, 3, 4) is iterable? True
通过这段代码,你就可以知道,给出的类型中,除了数字 1234 之外,其它的数据类型都是可迭代的。
生成器,又是什么?
据我所知,很多人对生成器这个概念会比较陌生,因为生成器在很多常用语言中,并没有相对应的模型。
这里,你只需要记着一点:生成器是懒人版本的迭代器。
我们知道,在迭代器中,如果我们想要枚举它的元素,这些元素需要事先生成。这里,我们先来看下面这个简单的样例。
import os
import psutil # process and system utilities
# 显示当前 python 程序占用的内存大小
def show_memory_info(hint):
pid = os.getpid()
p = psutil.Process(pid)
info = p.memory_full_info()
memory = info.uss / 1024. / 1024
print('{} memory used: {} MB'.format(hint, memory))
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')
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_iterator()
%time test_generator()
########## 输出 ##########
initing iterator memory used: 48.9765625 MB
after iterator initiated memory used: 3920.30078125 MB
4999999950000000
after sum called memory used: 3920.3046875 MB
Wall time: 17 s
initing generator memory used: 50.359375 MB
after generator initiated memory used: 50.359375 MB
4999999950000000
after sum called memory used: 50.109375 MB
Wall time: 12.5 s
声明一个迭代器很简单,[i for i in range(100000000)]
就可以生成一个包含一亿元素的列表。每个元素在生成后都会保存到内存中,你通过代码可以看到,它们占用了巨量的内存,内存不够的话就会出现 OOM 错误。
不过,我们并不需要在内存中同时保存这么多东西,比如对元素求和,我们只需要知道每个元素在相加的那一刻是多少就行了,用完就可以扔掉了。
于是,生成器的概念应运而生,在你调用 next() 函数的时候,才会生成下一个变量。生成器在 Python 的写法是用小括号括起来,(i for i in range(100000000))
,即初始化了一个生成器。
这样一来,你可以清晰地看到,生成器并不会像迭代器一样占用大量内存,只有在被使用的时候才会调用。而且生成器在初始化的时候,并不需要运行一次生成操作,相比于 test_iterator()
,test_generator()
函数节省了一次生成一亿个元素的过程,因此耗时明显比迭代器短。
到这里,你可能说,生成器不过如此嘛,我有的是钱,不就是多占一些内存和计算资源嘛,我多出点钱就是了呗。
哪怕你是土豪,请坐下先喝点茶,再听我继续讲完,这次,我们来实现一个自定义的生成器。
生成器,还能玩什么花样?
数学中有一个恒等式,(1 + 2 + 3 + ... + n)^2 = 1^3 + 2^3 + 3^3 + ... + n^3
,想必你高中就应该学过它。现在,我们来验证一下这个公式的正确性。老规矩,先放代码,你先自己阅读一下,看不懂的也不要紧,接下来我再来详细讲解。
def generator(k):
i = 1
while True:
yield i ** k
i += 1
gen_1 = generator(1)
gen_3 = generator(3)
print(gen_1)
print(gen_3)
def get_sum(n):
sum_1, sum_3 = 0, 0
for i in range(n):
next_1 = next(gen_1)
next_3 = next(gen_3)
print('next_1 = {}, next_3 = {}'.format(next_1, next_3))
sum_1 += next_1
sum_3 += next_3
print(sum_1 * sum_1, sum_3)
get_sum(8)
########## 输出 ##########
<generator object generator at 0x000001E70651C4F8>
<generator object generator at 0x000001E70651C390>
next_1 = 1, next_3 = 1
next_1 = 2, next_3 = 8
next_1 = 3, next_3 = 27
next_1 = 4, next_3 = 64
next_1 = 5, next_3 = 125
next_1 = 6, next_3 = 216
next_1 = 7, next_3 = 343
next_1 = 8, next_3 = 512
1296 1296
这段代码中,你首先注意一下 generator()
这个函数,它返回了一个生成器。
接下来的 yield 是魔术的关键。对于初学者来说,你可以理解为,函数运行到这一行的时候,程序会从这里暂停,然后跳出,不过跳到哪里呢?答案是 next()
函数。那么 i ** k
是干什么的呢?它其实成了 next()
函数的返回值。
这样,每次 next(gen)
函数被调用的时候,暂停的程序就又复活了,从 yield 这里向下继续执行;同时注意,局部变量 i 并没有被清除掉,而是会继续累加。我们可以看到 next_1
从 1 变到 8,next_3
从 1 变到 512。
聪明的你应该注意到了,这个生成器居然可以一直进行下去!没错,事实上,迭代器是一个有限集合,生成器则可以成为一个无限集。我只管调用 next()
,生成器根据运算会自动生成新的元素,然后返回给你,非常便捷。
到这里,土豪同志应该也坐不住了吧,那么,还能再给力一点吗?
别急,我们再来看一个问题:给定一个 list 和一个指定数字,求这个数字在 list 中的位置。
下面这段代码你应该不陌生,也就是常规做法,枚举每个元素和它的 index,判断后加入 result,最后返回。
def index_normal(L, target):
result = []
for i, num in enumerate(L):
if num == target:
result.append(i)
return result
print(index_normal([1, 6, 2, 4, 5, 2, 8, 6, 3, 2], 2))
########## 输出 ##########
[2, 5, 9]
那么使用迭代器可以怎么做呢?二话不说,先看代码。
def index_generator(L, target):
for i, num in enumerate(L):
if num == target:
yield i
print(list(index_generator([1, 6, 2, 4, 5, 2, 8, 6, 3, 2], 2)))
########## 输出 ##########
[2, 5, 9]
聪明的你应该看到了明显的区别,我就不做过多解释了。唯一需要强调的是, index_generator
会返回一个 Generator 对象,需要使用 list 转换为列表后,才能用 print 输出。
这里我再多说两句。在 Python 语言规范中,用更少、更清晰的代码实现相同功能,一直是被推崇的做法,因为这样能够很有效提高代码的可读性,减少出错概率,也方便别人快速准确理解你的意图。当然,要注意,这里“更少”的前提是清晰,而不是使用更多的魔术操作,虽说减少了代码却反而增加了阅读的难度。
回归正题。接下来我们再来看一个问题:给定两个序列,判定第一个是不是第二个的子序列。(LeetCode 链接如下:https://leetcode.com/problems/is-subsequence/ )
https://leetcode.cn/problems/is-subsequence/
先来解读一下这个问题本身。序列就是列表,子序列则指的是,一个列表的元素在第二个列表中都按顺序出现,但是并不必挨在一起。举个例子,[1, 3, 5]
是 [1, 2, 3, 4, 5]
的子序列,[1, 4, 3]
则不是。
要解决这个问题,常规算法是贪心算法。我们维护两个指针指向两个列表的最开始,然后对第二个序列一路扫过去,如果某个数字和第一个指针指的一样,那么就把第一个指针前进一步。第一个指针移出第一个序列最后一个元素的时候,返回 True,否则返回 False。
不过,这个算法正常写的话,写下来怎么也得十行左右。
那么如果我们用迭代器和生成器呢?
def is_subsequence(a, b):
b = iter(b)
return all(i in b for i in a)
print(is_subsequence([1, 3, 5], [1, 2, 3, 4, 5]))
print(is_subsequence([1, 4, 3], [1, 2, 3, 4, 5]))
########## 输出 ##########
True
False
这简短的几行代码,你是不是看得一头雾水,不知道发生了什么?
来,我们先把这段代码复杂化,然后一步步看。
def is_subsequence(a, b):
b = iter(b)
print(b)
gen = (i for i in a)
print(gen)
for i in gen:
print(i)
gen = ((i in b) for i in a)
print(gen)
for i in gen:
print(i)
return all(((i in b) for i in a))
print(is_subsequence([1, 3, 5], [1, 2, 3, 4, 5]))
print(is_subsequence([1, 4, 3], [1, 2, 3, 4, 5]))
########## 输出 ##########
<list_iterator object at 0x000001E7063D0E80>
<generator object is_subsequence.<locals>.<genexpr> at 0x000001E70651C570>
1
3
5
<generator object is_subsequence.<locals>.<genexpr> at 0x000001E70651C5E8>
True
True
True
False
<list_iterator object at 0x000001E7063D0D30>
<generator object is_subsequence.<locals>.<genexpr> at 0x000001E70651C5E8>
1
4
3
<generator object is_subsequence.<locals>.<genexpr> at 0x000001E70651C570>
True
True
False
False
首先,第二行的 b = iter(b)
,把列表 b 转化成了一个迭代器,这里我先不解释为什么要这么做。
接下来的 gen = (i for i in a)
语句很好理解,产生一个生成器,这个生成器可以遍历对象 a,因此能够输出 1, 3, 5
。而 (i in b)
需要好好揣摩,这里你是不是能联想到 for in
语句?
没错,这里的 (i in b)
,大致等价于下面这段代码:
while True:
val = next(b)
if val == i:
yield True
这里非常巧妙地利用生成器的特性,next()
函数运行的时候,保存了当前的指针。比如再看下面这个示例:
b = (i for i in range(5))
print(2 in b)
print(4 in b)
print(3 in b)
########## 输出 ##########
True
True
False
至于最后的 all()
函数,就很简单了。它用来判断一个迭代器的元素是否全部为 True,如果是则返回 True,否则就返回 False。
于是到此,我们就很优雅地解决了这道面试题。不过你一定注意,面试的时候尽量不要用这种技巧,因为你的面试官有可能并不知道生成器的用法,他们也没有看过我的专栏。不过,在这个技术知识点上,在实际工作的应用上,你已经比很多人更加熟练了。继续加油!
总结
总结一下,今天我们讲了四种不同的对象,分别是容器、可迭代对象、迭代器和生成器。
- 容器是可迭代对象,可迭代对象调用
iter()
函数,可以得到一个迭代器。迭代器可以通过next()
函数来得到下一个元素,从而支持遍历。 - 生成器是一种特殊的迭代器(注意这个逻辑关系反之不成立)。使用生成器,你可以写出来更加清晰的代码;合理使用生成器,可以降低内存占用、优化程序结构、提高程序速度。
- 生成器在 Python 2 的版本上,是协程的一种重要实现方式;而 Python 3.5 引入 async await 语法糖后,生成器实现协程的方式就已经落后了。我们会在下节课,继续深入讲解 Python 协程。
思考题
最后给你留一个思考题。对于一个有限元素的生成器,如果迭代完成后,继续调用 next()
,会发生什么呢?生成器可以遍历多次吗?
欢迎留言和我讨论,也欢迎你把这篇文章分享给你的同事、朋友,一起在交流中进步。
欢迎关注我公众号:AI悦创,有更多更好玩的等你发现!
公众号:AI悦创【二维码】
AI悦创·编程一对一
AI悦创·推出辅导班啦,包括「Python 语言辅导班、C++ 辅导班、java 辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发、Linux、Web」,全部都是一对一教学:一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。当然,还有线下线上摄影课程、Photoshop、Premiere 一对一教学、QQ、微信在线,随时响应!微信:Jiabcdefh
C++ 信息奥赛题解,长期更新!长期招收一对一中小学信息奥赛集训,莆田、厦门地区有机会线下上门,其他地区线上。微信:Jiabcdefh
方法一:QQ
方法二:微信:Jiabcdefh
- 0
- 0
- 0
- 0
- 0
- 0