mirror of
https://github.com/apachecn/ailearning.git
synced 2026-02-09 13:25:39 +08:00
379 lines
4.8 KiB
Markdown
379 lines
4.8 KiB
Markdown
# 迭代器
|
||
|
||
## 简介
|
||
|
||
迭代器对象可以在 `for` 循环中使用：
|
||
|
||
In [1]:
|
||
|
||
```py
|
||
x = [2, 4, 6]
|
||
|
||
for n in x:
|
||
print n
|
||
|
||
```
|
||
|
||
```py
|
||
2
|
||
4
|
||
6
|
||
|
||
```
|
||
|
||
其好处是不需要对下标进行迭代，但是有些情况下，我们既希望获得下标，也希望获得对应的值，那么可以将迭代器传给 `enumerate` 函数，这样每次迭代都会返回一组 `(index, value)` 组成的元组：
|
||
|
||
In [2]:
|
||
|
||
```py
|
||
x = [2, 4, 6]
|
||
|
||
for i, n in enumerate(x):
|
||
print 'pos', i, 'is', n
|
||
|
||
```
|
||
|
||
```py
|
||
pos 0 is 2
|
||
pos 1 is 4
|
||
pos 2 is 6
|
||
|
||
```
|
||
|
||
迭代器对象必须实现 `__iter__` 方法：
|
||
|
||
In [3]:
|
||
|
||
```py
|
||
x = [2, 4, 6]
|
||
i = x.__iter__()
|
||
print i
|
||
|
||
```
|
||
|
||
```py
|
||
<listiterator object at 0x0000000003CAE630>
|
||
|
||
```
|
||
|
||
`__iter__()` 返回的对象支持 `next` 方法，返回迭代器中的下一个元素：
|
||
|
||
In [4]:
|
||
|
||
```py
|
||
print i.next()
|
||
|
||
```
|
||
|
||
```py
|
||
2
|
||
|
||
```
|
||
|
||
当下一个元素不存在时，会 `raise` 一个 `StopIteration` 错误：
|
||
|
||
In [5]:
|
||
|
||
```py
|
||
print i.next()
|
||
print i.next()
|
||
|
||
```
|
||
|
||
```py
|
||
4
|
||
6
|
||
|
||
```
|
||
|
||
In [6]:
|
||
|
||
```py
|
||
i.next()
|
||
|
||
```
|
||
|
||
```py
|
||
---------------------------------------------------------------------------
|
||
StopIteration Traceback (most recent call last)
|
||
<ipython-input-6-e590fe0d22f8> in <module>()
|
||
----> 1 i.next()
|
||
|
||
StopIteration:
|
||
```
|
||
|
||
很多标准库函数返回的是迭代器：
|
||
|
||
In [7]:
|
||
|
||
```py
|
||
r = reversed(x)
|
||
print r
|
||
|
||
```
|
||
|
||
```py
|
||
<listreverseiterator object at 0x0000000003D615F8>
|
||
|
||
```
|
||
|
||
调用它的 `next()` 方法：
|
||
|
||
In [8]:
|
||
|
||
```py
|
||
print r.next()
|
||
print r.next()
|
||
print r.next()
|
||
|
||
```
|
||
|
||
```py
|
||
6
|
||
4
|
||
2
|
||
|
||
```
|
||
|
||
字典对象的 `iterkeys, itervalues, iteritems` 方法返回的都是迭代器：
|
||
|
||
In [9]:
|
||
|
||
```py
|
||
x = {'a':1, 'b':2, 'c':3}
|
||
i = x.iteritems()
|
||
print i
|
||
|
||
```
|
||
|
||
```py
|
||
<dictionary-itemiterator object at 0x0000000003D51B88>
|
||
|
||
```
|
||
|
||
迭代器的 `__iter__` 方法返回它本身：
|
||
|
||
In [10]:
|
||
|
||
```py
|
||
print i.__iter__()
|
||
|
||
```
|
||
|
||
```py
|
||
<dictionary-itemiterator object at 0x0000000003D51B88>
|
||
|
||
```
|
||
|
||
In [11]:
|
||
|
||
```py
|
||
print i.next()
|
||
|
||
```
|
||
|
||
```py
|
||
('a', 1)
|
||
|
||
```
|
||
|
||
## 自定义迭代器
|
||
|
||
自定义一个 list 的取反迭代器：
|
||
|
||
In [12]:
|
||
|
||
```py
|
||
class ReverseListIterator(object):
|
||
|
||
def __init__(self, list):
|
||
self.list = list
|
||
self.index = len(list)
|
||
|
||
def __iter__(self):
|
||
return self
|
||
|
||
def next(self):
|
||
self.index -= 1
|
||
if self.index >= 0:
|
||
return self.list[self.index]
|
||
else:
|
||
raise StopIteration
|
||
|
||
```
|
||
|
||
In [13]:
|
||
|
||
```py
|
||
x = range(10)
|
||
for i in ReverseListIterator(x):
|
||
print i,
|
||
|
||
```
|
||
|
||
```py
|
||
9 8 7 6 5 4 3 2 1 0
|
||
|
||
```
|
||
|
||
只要我们定义了这三个方法，我们可以返回任意迭代值：
|
||
|
||
In [14]:
|
||
|
||
```py
|
||
class Collatz(object):
|
||
|
||
def __init__(self, start):
|
||
self.value = start
|
||
|
||
def __iter__(self):
|
||
return self
|
||
|
||
def next(self):
|
||
if self.value == 1:
|
||
raise StopIteration
|
||
elif self.value % 2 == 0:
|
||
self.value = self.value / 2
|
||
else:
|
||
self.value = 3 * self.value + 1
|
||
return self.value
|
||
|
||
```
|
||
|
||
这里我们实现 [Collatz 猜想](http://baike.baidu.com/view/736196.htm)：
|
||
|
||
* 奇数 n：返回 3n + 1
|
||
* 偶数 n：返回 n / 2
|
||
|
||
直到 n 为 1 为止：
|
||
|
||
In [15]:
|
||
|
||
```py
|
||
for x in Collatz(7):
|
||
print x,
|
||
|
||
```
|
||
|
||
```py
|
||
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
|
||
|
||
```
|
||
|
||
不过迭代器对象存在状态，会出现这样的问题：
|
||
|
||
In [16]:
|
||
|
||
```py
|
||
i = Collatz(7)
|
||
for x, y in zip(i, i):
|
||
print x, y
|
||
|
||
```
|
||
|
||
```py
|
||
22 11
|
||
34 17
|
||
52 26
|
||
13 40
|
||
20 10
|
||
5 16
|
||
8 4
|
||
2 1
|
||
|
||
```
|
||
|
||
一个比较好的解决方法是将迭代器和可迭代对象分开处理，这里提供了一个二分树的中序遍历实现：
|
||
|
||
In [17]:
|
||
|
||
```py
|
||
class BinaryTree(object):
|
||
def __init__(self, value, left=None, right=None):
|
||
self.value = value
|
||
self.left = left
|
||
self.right = right
|
||
|
||
def __iter__(self):
|
||
return InorderIterator(self)
|
||
|
||
```
|
||
|
||
In [18]:
|
||
|
||
```py
|
||
class InorderIterator(object):
|
||
|
||
def __init__(self, node):
|
||
self.node = node
|
||
self.stack = []
|
||
|
||
def next(self):
|
||
if len(self.stack) > 0 or self.node is not None:
|
||
while self.node is not None:
|
||
self.stack.append(self.node)
|
||
self.node = self.node.left
|
||
node = self.stack.pop()
|
||
self.node = node.right
|
||
return node.value
|
||
else:
|
||
raise StopIteration()
|
||
|
||
```
|
||
|
||
In [19]:
|
||
|
||
```py
|
||
tree = BinaryTree(
|
||
left=BinaryTree(
|
||
left=BinaryTree(1),
|
||
value=2,
|
||
right=BinaryTree(
|
||
left=BinaryTree(3),
|
||
value=4,
|
||
right=BinaryTree(5)
|
||
),
|
||
),
|
||
value=6,
|
||
right=BinaryTree(
|
||
value=7,
|
||
right=BinaryTree(8)
|
||
)
|
||
)
|
||
|
||
```
|
||
|
||
In [20]:
|
||
|
||
```py
|
||
for value in tree:
|
||
print value,
|
||
|
||
```
|
||
|
||
```py
|
||
1 2 3 4 5 6 7 8
|
||
|
||
```
|
||
|
||
不会出现之前的问题：
|
||
|
||
In [21]:
|
||
|
||
```py
|
||
for x,y in zip(tree, tree):
|
||
print x, y
|
||
|
||
```
|
||
|
||
```py
|
||
1 1
|
||
2 2
|
||
3 3
|
||
4 4
|
||
5 5
|
||
6 6
|
||
7 7
|
||
8 8
|
||
|
||
``` |