python 基础知识梳理——迭代器和生成器

引言

for i in [1,2,3,4,5,6]:
  print(i)

这是一个非常简单的for in语句，什么样的对象可以被用来迭代呢？

容器、可迭代对象、迭代器

在Python中一切皆是对象，对象的抽象就是类，而对象的集合就是容器。

列表list:[0,1,2]，元组tuple:(0,1,2)，字典dict:{0:0,1:1,2:2}，集合set:set{0,1,2}都是容器。容器可以想象成各个元素在一起的单元，不同容器的区别在于内部数据结构的实现方法，然后，针对不同的场景，可以选择适合的不同时间复杂度和空间复杂的的容器。

迭代器提供了一个next方法，调用这个方法后你就可以得到容器中的下一个对象，或者得到一个错误信息，Stopiteration，不需要像列表一样指定元素的索引，因为字典和集合这样的容器是无序的，没有索引这一说。之前的博文<python 基础知识梳理——字典和集合>中提到过，字典中底层实现采用哈希表，我们只需要知道next函数可以一个一个的拿到容器中的所有元素。

对于可迭代对象，通过iter()函数返回一个迭代器，再通过next()函数就可以实现遍历，for in也是这样的过程，只不过藏起来了。

通过Python内置的isinstance(obj,Iterable)可以判断一个对象是否可迭代。

def is_iterable(func):
    try:
        iter(func)
        return '可以'
    except Exception:
        return '不可以'

func = [
    1234,
    '1234',
    [1,2,3,4],
    (1,2,3,4),
    {1:1,2:2,3:3,4:4},
    {1,2,3,4},]
for fun in func:
    print('{} 是否可迭代\t\t {}'.format(fun,is_iterable(fun)))
# 输出
1234 是否可迭代		 不可以
1234 是否可迭代		 可以
[1, 2, 3, 4] 是否可迭代		 可以
(1, 2, 3, 4) 是否可迭代		 可以
{1: 1, 2: 2, 3: 3, 4: 4} 是否可迭代		 可以
{1, 2, 3, 4} 是否可迭代		 可以

通过这个例子可知，除了数字1234以外，都是可以迭代的对象。

生成器

生成器是简单版/轻量级的迭代器

例如这样一个迭代器[i for i in range(1000000)]就可以生成一个包含100万个数字的列表，但是每个元素生成后都会存储在内存中，然而当内存不足时，就会出现OOM(OutOfMemeryError)错误。

当我们不需要迭代器一次性生成那么多数据的时候，生成器的作用就显现出来了。只有当你在调用next()函数的时候，才会生成下一个变量。Python中使用(i for i in range(10000000))来初始化一个生成器。

生成器并不会像一个迭代器一样占用大量的内存，只会在被使用的时候才会调用，生成器在初始化的时候并不需要运行一次生成的操作，所以内存占用会大大少于迭代器。

自定义生成器

例1：恒等式

数学中，有一个恒等式(1+2+3+···+n)^2 = 1^3 + 2^3 + 3^3+···+n^3，现在我们使用生成器来实现这个公式。

def generator(num):
    i = 1
    while True:
        yield i ** num
        i += 1

gen_1 = generator(1)
gen_3 = generator(3)

def get_sum(n):
    sum1 , sum2 = 0, 0
    for i in range(n):
        num_n = next(gen_1)
        result = next(gen_3)
        print('num_n = {},result = {}'.format(num_n,result))
        sum1 += num_n
        sum2 += result

get_sum(10)
# 输出
num_n = 1,result = 1
num_n = 2,result = 8
num_n = 3,result = 27
num_n = 4,result = 64
num_n = 5,result = 125
num_n = 6,result = 216
num_n = 7,result = 343
num_n = 8,result = 512
num_n = 9,result = 729
num_n = 10,result = 1000

这段代码中的generator()函数中的yield关键字，其实是一种魔术方法，这个函数的返回值其实是一个生成器，当函数运行到这部分的时候，就会暂停跳出，当next(gen_)函数被调用的时候，函数就会从yield后继续执行，局部变量的值并不会保持是1，而是会在1的基础上自增1，从结果看num_n从1变到10，result从1变到1000。

例2：求list中数的位置

给定一个list，求这个数字在list中的位置

传统方法

L = [1, 6, 2, 4, 5, 2, 3, 4, 6, 3, 3]
def find_element(list,target):
    result = []
    for location, num in enumerate(list):
        if num == target:
            result.append(location)
    return result

result = find_element(L,3)
print(result)
# 输出
[6, 9, 10]

传统方法中，我们通过库函数enumerate()来返回函数的索引并添加到列表中

迭代器

L = [1, 6, 2, 4, 5, 2, 3, 4, 6, 3, 3]
def find_element_use_generator(list,target):
    for location, num in enumerate(list):
        if num == target:
            yield location

result = find_element_use_generator(L,3)
print(list(result))
# 输出
[6, 9, 10]

区别很明显，但是yield的返回值是一个Generator对象，需要用list转换为列表后，才能输出。

例3：判断子序列

给定两个序列，判断第一个序列是不是第二个序列的子序列。

针对这个问题：常规的算法时贪心算法，维护两个指针，从列表最开始，然后针对第二个序列扫描过去，如果第一个数字和第一个指针一样，那么就把第一个指针前进一步，第一个指针溢出第一个序列最后一个元素的时候，返回True，否则返回False。

下面，我们尝试用迭代器和生成器完成这个算法。

def is_subsequence(list_a,list_b):
    list_b = iter(list_b)
    return all(i in list_b for i in list_a)

print(is_subsequence([1,2,4],[1,2,3,4,5]))
print(is_subsequence([1,4,3],[1,2,3,4,5]))
# 输出
True
False

思路：

iter(list_b)的目的是将list_b装换为一个迭代器
for i in list_a是一个生成器，用来遍历对象a
当遍历对象a时的i也存在于b中时，给定的i是否也存在于b中

非常巧妙的是，利用了生成器的特性，next()函数运行时，保存了当前的指针，如下列：

b = (i for i in range(5))

print(2 in b)
print(4 in b)
print(3 in b)
# 输出
True
True
False

很显然，当保存了指针后，print(3 in b)显然为False了。

总结

xxx

本文中共提到了四种不同的结构：①容器、②可迭代对象、③迭代器、④生成器

容器是可迭代对象，可迭代对象可以用iter()函数得到一个迭代器，迭代器可以通过next()函数来获取下一个元素，从而支持遍历
生成器是一种特殊的迭代器，它是一种轻量级/简单版的迭代器，用生成器可以使代码更加清晰，降低内存占用、优化程序结构、提高程序运行速度
生成器是Python2版本中的一种协程的重要实现方式，而Python3.5之后，引入新的asyncawit语法糖，生成器实现协程已经比较落后了。

Q.E.D.

星尘博客