python中的迭代器和生成器

发表于 | 分类于 | | 阅读次数: |
字数统计: 2,896 字 | 阅读时长 ≈ 12 分钟
Python中的迭代协议

Python是面向协议编程的，我们说的迭代协议一般是指__iter__魔法函数。

迭代器是访问集合内元素的一种方式， 一般用来遍历数据
迭代器和以下标的访问方式不一样， 迭代器是不能返回的, 迭代器提供了一种惰性方式数据的方式

迭代器和可迭代对象的区别

可迭代对象是什么呢？迭代器和可迭代有什么区别？我们看下源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from collections.abc import Iterable, Iterator

# Iterable 是指可迭代对象
class Iterable(metaclass=ABCMeta):

    __slots__ = ()

    @abstractmethod
    def __iter__(self):
        while False:
            yield None

    @classmethod
    def __subclasshook__(cls, C):
        if cls is Iterable:
            return _check_methods(C, "__iter__")
        return NotImplemented
  
 #  Iterator 是指迭代器
 class Iterator(Iterable):

    __slots__ = ()

    @abstractmethod
    def __next__(self):
        'Return the next item from the iterator. When exhausted, raise StopIteration'
        raise StopIteration

    def __iter__(self):
        return self

    @classmethod
    def __subclasshook__(cls, C):
        if cls is Iterator:
            return _check_methods(C, '__iter__', '__next__')
        return NotImplemented

从上面的源码中，我们看出可迭代对象是指实现了迭代协议__iter__的对象，而迭代器除了实现了迭代协议__iter__外还实现了魔法方法__next__。

我们看下内置类型list是可迭代对象还是迭代器对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
In [5]: a = [1,2,3]

In [6]: from collections import Iterable, Iterator

In [7]: isinstance(a, Iterable)
Out[7]: True

In [8]: isinstance(a, Iterator)
Out[8]: False

# 上述结果的原因我们可以查看list源码

class list(object):
    """
    list() -> new empty list
    list(iterable) -> new list initialized from iterable's items
    """
    def __iter__(self, *args, **kwargs): # real signature unknown
    """ Implement iter(self). """
    pass

我们看到list仅仅实现了__iter__，因此list是可迭代对象而不是迭代器。

Python中内置了一个iter()函数，可以返回一个迭代器对象，它接受的参数是一个实现了__iter__()方法的容器（也就是可迭代对象）。

1
2
3
4
In [9]: a = iter(a)

In [10]: isinstance(a, Iterator)
Out[10]: True
生成器函数的使用

这一小节我们将学习什么是生成器函数，及其使用。

函数里只要使用了yield关键字就是生成器函数了

image-20180710105026924

这里我们加上断点调试，发现生成器函数返回的不再是具体的值，而是一个生成器对象。

这里有小伙伴疑惑了，这个生成器对象应该在什么时候产生呢？

答案是：Python编译字节码的时候就产生了。

Python在运行之前会将代码编程字节码，在编译的时候发现生成器函数中存在 yield关键字，就会把对象的yield生成生成器对象。

生成的生成器函数我们如何使用呢？

因为生成器函数内部实现了可迭代协议，我们直接可以使用for循环。

1
2
for aa in ge:
    print(aa)

传统函数只能使用一次return进行数据返回，而生成器函数可以使用多次yield进行数据返回

1
2
3
4
def gen_func():
    yield 1
    yield 2
    yield 3

使用yield关键字使惰性求值和延迟求值成为了可能。（后面会学习到）

我们看下生成器函数的一个简单应用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 生成一个菲波那切数列 查找指定值的和
def fib(index):
    if index <= 2:
        return 1
    else:
        return fib(index - 1) + fib(index - 2)

# 记录每次相加的和
def fib2(index):
    re_list = []
    n, a, b = 0, 0, 1
    while n < index:
        re_list.append(b)
        a, b = b, a + b
        n += 1
    return re_list

# 使用yield记录
def gen_fib(index):
    n, a, b = 0, 0, 1
    while n < index:
        yield b
        a, b = b, a + b
        n += 1

我们看第二个和第三个函数，使用list记录会随着数值的增大而增加内存消耗，而使用yield生成器则不会消耗内存。

生成器的原理

在理解生成器的原理之前我们先看下Python中函数的运行原理。

我们先生成两个函数

1
2
3
4
5
def foo():
    bar()

def bar():
	pass

当我们运行上面的代码的时候，Python解释器python.exe会用一个叫做 PyEval_EvalFramEx(c函数)去执行foo函数， 这个函数首先会创建一个栈帧(stack frame)，这个栈帧是一个上下文，是编译器用来实现过程/函数调用的一种数据结构。

Python中一切皆对象 栈帧也是对象 解释器会将代码块也编译成字节码对象

我们可以使用dis查看函数代码编译成的字节码对象

1
2
3
4
5
6
7
8
9
10
11
import dis
print(dis.dis(foo))

# 输出

  2           0 LOAD_GLOBAL              0 (bar)
              2 CALL_FUNCTION            0
              4 POP_TOP
              6 LOAD_CONST               0 (None)
              8 RETURN_VALUE
None

上面字节码含义依次是加载全局，调用函数，从栈定抛出值，加载变量，返回。

在上面函数执行的过程是：

解释器在运行第一个函数foo的之前会创建一个栈帧对象，并将代码块编译成一个字节码对象，然后在栈帧对象的上下文中运行字节码对象，当函数运行到foo调用函数bar的时候，又是一次函数的调用，首先还是会创建一个栈帧对象，然后将函数的控制权交给新建的这个栈帧，然后在新创建的栈帧上下文运行bar函数对应的字节码。所有的栈帧都是分配在堆内存上，这就决定了栈帧可以独立于调用者存在

栈区（stack）— 由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。

堆区（heap） — 一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收 。

有关栈帧参考文章：

https://blog.csdn.net/Neil4/article/details/62416903

如何理解所有的栈帧都是分配在堆内存上，这就决定了栈帧可以独立于调用者存在这句话呢？

我们通过代码演示下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import inspect

frame = None


def foo():
    bar()


def bar():
    global frame
    frame = inspect.currentframe()
    
# 这里我们执行foo函数
foo()

# 获得栈帧
print(frame.f_code.co_name)
# 输出结果：bar

# 虽然上面函数foo已经执行完毕，但是可以通过函数bar的栈帧对象获得foo函数的栈帧对象
# 获得调用bar的栈帧
caller_frame = frame.f_back
print(caller_frame.f_code.co_name)
# 输出结果：foo

我们将函数bar的栈帧赋值给全局变量，通过这个全局变量获得一些数据。

上述过程和静态语言有所不同，静态语言函数的调用是栈的形式，函数调用完成则栈全部清空。而动态语言是放在堆上的。

上面代码执行的过程包含一个递归的过程，当执行到foo的时候回再次调用bar。我们看下龟叔画的一张图：

image-20180710143935727

上面这张图片就很形象的解释了上面代码整个调用过程。

我们了解了函数的执行过程对于我们了解生成器是很有帮助的，因为生成器正是利用了栈帧是保存在内存中这一特性。

下面我们在看一个生成器函数。

1
2
3
4
5
6
7
8
9
def gen_func():
    yield 1
    name = "hongshaorou"
    yield 2
    age = 20
    return "xiaomanong"

# 生成器函数返回的是一个生成器对象
gen = gen_func()

生成器对象时对PythonFrame进行了一层封装：

image-20180710144728969

生成器对象在PyFrameObject和PyCodeObject上面又封装了PyGenObject即Python生成器对象。

我们看下生成器对象的字节码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
  2           0 LOAD_CONST               1 (1)
              2 YIELD_VALUE
              4 POP_TOP

  3           6 LOAD_CONST               2 ('hongshaorou')
              8 STORE_FAST               0 (name)

  4          10 LOAD_CONST               3 (2)
             12 YIELD_VALUE
             14 POP_TOP

  5          16 LOAD_CONST               4 (20)
             18 STORE_FAST               1 (age)

  6          20 LOAD_CONST               5 ('xiaomanong')
             22 RETURN_VALUE
None

我们可以从字节码中看到总共有两次YIELD_VALUE。

对于生成器对象，当我们每次调用的时候回运行到yield关键字就停止。

我们可以使用Python生成器对象的fram获得最近执行代码运行的字节码位置和local变量。

1
2
3
4
5
print(gen.gi_frame.f_lasti)
print(gen.gi_frame.f_locals)
# 输出
-1
{}

输出上述结果是因为我们并没有调用生成器对象。

1
2
3
4
5
6
next(gen)
print(gen.gi_frame.f_lasti)
print(gen.gi_frame.f_locals)
# 输出
2
{}

当我们调用一次的时候，即运行了一次yield。这时运行到了字节码为2的位置，local变量为空。

1
2
3
4
5
6
next(gen)
print(gen.gi_frame.f_lasti)
print(gen.gi_frame.f_locals)
# 输出
12
{'name': 'hongshaorou'}

当我们再调用一次的时候，即再运行了一次yield。这是字节码运行到了12的位置，local在字节码为6的时候已经加载了值，所以local变量不再为空。

上述过程证明了对于生成器函数，使用yield生成的生成器对象，我们可以通过PyGenObject对函数的暂停和前进有了进一步的了解。因为我们可以通过变量获得函数具体执行到哪一步。这样就完成了整个函数的运行控制，通过yield来暂停函数。生成器就是依赖这种方式实现的。

生成器对象分配在堆内存中和之前的函数调用栈帧一样，可以独立于函数的调用。对于生成器对象，每次调用都会生成一个栈帧对象，然后获得生成器对象，由生成器对象控制程序往前走。也就是说我们可以在任何地方，只要获得这个生成器对象，都可以恢复暂停它。这也是协程的基础。

生成器在UserList中的使用

很多同学可能都不知道什么是UserList（其实我也不知道🤷‍♀️），UserList其实是Python实现的List，可以用来解释List是如何实现的（Python内置的List是C语言实现的）。如果我们想自定义List可以继承UserList。

我们通过源码查看下实现原理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from collections import UserList


class UserList(MutableSequence):
    """A more or less complete user-defined wrapper around list objects."""
    
# UserList 继承自可变序列 MutableSequence 

class MutableSequence(Sequence):

    __slots__ = ()
# MutableSequence 又继承自Sequence

class Sequence(Reversible, Collection):

    """All the operations on a read-only sequence.

    Concrete subclasses must override __new__ or __init__,
    __getitem__, and __len__.
    """

    __slots__ = ()

    @abstractmethod
    def __getitem__(self, index):
        raise IndexError

    def __iter__(self):
        i = 0
        try:
            while True:
                v = self[i]
                yield v
                i += 1
        except IndexError:
            return

从源码中我们可以看到使用了yield。每次调用next()函数会保存变量i记录到何处位置。这样就完成了全部的遍历。

生成器如何读取大文件

该代码为老师实际工作遇到的一个需求，文件过大，文件内容全部为一行，有指定分隔符进行分割。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def myreadlines(f, newline):
    buf = ""
    while True:
        while newline in buf:
            pos = buf.index(newline)
            yield buf[:pos]
            buf = buf[pos + len(newline):]
        chunk = f.read(4096)

        if not chunk:
            # 说明已经读到了文件结尾
            yield buf
            break
        buf += chunk


with open("input.txt") as f:
    for line in myreadlines(f, "{|}"):
        print(line)

本章收获颇多，加油ヾ(◍°∇°◍)ﾉﾞ！

知识就是财富
如果您觉得文章对您有帮助, 欢迎请我喝杯水！