yield与递归

2017-01-13 10:57:30来源:csdn作者:neuldp人点击

第七城市

递归中使用yield
yield中递归返回
目的
实现思想
具体代码实现

1 递归中使用yield

注意 递归算法中若要使用生成器,需要在生成器的原函数(首次调用)显式得到所有yield值 具体如下

def quick_sort(parameter_list):if len(parameter_list) == 0:
# print("error")
return
if len(parameter_list) == 1:
# print(parameter_list[0])
yield parameter_list[0]if parameter_list[0] < parameter_list[-1]:
pivot = parameter_list[0]
left = [i for i in parameter_list if i < pivot]
right = [i for i in parameter_list if i > pivot]
for item in quick_sort(left):
yield item
# quick_sort(left)#recursion in Generator are limited
yield pivot
# quick_sort(right)
for item in quick_sort(right):
yield item2 yield中递归返回

https://github.com/Earthson/RecGen

当我们持有一个generator之后,我们可以做什么呢?

我们可以获得它的输出,并且给它传值。这里,隐含了一种特殊的模式,generator输出任务,而我们传入任务的执行结果。这个过程看起来就像一次函数调用一样:)

这里最关键的一点是,我们持有了任务的处理过程,而generator并不关心任务是如何被处理的。实际上,我们可以直接执行,或者丢给异步引擎,或者丢到线程池,或者干脆提交到远程机器上执行。我们把这个分配任务的部分叫做调度器吧:)

递归

如果generator生成的任务本身也是generator呢?我们应当如何让generator完成递归呢?

如何返回值?

其实我们直接用yield返回值即可。但是我们需要把任务和值区分开来,因为python并没有提供什么有效的方式能把这两者分离。所以我们通过yield出的值的类型判断即可,我们可以定义一个接口,所有持有某个方法的对象都是任务。

调度器的困境

这里有一个重要的问题是,也就是generator的下一次操作,取决于任务是否完成。而这个操作是由任务决定的,调度器无法做到这一点。这导致一个问题,调度器不能直接控制generator的执行,它需要把控制的操作下传给任务,让任务在结束后自动完成这个操作。只有这样,调度器才不需要独立的线程或者额外的方式进行控制,因为它的触发是被动的。

目的

实现如下功能计算斐波那契数列

def fib(n):
if n <= 1:
yield n
else:
yield (yield RecTask(fib, n-1)) + (yield RecTask(fib, n-2))pfib = rec_gen(fib, lambda x: print(x))
for i in range(15):
pfib(i)实现思想

执行任务


任务的执行需要接受一个callback和一个error_callback函数,当任务完成的时候,它执callback,出现错误则执行error_callback。


我们需要把对于generator的控制封装到一个callback中,使得任务可以调用这个函数,完成它的功能。我们可以把重试的函数作为error_callback传入任务,这使得任务在失败之后可以被重试。

下面是一个实现。包含了如下的一些特性。

调度器可以作为装饰器使用(如果忽略错误和返回值)
对于正常的函数,它能够直接返回结果(传递给callback)
对于普通的generator输出,它能把generator的输出作为参数传递给callback
所有的任务对象都包含一个dojob方法,它接受callback和err_callback,用于完成任务
任务包含了重试机制,当任务失败次数达到限额之后,整个任务会直接失败(整个递归过程)

RecTask任务

默认的RecTask类型,是常规的python函数调用,包含函数和它的参数。
RecTask方法包含一个transform方法,用于对任务函数进行变换(完全是一个约定)。这个方法不会修改原始的任务函数,因为一个可变对象在重复调用的过程中会出现难以预计的问题。
RecTask的run方法,用于接受新的任务函数(如果是None则直接执行原始的函数)
通过继承RecTask,可以构造其它的任务执行方式。比如通过异步引擎来执行任务。这也使得异步架构能够完成一些递归任务:)
具体代码实现
import sys
import types
from traceback import format_excdef rec_gen(func, callback=None, err_callback=None):
'''
callback accept arguments with output of func
err_callback is called after Exception occured, accept Exception instance as it's arguments
'''
def trans_func(*args, **kwargs):
def error_do(e):
print('@rec_func_error:', e, file=sys.stderr)
if err_callback is not None:
err_callback(e)
try:
g = func(*args, **kwargs)
except Exception as e:
error_do(e)
return
if not isinstance(g, types.GeneratorType):
#return if g is not generator
if callback is not None:
callback(g)
return
#ans = []
def go_through(it=None):
try:
em = g.send(it)
if not hasattr(em, 'dojob'):
#ans.append(em)
go_through(None)
else:
em.dojob(callback=go_through, err_callback=error_do)
except StopIteration as st:
if callback is not None:
callback(st.value)
return
except Exception as e:
g.close()
error_do(e)
return
go_through()
return trans_func
from functools import partial
class RecTask(object):
def __init__(self, func, *args, **kwargs):
self.func = func
self.args = args
self.kwargs = kwargsdef dojob(self, callback=None, err_callback=None):
self.run(self.transform(partial(rec_gen, callback=callback, err_callback=err_callback)))def transform(self, f):
return f(self.func)def run(self, func=None):
if func is None:
func = self.func
return func(*self.args, **self.kwargs)
class TaskWithRetry(RecTask):retry_limit = 1def dojob(self, callback=None, err_callback=None):
try_cnt = 0
def ierr(e, *args, **kwargs):
nonlocal try_cnt
if not hasattr(self, 'retry_limit') or try_cnt > self.retry_limit:
print('@error: overflow retry limit! task has complete failed', file=sys.stderr)
if err_callback is not None:
return err_callback(e, *args, **kwargs)
return
try_cnt += 1
print('@warning_retry: retry count: %s, %s' % (try_cnt, e), file=sys.stderr)
self.run(self.transform(partial(rec_gen, callback=callback, err_callback=ierr)))
self.run(self.transform(partial(rec_gen, callback=callback, err_callback=ierr)))
class MapTask(object):
def __init__(self, *tasks):
self.tasks = list(tasks)def dojob(self, callback=None, err_callback=None):
self.ans = [None for e in self.tasks]
self.flags = [False for e in self.tasks]
self.cnt = len(self.tasks)
self.todo = callback
self.apply_tasks(err_callback=err_callback)def apply_tasks(self, err_callback):
for i, e in zip(range(len(self.tasks)), self.tasks):
e.dojob(callback=self.acker(i), err_callback=err_callback)def acker(self, posi):
def ack(x):
if self.flags[posi] is False:
self.flags[posi] = True
self.ans[posi] = x
self.cnt -= 1
if self.cnt == 0:
if self.todo is not None:
self.todo(tuple(self.ans))
return ack
class HTTPTask(TaskWithRetry):
def __init__(self, sender, req, callback):
self.sender = sender
self.req = req
self.callback = callback
self.retry_limit = 10def transform(self, f):
return f(self.callback)def run(self, callback=None):
if callback is None:
callback = self.callback
self.sender(self.req, callback)
if __name__ == '__main__':
sys.setrecursionlimit(1000000000)
def fib(n):
if n <= 1:
return n
return (yield RecTask(fib, n-1)) + (yield RecTask(fib, n-2))
#x, y = yield MapTask(RecTask(fib, n-1), RecTask(fib, n-2))
#return x + y
pfib = rec_gen(fib, lambda x: print(x))
pfib(25)
第七城市

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台