Python 学习笔记 #6 —— Iterator 迭代器

What is Iterator

PEP 234 -- Iterators 原文链接。

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

from collections import Iterable

isinstance([], Iterable)  # True
isinstance({}, Iterable)  # True
isinstance('abc', Iterable) # True
isinstance(100, Iterable)  # False
isinstance(x for x in range(10), Iterable)  # True

实现了 next() 方法的对象称为迭代器：Iterator

可以用 isinstance() 判断一个对象是否为 Iterator 对象，

1
2
3
4
5
6
7

from collections import Iterator

isinstance([], Iterator)  # False
isinstance({}, Iterator)  # False
isinstance('abc', Iterator)  # False
isinstance(100, Iterator)  # False
isinstance(x for x in range(10), Iterator)  # True

lsit, dict, str 等都是 Iterable，但不是 Iterator，可以用 iter() 得到其对应的 Iterator

实际上，python 的 for 循环作用于 Iterable 时，会自动调用 iter() 来得到对应的 Iterator，然后不断调用 next 获取其中的元素，

1
2

for i in seq:
    do_something_to(i)

Python 在底层实现时，会自动替换成下面的方式，

1
2
3
4
5
6
7

fetch = iter(seq)
while True:
    try:
        i = fetch.next()
    except StopIteration:
        break
    do_something_to(i)

结论：对于 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(obj)，返回一个迭代器
• iter(func, sentinel)，iter 会重复调用 func，直到迭代返回值为 sentinel 时停止迭代

Delegate

如果是一个自定义容器，内部包含一个 list、tuple、dict 等可迭代对象，那么可以直接在自定义容器中定义一个 __iter()__ 方法，将迭代请求委托到容器内容对象上。

1
2
3
4
5
6
7

class Node(object):
    def __init__(self, value):
        self._value = value
        self._children = []

    def __iter__(self):
        return iter(self._children)

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

#! /usr/bin/env python

from random import choice

class RandSeq(object):
    def __init__ (self, seq):
        self.data = seq

    def __iter__ (self):
        return self

    def next(self):
        return choice(self.data)

seq = RandSeq(('rock', 'paper', 'scissors'))

for item in seq:
    print item

也可以像前面介绍的一样，用 isinstance() 来检查，说明我们的 RandSeq 类既是一个 Iterable 也是一个 Iterator。

1
2

isinstance(seq, Iterable)  # True
isinstance(seq, Iterator)  # True

Generator

Generator 是一种特殊的 iterator，最典型的例子就是 Fibonacci 数列。可以直接根据需要写一个 generator 直接调用，

1
2
3
4
5
6
7
8

def frange(start, stop, increment):
    x = start
    while x < stop:
        yiled x
        x += increment

for n in frange(0, 4, 0.5)
    print(n)

如果 generator 涉及到比较复杂的控制（比如暴露属性等），可以把 generator 函数扩展成 class 形式。比如前面的 RandSeq 例子可以扩展出更加复杂的功能，然后将 __iter__ 内部的 return 改为 yield 即可。

Using Iterator

Sequence

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

>>> myTuple = (123, 'xyz', 45.67)
>>> i = iter(myTuple)
>>> i.next()
123
>>> i.next()
'xyz'
>>> i.netx()
45.67
>>> i.next()
Traceback (most recent call last):
  File "<stdin>, line 1, in <module>
StopIteration

Dict

• dict 内部实现了一个 sq_contaisn 的函数，它实现了 has_key() 相同的功能，所以可以这么写，

1
2
3
4

if k in dict: ...

# equivalent to
if dict.has_key(k): ...

• dict 内部还实现了一个 tp_iter 的函数，可以产生一个针对所有 keys 的高效迭代器。所以可以这么写，

1
2
3
4

for k in dict: ...

# equivalent to, but much faster than
for k in dict.keys(): ...

只要不违反 “ 禁止修改 dict 内容 ” 的约束，就可以这么用。

• dict 实际上有 3 种 iterator，for x in dict 实际上是 for x in dict.iterkeys() 的缩写

1
2
3
4
5

for key in dict.iterkeys(): ...

for value in dict.itervalues(): ...

for key, value in dict.iteritems(): ...

File

file 对象内部实现了 tp_iter 方法，所以访问文件内容的代码可以写得更简洁，

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

for line in myFile:
    print line

# as a shorthand for
for line in iter(file.readline, ""):
    print line

# equivalent, but faster than
while 1:
    line = file.readline()
    if not line:
        break
    print line

Restrictions

sequence 中除了 list，其它（tuple 和 string）都是不可变的，所以只需要注意 list 的情况即可。对于 dict，只允许对一个已经存在的 key 设置它的值，其他操作（增加 / 删除 /update()）都是不允许的。原因就是 iterator 和实际对象是绑定在一起的，一旦修改了原对象，效果会马上体现出来。

1
2
3
4
5
6
7
8

# legal
myDict = {'a': 1, 'b': 2, 'c': 3}
for key in myDict:
    myDict[key] = myDict[key] + 1

# illegal
for key in myDict:
    del myDict[key]

实际上，在 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

from itertools import count

counter = count(10)
next(counter)  # 10
next(counter)  # 11

itertools 常见的 iterator 有：

• 生成切片： itertools.islice()
• 丢弃部分数据： itertools.dropwhile()
• 产生所有排列组合： itertools.permutations()
• 一次性迭代不同容器内的元素： itertools.chain()

总结：遇到看似复杂的迭代任务，不要着急自己写复杂的 for index 循环或者是 iterator，而是应该首先看看 itertools 里面是否提供了相关功能，往往有惊喜。

enumerate()

如果想在迭代对象时，同时知道对应的索引，该怎么办？

或许你会想在 iterator 的基础上，再加一个计数器，在每次 for 循环中不断自增，类似这样，

1
2
3
4
5
6

my_list = ['a', 'b', 'c']

idx = 1
for val in my_list:
    print idx, val
    idx = idx + 1

但是这种写法很丑陋，最优雅的答案是用内建函数 enumerate()，它的返回值是一个 enumerate 对象，本质上就是个迭代器，返回一个由 index 和 value 组成的 tuple。

PEP 279 介绍了这个函数的实现原理，如下

1
2
3
4
5
6
7

def enumerate(collection):
    'Generates an indexed series: (0, coll[0]), (1, coll[1]) ...'
    i = 0
    it = iter(collection)
    while 1:
        yield (i, it.next())
        i += 1

使用方法：

1
2

for idx, val in enumerate(my_list):
    print idx, val

zip()

如果想同时迭代多个对象，每次迭代分别从中取出一个元素，应该怎么办？

最优雅的方式是用 zip() 函数，zip 函数的返回值是一个 iterator，所以可以直接在 for 循环中使用，

1
2
3
4
5

a = [1, 2, 3]
b = ['a', 'b', 'c']

for i in zip(a, b)
    print i

Ref

PEP 234 -- Iterator

PEP 279 -- The enumerate() built-in function

Python 核心编程

Python Cookbook

迭代器 - 廖雪峰的官方网站

Iterables vs. Iterators vs. Generators

完全理解 Python 迭代对象、迭代器、生成器