• 进入"运维那点事"后,希望您第一件事就是阅读“关于”栏目,仔细阅读“关于Ctrl+c问题”,不希望误会!

Python生成器与迭代器

Python编程 彭东稳 7年前 (2017-08-08) 17741次浏览 已收录 0个评论

一、迭代器

在第一次接触 Python 的时候,你可能写过类似:

但是,你想过 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 语句将这个过程隐式化,所以,你只需要知道它大概做了什么就行了。 我们来看下面这段代码,主要向你展示怎么判断一个对象是否可迭代。

结果输出:

通过这段代码,你就可以知道,给出的类型中,除了数字 1234 之外,其它的数据类型都是可迭代的。

当然,这还有另一种做法,直接使用 isinstance(obj, Iterable)。

容器是可迭代对象,可迭代对象调用 iter() 函数,可以得到一个迭代器(Iterator)。迭代器可以通过 next() 函数来得到下一个元素,从而支持遍历。

可以使用 isinstance() 判断一个对象是否是迭代器(Iterator)对象:

生成器都是 Iterator 对象,但 list、dict、str 虽然是 Iterable,却不是 Iterator。

把 list、dict、str 等 Iterable(可迭代对象)变成 Iterator(迭代器)可以使用 iter() 函数:

为什么 list、dict、str 等数据类型不是 Iterator?

这是因为 Python 的 Iterator 对象表示的是一个数据流,Iterator 对象可以被 next() 函数调用并不断返回下一个数据,直到没有数据时抛出 StopIteration 错误。可以把这个数据流看做是一个有序序列,但我们却不能提前知道序列的长度,只能不断通过 next() 函数实现按需计算下一个数据,所以 Iterator 的计算是惰性的,只有在需要返回下一个数据时它才会计算。

Iterator 甚至可以表示一个无限大的数据流,例如全体自然数。而使用 list 是永远不可能存储全体自然数的。

细看迭代器,好像没有任何用处,它能完成的工作使用生成器也可以完成,其实也可以说迭代器是生成器的超集。如果学过 Python 的网络 IO 就会发现 iter 函数的优势,可以造非阻塞 IO。

二、生成器

通过列表解析,我们可以直接创建一个列表。但是,受到内存限制,列表容量肯定是有限的。而且,创建一个包含 100 万个元素的列表,不仅占用很大的存储空间,如果我们仅仅需要访问前面几个元素,那后面绝大多数元素占用的空间都白白浪费了。不过,我们并不需要在内存中同时保存这么多东西,比如对元素求和,我们只需要知道每个元素在相加的那一刻是多少就行了,用完就可以扔掉了。

如果列表元素可以按照某种算法推算出来,那我们是否可以在循环的过程中不断推算出后续的元素呢?这样就不必创建完整的list,从而节省大量的空间。于是,生成器的概念应运而生,在你调用 next() 函数的时候,才会生成下一个变量,这是一种一边循环一边计算的机制。

生成器是懒人版本的迭代器。

我们知道,在迭代器中,如果我们想要枚举它的元素,这些元素需要事先生成。这里,我们先来看下面这个简单的样例。

输出结果:

要创建一个 generator,有很多种方法。第一种方法很简单,只要把一个列表解析的 [] 改成 (),就创建了一个 generator:

创建 L 和 g 的区别仅在于最外层的 [] 和 (),L 是一个 list,而 g 是一个 generator。

我们可以直接打印出 list 的每一个元素,但我们怎么打印出 generator 的每一个元素呢?如果要一个一个打印出来,可以通过 next() 函数获得 generator 的下一个返回值:

Generator 保存的是算法,每次调用 next(g),就计算出 g 的下一个元素的值,直到计算到最后一个元素,没有更多的元素时,抛出 StopIteration 的错误。这种方式也称为延迟计算。

当然,上面这种不断调用 next(g) 实在是太变态了,正确的方法是使用 for 循环,因为 generator 也是可迭代对象:

所以,我们创建了一个 generator 后,基本上永远不会调用 next(),而是通过 for 循环来迭代它,并且不需要关心 StopIteration 的错误。

生成器不能遍历多次,重新遍历需要生成一个新的生成器。

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

生成器,还能玩什么花样?

数学中有一个恒等式,想必你高中就应该学过它。

现在,我们来验证一下这个公式的正确性。老规矩,先放代码,你先自己阅读一下,看不懂的也不要紧,接下来我再来详细讲解。

输出结果:

这段代码中,你首先注意一下 generator() 这个函数,它返回了一个生成器。 接下来的 yield 是魔术的关键。对于初学者来说,你可以理解为,函数运行到这一行的时候,程序会从这里暂停,然后跳出,不过跳到哪里呢?答案是 next() 函数。那么 i ** k 是干什么的呢?它其实成了 next() 函数的返回值。这样,每次 next(gen) 函数被调用的时候,暂停的程序就又复活了,从 yield 这里向下继续执行;同时注意,局部变量 i 并没有被清除掉,而是会继续累加。我们可以看到 next_1 从 1 变到 8,next_3 从 1 变到 512。

你应该注意到了,这个生成器居然可以一直进行下去!没错,事实上,迭代器是一个有限集合,生成器则可以成为一个无限集。我只管调用 next(),生成器根据运算会自动生成新的元素,然后返回给你,非常便捷。

我们再来看一个问题:给定一个 list 和一个指定数字,求这个数字在 list 中的位置。

下面这段代码你应该不陌生,也就是常规做法,枚举每个元素和它的 index,判断后加入 result,最后返回。

那么使用迭代器可以怎么做呢?看代码。

通过对比可以看到了明显的区别,我就不做过多解释了。唯一需要强调的是, index_generator 会返回一个 Generator 对象,需要使用 list 转换为列表后,才能用 print 输出。

在 Python 语言规范中,用更少、更清晰的代码实现相同功能,一直是被推崇的做法,因为这样能够很有效提高代码的可读性,减少出错概率,也方便别人快速准确理解你的意图。当然,要注意,这里“更少”的前提是清晰,而不是使用更多的魔术操作,虽说减少了代码却反而增加了阅读的难度。

回归正题。接下来我们再来看一个问题:给定两个序列,判定第一个是不是第二个的子序列。(LeetCode 链接如下: leetcode.com/problems/i )

先来解读一下这个问题本身。序列就是列表,子序列则指的是,一个列表的元素在第二个列表中都按顺序出现,但是并不必挨在一起。举个例子,[1, 3, 5] 是 [1, 2, 3, 4, 5] 的子序列,[1, 4, 3] 则不是。

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

不过,这个算法正常写的话,写下来怎么也得十行左右。

那么如果我们用迭代器和生成器呢?

这简短的几行代码,你是不是看得一头雾水,不知道发生了什么?

来,我们先把这段代码复杂化,然后一步步看。

首先,第二行的 b1 = iter(b),把列表 b 转化成了一个迭代器,这里我先不解释为什么要这么做。接下来的 gen = (i for i in a) 语句很好理解,产生一个生成器,这个生成器可以遍历对象 a,因此能够输出 1, 3, 5。而 (i in b1) 需要好好揣摩,这里你是不是能联想到 for in 语句? 没错,这里的(i in b1),大致等价于下面这段代码:

这里非常巧妙地利用生成器的特性,next() 函数运行的时候,保存了当前的指针。比如再看下面这个示例:

至于最后的 all() 函数,就很简单了。它用来判断一个迭代器的元素是否全部为 True,如果是则返回 True,否则就返回 False。

三、总结

总结一下,今天我们讲了四种不同的对象,分别是容器、可迭代对象、迭代器和生成器。

1、容器是可迭代对象,可迭代对象调用 iter() 函数,可以得到一个迭代器。迭代器可以通过 next() 函数来得到下一个元素,从而支持遍历。

2、生成器是一种特殊的迭代器(注意这个逻辑关系反之不成立)。使用生成器,你可以写出来更加清晰的代码;合理使用生成器,可以降低内存占用、优化程序结构、提高程序速度。

3、生成器在 Python 2 的版本上,是协程的一种重要实现方式;而 Python 3.5 引入 async await 语法糖后,生成器实现协程的方式就已经落后了。


如果您觉得本站对你有帮助,那么可以支付宝扫码捐助以帮助本站更好地发展,在此谢过。
喜欢 (0)
[资助本站您就扫码 谢谢]
分享 (0)

您必须 登录 才能发表评论!