1. 迭代器

1.1. 什么是迭代器

• 迭代是Python最强大的功能之一，是访问集合元素的一种方式；
• 迭代器是一个可以记住遍历的位置的对象；
• 迭代器获基于 迭代协议 取值，背后是 __ iter __ 方法；

1.2. 迭代器如何使用

• 迭代器有两个基本的方法：iter() 和 next()；
• 迭代器对象从集合的第一个元素开始访问，直到所有的元素被访问完结束，迭代器只能往前不会后退；
• 字符串，列表或元组对象都可用于创建迭代器；
• 迭代器中没有更多的元素时，next() 动作会抛出 StopIteration 的错误；

>>> list=[1,2,3,4]
>>> it = iter(list)    # 创建迭代器对象
>>> print (next(it))   # 输出迭代器的下一个元素
1
>>> print (next(it))
2
>>> print (next(it))
3
>>> print (next(it))
4
>>>
>>> print (next(it))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration                                      # 迭代器中没有更多的元素时，next() 动作会抛出 **StopIteration** 的错误

• 与 list 序列不同，迭代器不能按位置下标返回；
  -- list 下标获取值，背后的原理是 __ getitem __，而迭代器获取值用到的 迭代协议，背后是 __ iter __ 方法。

2. 生成器函数

2.1. 什么是生成器

• 在 Python 中，一边循环一边计算的机制，称为生成器（Generator）；
• 生成器是一个返回迭代器的函数，只能用于迭代操作；
• 生成器可以通过生成器表达式和生成器函数获取到；
• 生成器是Python中的一个对象，对这个对象进行操作，可以依次生产出按生成器内部运算产生的数据；

2.2. 什么是生成器函数

• 只要函数里面有 yield 关键字，就是生成器函数，不再是普通函数；
• 生成器函数保存的是函数内部的算法，每次调用就通过算法计算出下一个元素的值，直到计算到最后一个元素；
• 生成器函数使用 next() 调用生成器函数的赋值对象（不是函数本身）返回 yiled 值；

注意：生成器函在被 next 调用之前，必须将生成器函数赋值于某个变量，next 调用的是被赋值后的变量，而不是函数本身，如：下面代码中的 result = fun_gen()，这一步一定不能省，next 调用的是 result，不是 fun_gen()；

>>> def fun_gen():
...     print("第一次 yield")
...     yield 1
...     print("第二次 yield")
...     yield 2
...     print("第三次 yield")
...     yield 3
...
>>> result = fun_gen()                # 注意：必须将生成器函数赋值于某个变量！！！
>>> next(result)                      # next 调用的是被赋值后的变量，而不是函数本身；
第一次 next
1
>>> next(result)                      # next 调用的是被赋值后的变量，而不是函数本身；
第二次 next
2
>>> next(result)                      # next 调用的是被赋值后的变量，而不是函数本身；
第三次 next
3

• 与迭代器一样，生成器中没有更多的元素时，next() 动作会抛出 StopIteration 的错误；

>>> def fun_gen():
...     print("第一次 yield")
...     yield 1
...     print("第二次 yield")
...     yield 2
...     print("第三次 yield")
...     yield 3
...
>>>
>>> result = fun_gen()
>>> next(result)
第一次 yield
1
>>> next(result)
第二次 yield
2
>>> next(result)
第三次 yield
3
>>> next(result)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration                          # 没有更多的元素，next() 动作抛出 StopIteration 的错误

• 实际使用生成器函数的时候，不必依次进行 next 调用，一般使用 for...in...，这样会更简洁、合理；

>>> def fun_gen():
...     print("第一次 yield")
...     yield 1
...     print("第二次 yield")
...     yield 2
...     print("第三次 yield")
...     yield 3
...
>>>
>>> for i in fun_gen():
...     print(i)
...
第一次 yield
1
第二次 yield
2
第三次 yield
3

2.3. 生成器函数 与 普通函数 的区别

• 生成器函数可以多次 yield 结果值，普通函数只能返回一次结果值；
• 生成器函数需要结果值的时候就直接生成一个，不需要直接占用很大的内存空间，而普通函数执行时需要足够的内存空间，尤其是需要生成元素很多的列表、巨大的数值的时候，需要占用巨大的内存空间；

3. 用生成器构造斐波那契数列

3.1. 斐波那契数列简介

-- 斐波那契数列，是有一系列整数组成的数列；
-- 这一数列任意位置上的数值与后一位相加，等于第三位数值；
-- 示例：

0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , ...

3.2. 普通方法构造斐波那契数列

• 构造方法一
  -- 如下面代码，使用递归构造斐波那契数列生成函数，并记录运行时间；

def feb_1(index):
    """
    斐波那契数列生成函数
    """
    if index <= 2:
        return 1
    elif index > 2 and index < 101:
        return feb_1(index-1) + feb_1(index-2)

def test_time(max_index):
    """
    测试上面 斐波那契数列函数的执行情况
    """
    starttime = datetime.datetime.now()  # 记录开始时间
    print("最大值为 ： {}\n结果值为：{}".format(max_index, feb_1(max_index)))
    endtime = datetime.datetime.now()  # 记录结束时间
    print("运行时间为：{}".format(endtime - starttime))  # 以秒为单位，计算运行时长

-- 方法缺陷：
（1）每次只能获取一个末位的数值，而不是整个数列；
（2）如果数值太大，运行时间会变得非常的长；

print(test_time(10))

print(test_time(20))

print(test_time(30))

print(test_time(40))

最大值为 ： 10
结果值为：55
运行时间为：0:00:00
None

最大值为 ： 20
结果值为：6765
运行时间为：0:00:00.003998
None

最大值为 ： 30
结果值为：832040
运行时间为：0:00:00.469920 
None

最大值为 ： 40
结果值为：102334155
运行时间为：0:00:57.805053       # 此处，max_index=40，运行时间就已经需要 57 秒，相比前面的时间花费增速是几何式的，
None

-- 如上面的例子，max_index = 30 的时候程序运行时常只需要 0:00:00.749871 秒，到了 max_index = 40 的时候就已经需要 0:00:57.805053 秒，这种耗时的增速在实际生产中是不能接受的；

• 构造方法二

def feb_2(max_index):
    """
    斐波那契数列生成函数
    """
    result_list = []          # 此处使用 list 作为一个容器存储生成的数值，如果数值足够大这个 list 将会占用大量的的内存
    n, a, b = 0, 0, 1
    while n < max_index:
        result_list.append(b)
        a,b = b, a+b
        n += 1
    return "最大值为 ： {}\n结果值为：{}".format(max_index, result_list)

def test_time(max_index):
    """
    测试上面 斐波那契数列函数的执行情况
    """
    starttime = datetime.datetime.now()  # 记录开始时间
    print(feb_2(max_index))
    endtime = datetime.datetime.now()  # 记录结束时间
    print("运行时间为 ： {}".format(endtime - starttime))  # 以秒为单位，计算运行时长

-- 该方法的优点：相比与前面的方法，程序运行耗费的时间相对较快；

test_time(10)

test_time(20)

test_time(30)

test_time(40)

最大值为 ： 10
结果值为：[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
运行时间为 ： 0:00:00.001000

最大值为 ： 20
结果值为：[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]
运行时间为 ： 0:00:00

最大值为 ： 30
结果值为：[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040]
运行时间为 ： 0:00:00

最大值为 ： 40
结果值为：[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155]
运行时间为 ： 0:00:00

-- 该方法的缺陷：该方法使用 result_list = [] 作为一个容器存储生成的数值，如果数值足够大这个 list 将会占用大量内存空间，简言之：如果数值过大，会占用大量内存；
-- 有兴趣的小伙伴可以尝试 max_index=10000 时程序的执行情况，看一看程序内存占用情况；
-- 请注意：你的电脑可能会被卡死！！！

test_time(10000)    # 注意：你的电脑可能会被卡死

3.3. 生成器构造斐波那契数列

• 如下面的代码：
  -- fib_3(max_index) 是用生成器函数构成的斐波那契数列生成函数；
  -- 在 test_time(max_index) 测试函数中使用 for i in fib_3(max_index) print(i) 打印所有的生成结果；

import datetime


def fib_3(max_index):
    """
    使用 yiled 生成器构造的斐波那契数列生成函数
    """
    n, a, b = 0, 0, 1
    while n < max_index:
        yield b                                                 # 此处使用 yiedl b 
        a,b = b, a+b
        n += 1


def test_time(max_index):
    """
    测试上面 斐波那契数列函数的执行情况
    """
    starttime = datetime.datetime.now() 
    for i in fib_3(max_index):                                   # 使用 for ... in ... 遍历打印所有的生成结果
        print(i)
    endtime = datetime.datetime.now() 
    print("运行时间为 ： {}".format(endtime - starttime))


test_time(10)        
test_time(100)
test_time(1000)
test_time(10000) 

• 运行耗时、内存占用都被大大缩减，下面的结果展示了运行时间结果，和前面的对比这种方法的效率是惊人的；

# 运行的时间如下所示：

运行时间为 ： 0:00:00
运行时间为 ： 0:00:00
运行时间为 ： 0:00:00.001000
运行时间为 ： 0:00:00.004998

3.4. 生成器函数构建杨辉三角

• 杨辉三角简介：
  -- 杨辉三角，是二项式系数在三角形中的一种几何排列，中国南宋数学家杨辉1261年所著的《详解九章算法》一书中出现；
  -- 在欧洲，帕斯卡在1654年发现这一规律，所以这个表又叫做[帕斯卡三角形；
  -- 杨辉三角示例如下图：

20190307104242486.png

• 杨辉三角特性：
  -- 每个数等于它上方两数之和；
  -- 每行数字左右对称，由1开始逐渐变大；
• 代码实现：

def triangles(max_index):        # max_index 表示最大行数
    L = [1]
    i = 1
    while i <= max_index:        # 进入持续循环
        yield L[:len(L)]         # 输出数组
        L.append(0)              # 为数组添加最后一位
        L = [L[j - 1] + L[j] for j in range(len(L))]
        i += 1

for i in triangles(10):          # 使用 for 循环打印结果值
    print(i)

• 运行结果

[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]
[1, 7, 21, 35, 35, 21, 7, 1]
[1, 8, 28, 56, 70, 56, 28, 8, 1]
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]