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

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 对象，

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 对象，

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 在底层实现时，会自动替换成下面的方式，

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

如何得到一个迭代器呢？

对于 Python 内建数据类型，比如容器，只需要用内建函数 iter() 就可以得到对应的迭代器，具体有两种调用方式：

1
2

iter(obj)
iter(func, sentinel)

iter(obj)，返回一个迭代器
iter(func, sentinel)，iter 会重复调用 func，直到迭代返回值为 sentinel 时停止迭代

Delegate

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

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 循环迭代该对象，

#! /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 直接调用，

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

>>> 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 内部实现了一个 sq_contaisn 的函数，它实现了 has_key() 相同的功能，所以可以这么写，

if k in dict: ...

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

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

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() 的缩写

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

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

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

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

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

在用 iterator 时，sequence/dict 的内容是不能被修改的。

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

# 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() 等。

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 循环中不断自增，类似这样，

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 介绍了这个函数的实现原理，如下

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 循环中使用，

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

for i in zip(a, b)
    print i

PEP 234 -- Iterator

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

Python 核心编程

Python Cookbook

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

Iterables vs. Iterators vs. Generators

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

What is Iterator

Iteratable vs Iterator

Why Iterator

Construct Iterator

Delegate

Implement Iterator Protocal

Generator

Using Iterator

Sequence

Restrictions

Special Iterator

Reversed Iterator

Using `itertools`

`enumerate()`

`zip()`

Recommend

Python 学习笔记 #7 —— Generator 生成器

Python 学习笔记 #8 —— Decorator 装饰器

小白期货CTP程序化交易开发入门（五）--C#程序获取Tick数据

小白期货CTP程序化交易开发入门（六）--C#程序自动订阅所有合约的Tick数据

小白期货CTP程序化交易开发入门（七）--C++自动收取所有行情数据

数字货币(1)-python爬取行情

香农的无限网格策略

期现套利机会_20200731

数字货币的python量化交易（二）--Rsi短周期策略

python standard_library Built-in Exception

About Joyk

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

What is Iterator

Iteratable vs Iterator

Why Iterator

Construct Iterator

Delegate

Implement Iterator Protocal

Generator

Using Iterator

Sequence

Restrictions

Special Iterator

Reversed Iterator

Using itertools

enumerate()

zip()

Recommend

About Joyk

Using `itertools`

`enumerate()`

`zip()`