Python：理解迭代器、生成器，并用生成器构建斐波那契数列和杨
2020-07-26 本文已影响0人
dex0423
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]
