本文介绍了 python 的生成器,构造一些有趣的惰性计算程序,可以作为 python 函数式的基础。
1. iterator and generator
众所周知,python3 里面的 range 返回是一个对象而不是列表,它的前身是 python 2 的 xrange。python 2 里面的 range 会生成一个列表,当这个列表很大时,会有严重的性能问题:
for x in range(0,100000):print(x)
可以使用iter(range(0,100000))将 range 对象转换为可迭代实例(iterator),下面的代码是和上面代码等价的:
lst=iter(range(0,10))while True:try:b = next(lst) print(b)except StopIteration:break
显而易见,其实 python 的 for 循环其实是个语法糖,首先隐式将list(可迭代对象)转换为list_iterator,然后不断调用迭代器的__next__函数,直到出现StopIteration为止;下面是一个迭代器的实例(注意内部函数__next__):
class :'''To use this class like thisfor n in fibonacci(100):print(n, end=',')'''def __init__(self, max):self.max = max#可迭代对象实现了__iter__方法,str、list、set、dict、file、sockets等容器都有这个内部函数def __iter__(self):self.a = 1self.b = 1return selfdef __next__(self):fib = self.aif fib > self.max:raise StopIterationself.a, self.b = self.b, self.a + self.breturn fib
使用也很简单,首先生成一个迭代器对象,然后调用next函数就可以了,我们这里使用enumerate函数生成组合迭代器返回索引和内部迭代器返回值 (类似的 api 还有 zip、reversed):
fib = fibonacci(20)print(next(fib))# more next(fib)...for i,n in enumerate(fibonacci(20)): # 不能重复使用fib对象!print('fib[', i, ']=', n, end='n')
根据 python doc 的描述,迭代器内部是有状态的,每次取一个值都会消耗迭代器的状态。需要注意的是 range 并不是一个迭代器,因此可以重复使用,其长度并不会因为遍历过而变化。因此并重复使用一个 range 对象是安全的,而上面的 fib 对象并不能重复从 fib(0) 计算。
另一个普遍使用产生迭代器的方法是生成器(generator),即使用yield返回值;还有少见的生成器表达式也能构造生成器:
def FibonacciIter(n):a, b, c = 1, 1, nwhile c > -1:yield aa, b, c = b, a + b, c - 1# a is a <class 'generator'>a = (x*x for x in range(10))
上面的 fibonacci generator 和迭代器对象 (iterable) 使用方法一样,都可以使用 next 取出下个返回值,当生成n个 fibonacci 数后,会耗尽并返回。
fib_gen = FibonacciIter(6)b = 0while 1:try:b = next(fib_gen)except StopIteration:breakprint(b, end=' ')
除了使用 for 循环取值,还可以使用生成器构造 list,或使用map、filter、reduce等函数进行计算:
# 使用generator构造listlist(FibonacciIter(6)) # [1, 1, 2, 3, 5, 8, 13]a = FibonacciIter(6)print(list(map(lambda x: x**2, a))) # [1, 1, 4, 9, 25, 64, 169]
为了验证生成器是惰性的,我们使用一个筛法生成素数数列:
# 奇数生成器def _odd_iter():n = 1while True:n = n + 2yield n# 整除def _not_divisible(n):return lambda x: x % n != 0# a generator for prime numberdef PrimesIter():#素数不包括1,从2开始yield 2it = _odd_iter()while True:n = next(it)yield nit = filter(_not_divisible(n), it)
代码参考:/wiki/1016959663602400/1017404530360000
生成器 PrimesIter 首次返回 2(2 是特殊素数,其他素数全为奇数),然后在奇数生成器的基础上进行过滤运算 (筛法):首先奇数生成器返回 3, 这个是素数,yield n处返回,it 看做一个惰性数列 (现在是 3 之后的奇数),使用filter函数将这个数列里面所有被 3 整除的奇数全部过滤掉,并返回一个迭代器重新赋值给 it,里面包含所有素数。继续下次循环会过滤掉所有 5 整除的奇数…实际上这个 it 会被重复包裹成…filter(__not_divisible(5), filter(__not_divisible(3),it),while 每循环一次,就多加一层 filter。
2. itertools and basical usage
无限生成器可以永久运行下去,很容易造成死循环,幸好 python 库提供了 itertools 用于处理这些情况, 我们参考 python doc 编写了一些使用的 itertools 扩展 api:
from itertools import islice,takewhile# get first n elements from iter,#take(itertools.count(1,2), 5) will get [1,3,5,7,9]def take(iter, n):return list(islice(iter, n))# takeWhile elements {x} from iter, until f(x) is false# iter should be a infinate generatordef takeWhile(iter, f):return list(takewhile(f, iter))# return a list contains prime numbersdef takePrimesBy(flt):return takeWhile(PrimesIter(), flt)def isPrime(n):for i in takePrimesBy(lambda x: x < math.sqrt(n)):if n % i == 0:return Falsereturn True# generate N primes.def takePrimes(N):return take(PrimesIter(), N)# generate prime less then N.def getPrimes(N):return takePrimesBy(lambda x: x < N)
有了素数生成器,很容易构造一个正整数分解生成器(参考我写的 fold/unfold 文章):
# decompose N into Mult{x_i}, x_i is primedef DecomposeIter(N):c = Nwhile True:p = takePrimesBy(lambda x: x <= math.sqrt(c))s = [x for x in p if c % x == 0] # 取出所有可能的素因子if len(s) < 1:yield c # c是素数breakelse:c = int(c / s[0]) # 第一个素因子s[0]yield s[0]
验证方法是使用 list 取出生成器的值:
print(list(DecomposeIter(123))) # [3, 41]
3 container and iterators
除了 list,其他所有容器 set/dict 都能使用 for 循环遍历,即说明这些容器是可迭代的 (iterable),另外字符串、文件、socket 等容器也是可以生成迭代器的。除了使用 for 循环遍历容器/迭代器,我们还可以使用迭代器/生成器构造容器,第 2 节里面已经出现很多使用 list 读取生成器内容的用法,当然也可以用结合 enumerate 生成 dict:
iter = PrimesIter()dict(enumerate(islice(iter, 10))) #{0: 2, 1: 3, 2: 5, 3: 7, 4: 11, 5: 13, 6: 17, 7: 19, 8: 23, 9: 29}# get first 10 fibonacci numberimport profilea = range(0,10)profile.run('list(zip(a,PrimesIter()))')
我们在使用 filter/map/reduce 等函数将容器进行转换时,实际上可看做是对容器的迭代器进行操作(注意他们并不直接返回结果,而是返回另一个迭代器!),比较接近于 FP 风格。
原文链接:/mightbe/topics/1458578