我有一个类,使用递归回溯算法解决精确覆盖问题。最初,我在初始化期间向对象传递了回调函数来实现该类。每当找到解决方案时,都会调用此回调。在查看其他人对同一问题的实现时,我发现他们正在使用yield语句传递解决方案,换句话说,他们的代码是一个Python生成器。我认为这是一个有趣的想法,所以我制作了一个新版本的类来使用yield。然后我运行了两个版本之间的比较测试,并惊讶地发现生成器版本比回调版本慢5倍。请注意,除了将回调替换为yield之外,代码完全相同。
这里发生了什么?我猜测,因为生成器需要在yield之前保存状态信息,然后在下一次调用时恢复该状态,因此正是这种保存/恢复使生成器版本运行得如此缓慢。如果是这样,生成器需要保存和恢复多少状态信息?
有没有Python专家有什么想法?
-编辑7:40 PDT
以下是使用yield的求解器代码。请将下面的第一个yield替换为对回调函数的调用,并将以下循环更改为原始代码的递归调用。
调用求解器的邮件循环(当然,在初始化之后)是:
在回调版本中,只需要一次调用solve,循环就被去掉了。
这里发生了什么?我猜测,因为生成器需要在yield之前保存状态信息,然后在下一次调用时恢复该状态,因此正是这种保存/恢复使生成器版本运行得如此缓慢。如果是这样,生成器需要保存和恢复多少状态信息?
有没有Python专家有什么想法?
-编辑7:40 PDT
以下是使用yield的求解器代码。请将下面的第一个yield替换为对回调函数的调用,并将以下循环更改为原始代码的递归调用。
def solve(self):
for tp in self.pieces:
if self.inuse[tp.name]: continue
self.inuse[tp.name] = True
while tp.next_orientation() is not None:
if tp.insert_piece():
self.n_trials += 1
self.pieces_in += 1
self.free_cells -= tp.size
if self.pieces_in == len(self.pieces) or self.free_cells == 0:
self.solutions += 1
self.haveSolution = True
yield True
self.haveSolution = False
else:
self.table.next_base_square()
for tf in self.solve():
yield tf
tp.remove_piece()
self.pieces_in -= 1
self.table.set_base_square(tp.base_square)
self.free_cells += tp.size
self.inuse[tp.name] = False
tp.reset_orientation()
调用求解器的邮件循环(当然,在初始化之后)是:
start_time = time.time()
for tf in s.solve():
printit(s)
end_time = time.time()
delta_time = end_time - start_time
在回调版本中,只需要一次调用solve,循环就被去掉了。
yield
看起来需要额外的for
循环将结果传递给调用者,是这样吗?也许你的意思是使用协程,通过send
传递结果? - Jochen Ritzeltimeit
(它不像其他程序那样脆弱,因为它运行多次并采取一些对抗其他程序占用大部分CPU时间的措施)。也许按行进行分析也有所帮助。 - user395760