编程入门15：Python迭代机制

上一篇：编程入门14：Python模式匹配

我们已熟悉了“迭代”这一概念，许多数据类型都支持迭代。可迭代对象的判断依据是看其成员中有没有__iter__，只要对象定义了__iter__方法，我们就能使用iter函数返回对象的“迭代器”（Iterator）——Python迭代操作的统一机制是先把可迭代对象转成迭代器，然后逐个取出迭代器中的元素，如果没有元素可取则停止迭代并抛出StopIteration异常。以下代码演示了如何手动获取并操作迭代器：

In [1]: s = "迭代"

In [2]: hasattr(s, "__iter__")  # hasattr函数判断对象有无特定属性
Out[2]: True

In [3]: i = iter(s)  # iter函数使用可迭代对象的__iter__方法返回迭代器

In [4]: type(i)
Out[4]: str_iterator

In [5]: next(i)  # next函数返回迭代器里的下一个元素
Out[5]: '迭'

In [6]: next(i)
Out[6]: '代'

In [7]: next(i)  # 迭代器里的元素耗尽后将停止迭代抛出异常
Traceback (most recent call last):

  File "<ipython-input-7-a883b34d6d8a>", line 1, in <module>
    next(i)

StopIteration

多数时候我们都会使用for语句来进行循环迭代，在解释器内部自动完成上述操作——迭代器是一次性使用的特殊可迭代对象，其中的元素取一个就少一个。以下代码对迭代器使用成员运算符in，同样也是逐个取出元素：

In [8]: i = iter("ab")

In [9]: "a" in i  # 取出一个元素即满足条件结束迭代
Out[9]: True

In [10]: "b" in i  # 后面的元素还存在
Out[10]: True

In [11]: i = iter("ab")

In [12]: "b" in i  # 取出两个元素才满足条件结束迭代
Out[12]: True

In [13]: "a" in i  # 前面的元素已取走
Out[13]: False

迭代器一定包含__next__方法，当我们调用next函数时就会执行迭代器的__next__方法。下面让我们尝试定义一个迭代器类，逐个输出2的正整数次幂：

class Power2n:
    """2的正整数次幂数列迭代器类
    """
    def __init__(self, n):
        self.n = n  # 数列长度
        self.cur = 1  # 当前幂次

    def __iter__(self):  # 可迭代对象必须实现__iter__方法来返回迭代器
        return self

    def __next__(self):  # 迭代器必须实现__next__方法来返回下一个元素
        if self.n >= self.cur:
            result = 2 ** self.cur
            self.cur += 1
            return result
        else:  # 没有元素可返回则抛出停止迭代异常
            raise StopIteration()

迭代器初始化时不会把所有元素都载入内存，而是等__next__方法被调用时返回一个元素，这样无论要迭代多少次，所消耗的内存空间都保持不变。

迭代器很好用，但定义起来有点繁琐，为此Python又提供了“生成器”（Generator）——同样输出2的正整数次幂数列，只需如下的生成器函数：

def Power2nX(n):
    """2的正整数次幂数列生成器函数
    """
    for i in range(1, n + 1):
        yield 2 ** i

可以看到生成器函数很像普通函数，只是改用yield关键词而非return来返回值，这样返回的就是一个生成器对象。生成器是特殊的迭代器，会自动实现迭代方法，并自动处理迭代异常。当调用生成器的__next__方法时，将执行对应生成器函数到yield语句返回一个值，下次调用时会从离开位置之后继续执行返回下一个值。

生成器函数已经相当简洁，不过Python还提供了更为紧凑的“解析式”（Comprehension）语法，基于可迭代对象经过简单运算推导出新的列表或者生成器——所以想要输出2的正整数次幂数列，其实只要一行语句就够了：

In [14]: import sys  # 标准库系统模块

In [15]: l = [2**n for n in range(1, 11)]  # 列表解析式

In [16]: l
Out[16]: [2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]

In [17]: sys.getsizeof(l)  # 查看对象占用字节数
Out[17]: 192

In [18]: g = (2**n for n in range(1, 11))  # 生成器解析式

In [19]: type(g)
Out[19]: generator

In [20]: sys.getsizeof(g)
Out[20]: 120

In [21]: l = [2**n for n in range(1, 21)]

In [22]: g = (2**n for n in range(1, 21))

In [23]: sys.getsizeof(l)
Out[23]: 264

In [24]: sys.getsizeof(g)  # 生成器对象大小是固定的
Out[24]: 120

可以看到列表会随元素的增加而消耗更多内存，生成器的大小则保持不变，需要迭代海量数据时用生成器更合适。

以下是一段绘制曼德布罗分形图的程序：

"""xiter_mandelbrot.pyw 绘制曼德布罗分形图
"""
import tkinter as tk
import time


def mandelbrot_pixel(c):
    """返回曼德布罗平面像素点对应索引号
    """
    maxiter = 256
    z = complex(0.0, 0.0)
    for i in range(maxiter):
        z = z * z + c
        if abs(z) >= 2.0:
            return i
    return 256


def mandelbrot_image(xa, xb, ya, yb, x, y):
    """返回曼德布罗平面图像字符串
    """
    clr = ["#%02x%02x%02x" % (  # 索引号0-255对应不同颜色
            int(255 * ((i / 255) ** 8)) % 64 * 4,
            int(255 * ((i / 255) ** 8)) % 128 * 2,
            int(255 * ((i / 255) ** 8)) % 256) for i in range(255, -1, -1)]
    clr.append("#000000")  # 索引号256对应黑色
    # 计算复平面坐标对应的像素点
    xm = [xa + (xb - xa) * kx / x for kx in range(x)]
    ym = [ya + (yb - ya) * ky / y for ky in range(y)]
    # 生成图像字符串
    return " ".join((("{" + " ".join(clr[mandelbrot_pixel(complex(i, j))]
                    for i in xm)) + "}" for j in ym))


def main():
    """绘制曼德布罗分形图
    """
    # 复数取值范围
    xa = -2.25
    xb = 0.75
    ya = -1.25
    yb = 1.25
    # 显示窗口大小
    x = 600
    y = 500
    window = tk.Tk()
    canvas = tk.Canvas(window, width=x, height=y, bg="#000000")
    canvas.pack()
    t1 = time.process_time()
    img = tk.PhotoImage(width=x, height=y)
    canvas.create_image((0, 0), image=img, state="normal", anchor=tk.NW)
    # 计算并显示图像
    pixels = mandelbrot_image(xa, xb, ya, yb, x, y)
    img.put(pixels)
    print("运行耗时：{}秒。".format(time.process_time() - t1))
    tk.mainloop()


if __name__ == "__main__":
    main()

以上程序用到了复数类型、列表解析式和生成器解析式，并引入time模块来查看运行耗时，绘图区30万像素点的颜色需要逐一计算，每个点执行最多256次迭代，在我的i3-6100电脑上需要花费3秒钟……

15_mandelbrot.png

——编程原来是这样……

编程小提示：曼德布罗集合

“曼德布罗集合”（Mandelbrot Set）是在自平方变换 f_c(z) = z_n² + c 下不发散的复数值 c 的集合：对于复平面上的一点 c，从 z=0 开始对 f_c(z) 进行迭代：z_n+1 = z_n + c (n = 0, 1, 2, ...)。重复迭代步骤以确定结果是否收敛（例如迭代256次后复数绝对值即与原点的距离不大于2），这个收敛域就是曼德布罗集合——曼德布罗集合的主要部分包含在实部-2.25至0.75，虚部-1.25至1.25的复平面区域中。

曼德布罗集合是最令人着迷的分形图之一，很难想象如此简单的公式能产生如此复杂的图形，无论如何放大也无法穷尽其所包含的细节，更多介绍可参看维基百科 https://en.wikipedia.org/wiki/Mandelbrot_set