关于pyhton的yield, 生成器与尾调用

前言

什么时候可以认真看过一遍SICP啊 (:3」∠)

以下单纯的作为学习笔记

迭代器

好像没什么徒手撸一个迭代器的机会所以留意一下Python的for循环本质上就是通过不断调用next()函数实现。next()方法返回容器的下一个元素，在结尾时引发StopIteration异常

1
2
3
4
5
6
7
8
9
10
# 首先获得Iterator对象:
it = iter([1, 2, 3, 4, 5])
# 循环:
while True:
    try:
        # 获得下一个值:
        print(next(it))
    except StopIteration:
        # 遇到StopIteration就退出循环
        break

yield的用法

1
2
3
4
5
6
7
8
9
10
11
12
def fab():
    a = 0
    b = 1
    while True:
        yield b
        a, b = b, a+b
        
a = fab()
a.__next__() #1
a.__next__() #1
a.__next__() #2
a.__next__() #3

上面生成了一个可返回无限长度的生成器函数（语言不太精确但大概就是这个意思），用python3的next()方法可以不断返回下一个值。

这里再贴一下itertools里面islice()的用法

islice()的设定是

Make an iterator that returns selected elements from the iterable.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def islice(iterable, *args):
    # islice('ABCDEFG', 2) --> A B
    # islice('ABCDEFG', 2, 4) --> C D
    # islice('ABCDEFG', 2, None) --> C D E F G
    # islice('ABCDEFG', 0, None, 2) --> A C E G
    s = slice(*args)
    it = iter(range(s.start or 0, s.stop or sys.maxsize, s.step or 1))
    try:
        nexti = next(it) #得到第一个序号
    except StopIteration:
        return
    for i, element in enumerate(iterable):
        if i == nexti:
            yield element
            nexti = next(it)

实际用起来就是

1
2
for i in islice(fab(),3,9):
    print(i)

尾调用

尾调用就是在return一个函数以后没有新的运算，堆栈直接把原来的函数pop掉，push新的函数，可以用来防爆栈。实际操作就是把变化的参数传递给递归函数的变量。

1
2
3
4
def sum(n, total = 0):
    if n == 0:
        return total
    return sum(n - 1, total+n)

然而python不支持尾调用orz

sys.getrecursionlimit()查看最大递归深度，sys.setrecursionlimit()可以设置。

说好的1000爆栈怎么sum(971)就爆了，最后可以的是sum(970)，微妙。

可以用reference里面的菊苣的代码实现真*尾调用不爆栈。

Tips: c/cpp有优化所以会说是tail_call_optimize, python3可以用装饰器实现尾调用（默认栈深度1000且没有尾调用）但是没有优化，单纯的防爆栈。

Update

看到一个新的写法, 以下引用:

1
2
3
4
5
6
7
def fib(count, cur=0, next_=1):
    if count <= 1:
        yield cur
    else:
        # Notice that this is the tail-recursive version
        # of fib.
        yield fib(count-1, next_, cur + next_)

那我们怎么办呢，这里我们使用的技术称为Trampline,我们用一个方法让它不断执行生成器的next(),达到我们的目的。

1
2
3
4
5
6
7
8
import types
def tramp(gen, *args, **kwargs):
    g = gen(*args, **kwargs)
    while isinstance(g, types.GeneratorType):
        g=g.__next__()
    return g
print tramp(fib, 996)

fib的返回也是一个生成器，所以要算fib的第1000项的话，相当于把这些生成器都跑一遍(生成器里返回生成器感觉好奇妙）。

用ipython的%timeit比了一下，之前的方法输惨了啊（瓶颈在exception捕获？）

1
2
3
4
5
%timeit -n 1000 tramp(fib1, 1000)
1000 loops, best of 3: 817 µs per loop
%timeit -n 1000 fib(1000)
1000 loops, best of 3: 2.78 ms per loop

总之超帅的

Reference：

两篇写的都real棒