Skip to content

Latest commit

 

History

History
379 lines (254 loc) · 4.77 KB

072.md

File metadata and controls

379 lines (254 loc) · 4.77 KB

迭代器

简介

迭代器对象可以在 for 循环中使用:

In [1]:

x = [2, 4, 6]

for n in x:
    print n
2
4
6

其好处是不需要对下标进行迭代,但是有些情况下,我们既希望获得下标,也希望获得对应的值,那么可以将迭代器传给 enumerate 函数,这样每次迭代都会返回一组 (index, value) 组成的元组:

In [2]:

x = [2, 4, 6]

for i, n in enumerate(x):
    print 'pos', i, 'is', n
pos 0 is 2
pos 1 is 4
pos 2 is 6

迭代器对象必须实现 __iter__ 方法:

In [3]:

x = [2, 4, 6]
i = x.__iter__()
print i
<listiterator object at 0x0000000003CAE630>

__iter__() 返回的对象支持 next 方法,返回迭代器中的下一个元素:

In [4]:

print i.next()
2

当下一个元素不存在时,会 raise 一个 StopIteration 错误:

In [5]:

print i.next()
print i.next()
4
6

In [6]:

i.next()
---------------------------------------------------------------------------
StopIteration                             Traceback (most recent call last)
<ipython-input-6-e590fe0d22f8> in <module>()
----> 1  i.next()

StopIteration: 

很多标准库函数返回的是迭代器:

In [7]:

r = reversed(x)
print r
<listreverseiterator object at 0x0000000003D615F8>

调用它的 next() 方法:

In [8]:

print r.next()
print r.next()
print r.next()
6
4
2

字典对象的 iterkeys, itervalues, iteritems 方法返回的都是迭代器:

In [9]:

x = {'a':1, 'b':2, 'c':3}
i = x.iteritems()
print i
<dictionary-itemiterator object at 0x0000000003D51B88>

迭代器的 __iter__ 方法返回它本身:

In [10]:

print i.__iter__()
<dictionary-itemiterator object at 0x0000000003D51B88>

In [11]:

print i.next()
('a', 1)

自定义迭代器

自定义一个 list 的取反迭代器:

In [12]:

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]:

x = range(10)
for i in ReverseListIterator(x):
    print i,
9 8 7 6 5 4 3 2 1 0

只要我们定义了这三个方法,我们可以返回任意迭代值:

In [14]:

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 猜想

  • 奇数 n:返回 3n + 1
  • 偶数 n:返回 n / 2

直到 n 为 1 为止:

In [15]:

for x in Collatz(7):
    print x,
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

不过迭代器对象存在状态,会出现这样的问题:

In [16]:

i = Collatz(7)
for x, y in zip(i, i):
    print x, y
22 11
34 17
52 26
13 40
20 10
5 16
8 4
2 1

一个比较好的解决方法是将迭代器和可迭代对象分开处理,这里提供了一个二分树的中序遍历实现:

In [17]:

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]:

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]:

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]:

for value in tree:
    print value,
1 2 3 4 5 6 7 8

不会出现之前的问题:

In [21]:

for x,y in zip(tree, tree):
    print x, y
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8