Python 学习笔记 #6 —— Iterator 迭代器
Posted on 2020-05-24 22:47 in CS
What is Iterator
Sequence 是 python 中的一种数据结构,它们的成员是有序排列的,可以通过下标来访问特定元素,比如字符串、list、tuple 等都是 sequence。很多时候我们需要对 sequence 进行顺序访问,最简单的方法是写一个 for 循环,通过计数的方式实现迭代。但是计数的方式很原始也不高效,所以 python 提供了 iterator 来迭代 sequence。Iterator 在 Python 中使用非常广泛,它不仅对 sequence 的支持是无缝的,它还能迭代那些具有 sequence 的行为但实际上并不是 sequence 的对象,比如 dict 的 keys 以及 file。
Iterator 实际上是一个实现了工厂模式的对象,它通过 next()
方法来获取元素,而不是通过 index 计数来实现。for 循环只要调用 iterator 的 next 方法,就能获得 sequence 中的下一项,当迭代完所有的 item 后,再次调用会返回一个 StopIteration
的异常,这个异常并不代表发生了错误,而是告诉调用者,迭代已经完成了。
Iteratable vs Iterator
含有 __iter__()
或 __getitem__()
方法的对象称为 “ 可迭代对象 ”:Iteratable
可以用 isinstance()
判断一个对象是否为 Iteratable
对象,
1 2 3 4 5 6 7 |
|
实现了 next()
方法的对象称为迭代器:Iterator
可以用 isinstance()
判断一个对象是否为 Iterator
对象,
1 2 3 4 5 6 7 |
|
lsit
, dict
, str
等都是 Iterable
,但不是 Iterator
,可以用 iter()
得到其对应的 Iterator
实际上,python 的 for 循环作用于 Iterable 时,会自动调用 iter()
来得到对应的 Iterator,然后不断调用 next 获取其中的元素,
1 2 |
|
Python 在底层实现时,会自动替换成下面的方式,
1 2 3 4 5 6 7 |
|
结论:对于 Iterable
对象,我们可以直接用 for 循环来迭代。
Why Iterator
翻译自 PEP234:
- 提供了一种可扩展的 iterator 接口
- 加强了 list 的迭代性能
- dict 的迭代性能巨大提升
- 迭代功能的底层实现是真正的迭代,而不是用随机访问来模拟
- 兼容目前已有的所有用户自定义的 class、模拟 sequence 和 dict 的扩展对象、甚至那些只实现了
{__getitee__, keys, valus, itmes}
的 mappings - 迭代那些非 sequence 对象的代码可以更加简洁,可读性更高
Construct Iterator
如何得到一个迭代器呢?
BIT
对于 Python 内建数据类型,比如容器,只需要用内建函数 iter()
就可以得到对应的迭代器,具体有两种调用方式:
1 2 |
|
iter(obj)
,返回一个迭代器iter(func, sentinel)
,iter 会重复调用 func,直到迭代返回值为 sentinel 时停止迭代
Delegate
如果是一个自定义容器,内部包含一个 list、tuple、dict 等可迭代对象,那么可以直接在自定义容器中定义一个 __iter()__
方法,将迭代请求委托到容器内容对象上。
1 2 3 4 5 6 7 |
|
Implement Iterator Protocal
有时候内建类型的迭代协议无法满足我们的需求,这个时候可以自行实现迭代协议。只要一个 class 实现了下面两个方法,就可以当作迭代器来使用,
- 一个
__iter()__
方法,返回值是self
- 一个
next()
方法,返回一个 item 或者是 StopIteration 异常
这两个方法分别对应了前面区分过的两种协议,
- 任意一个实现了
__iter()__
或__getitme__()
的对象,都可以用 for 循环来迭代 —— Iterable 对象 - 任意一个实现了
next()
的对象都可以当作是 iterator —— Iterator 协议
迭代的概念本身只涉及第二种协议,容器类的对象一般都支持第一种协议。目前 iterator 要求这两种协议都支持,支持第一种协议的目的是为了让 iterator 同时也是 Iterable,这样它的行为和 sequence 类似,特别是在用 for 循环中使用 iterator 的场景。
example:
定义一个产生随机 sequence 的 class,然后使用 for 循环迭代该对象,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
也可以像前面介绍的一样,用 isinstance()
来检查,说明我们的 RandSeq 类既是一个 Iterable 也是一个 Iterator。
1 2 |
|
Generator
Generator 是一种特殊的 iterator,最典型的例子就是 Fibonacci 数列。可以直接根据需要写一个 generator 直接调用,
1 2 3 4 5 6 7 8 |
|
如果 generator 涉及到比较复杂的控制(比如暴露属性等),可以把 generator 函数扩展成 class 形式。比如前面的 RandSeq 例子可以扩展出更加复杂的功能,然后将 __iter__
内部的 return 改为 yield 即可。
Using Iterator
Sequence
1 2 3 4 5 6 7 8 9 10 11 12 |
|
Dict
- dict 内部实现了一个
sq_contaisn
的函数,它实现了has_key()
相同的功能,所以可以这么写,
1 2 3 4 |
|
- dict 内部还实现了一个
tp_iter
的函数,可以产生一个针对所有 keys 的高效迭代器。所以可以这么写,
1 2 3 4 |
|
只要不违反 “ 禁止修改 dict 内容 ” 的约束,就可以这么用。
- dict 实际上有 3 种 iterator,
for x in dict
实际上是for x in dict.iterkeys()
的缩写
1 2 3 4 5 |
|
File
file 对象内部实现了 tp_iter
方法,所以访问文件内容的代码可以写得更简洁,
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
Restrictions
Note
在用 iterator 时,sequence/dict 的内容是不能被修改的。
sequence 中除了 list,其它(tuple 和 string)都是不可变的,所以只需要注意 list 的情况即可。对于 dict,只允许对一个已经存在的 key 设置它的值,其他操作(增加 / 删除 /update()
)都是不允许的。原因就是 iterator 和实际对象是绑定在一起的,一旦修改了原对象,效果会马上体现出来。
1 2 3 4 5 6 7 8 |
|
实际上,在 python 的迭代器出现之前,这个限制就已经存在了,比如 C++ 也有类似的约束。
Special Iterator
Reversed Iterator
获得一个反向迭代器的方式:
- 调用 BIF
reversed()
- 实现
__reversed__()
方法 - 将对象转化为 list 对象
- 使用 generator
直接使用 reversed()
的问题在于待处理的对象必须是大小确定的,如果一个对象大小不固定而且又没有实现 __reversed__()
方法,那么直接将其转化为 list 对象可能会占用大量内存,更优的做法是在 __reversed__()
中定义一个 generator。
Using itertools
Python 内建的工具包,可以产生一系列各种各样的 iterator,比如无穷迭代器 count()
, cycle()
, repeat()
,有限长度的 accumulate()
, compress()
, chain()
等。
1 2 3 4 5 |
|
itertools
常见的 iterator 有:
- 生成切片:
itertools.islice()
- 丢弃部分数据:
itertools.dropwhile()
- 产生所有排列组合:
itertools.permutations()
- 一次性迭代不同容器内的元素:
itertools.chain()
总结:遇到看似复杂的迭代任务,不要着急自己写复杂的 for index 循环或者是 iterator,而是应该首先看看 itertools
里面是否提供了相关功能,往往有惊喜。
enumerate()
如果想在迭代对象时,同时知道对应的索引,该怎么办?
或许你会想在 iterator 的基础上,再加一个计数器,在每次 for 循环中不断自增,类似这样,
1 2 3 4 5 6 |
|
但是这种写法很丑陋,最优雅的答案是用内建函数 enumerate()
,它的返回值是一个 enumerate
对象,本质上就是个迭代器,返回一个由 index 和 value 组成的 tuple。
PEP 279 介绍了这个函数的实现原理,如下
1 2 3 4 5 6 7 |
|
使用方法:
1 2 |
|
zip()
如果想同时迭代多个对象,每次迭代分别从中取出一个元素,应该怎么办?
最优雅的方式是用 zip()
函数,zip 函数的返回值是一个 iterator,所以可以直接在 for 循环中使用,
1 2 3 4 5 |
|
Ref
PEP 279 -- The enumerate() built-in function
This post is part 7 of the "Python Notes" series:
- Python 学习笔记 #0 —— 新的开始
- Python 学习笔记 #1 —— PEP8 编程风格
- Python 学习笔记 #2 —— PEP8 实践
- Python 学习笔记 #3 —— Docstring 风格
- Python 学习笔记 #4 —— Python 之禅
- Python 学习笔记 #5 —— Comprehension 解析式
- Python 学习笔记 #6 —— Iterator 迭代器
- Python 学习笔记 #7 —— Generator 生成器
- Python 学习笔记 #8 —— Decorator 装饰器
- Python 学习笔记 #9 —— Function Arguments 函数参数
- Python 学习笔记 #10 —— Python 中的 FP