Python生成器与回调函数 [英] Python generator vs callback function

问题描述

我有一个使用递归回溯算法解决确切的掩护问题的类.最初，我使用在初始化期间传递给对象的回调函数来实现该类.找到解决方案时将调用此回调.在查看其他人对同一问题的实现时，我看到他们正在使用yield语句来传递解决方案，换句话说，他们的代码是python生成器.我以为这是一个有趣的主意，因此我制作了班级的新版本以使用yields.然后，我在两个版本之间进行了比较测试，令我惊讶的是，我发现生成器版本的运行速度比回调版本慢5倍.请注意，除了为回调切换收益率外，代码是相同的.

I have a class that solves an exact cover problem using a recursive, backtracking algorithm. Originally, I implemented the class with a callback function I passed to the object during initialization. This callback is invoked whenever a solution is found. In looking at someone else's implementation of the same problem, I saw that they were using yield statements to pass a solution out, in other words, their code was a python generator. I thought this was an interesting idea so I made a new version of my class to use yields. I then ran comparison tests between the two versions and, to my surprise, I found the generator version ran 5 times slower than the callback version. Note that, except for switching in a yield for a callback, the code is identical.

这是怎么回事?我正在推测，因为生成器需要在屈服之前保存状态信息，然后在下一次调用时重新启动时恢复该状态，所以正是这种保存/恢复才使生成器版本运行得慢得多.如果是这种情况，生成器必须保存和还原多少状态信息?

What is going on here? I'm speculating that, because a generator needs to save state information before yielding and then restore that state when restarting at the next call, it is this save/restore that is what makes the generator version run so much slower. If this is the case, how much state information is the generator having to save and restore?

Python专家有什么想法吗?

Any ideas from the python experts?

-太平洋夏令时间7:40编辑

--Edited 7:40 PDT

这是使用yield的求解器代码.将下面的第一个yield替换为对回调函数的调用，然后将第二个yield的以下循环更改为仅递归调用，以解决此代码的原始版本.

Here is the solver code which uses yield. Replace the first yield below with a call to the callback function and change the following loop with the second yield to just a recursive call to solve for the original version of this code.

   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()

(当然，在初始化之后)调用求解器的邮件循环为

The mail loop which invokes the solver (after initialization, of course) is

   start_time = time.time()
   for tf in s.solve():
      printit(s)

   end_time = time.time()
   delta_time = end_time - start_time

在回调版本中，循环只需一个调用即可解决.

In the callback version, the loop is gone with just a single call to solve.

推荐答案

我在我的注释中的意思是(从递归函数中获得的声音听起来像是需要额外的for循环才能将结果传递给调用者")行:

What i meant in my comment, ("yielding from a recursive function sounds like it requires extra for loops to pass the results down to the caller") is this line:

          for tf in self.solve():
             yield tf

这些行以递归方式遍历更深层递归阶段的结果.这意味着在递归的每个级别上迭代一个结果，导致很多不必要的循环.

These lines recursively loop over the results from the deeper recursion stages. That means that a single result is iterated over on each level of the recursion, resulting in a lot of unnecessary looping.

让我用这个例子来说明:

Let me illustrate with this example:

n = 0
def rekurse(z):
    global n
    if z:
        yield z
        for x in rekurse(z-1):
            n += 1
            yield x

print list(rekurse(10))
print n

如您所见，它只是从10开始递减计数，因此您希望得到线性的迭代次数.但是，您看到的是n呈平方增长-recurse(10)遍历9个项目，recurse(9)遍历8个项目，依此类推.

As you can see this simply counts down from 10, so you'd expect a a linear number of iterations. What you can see though is that n grows quadratically - recurse(10) loops over 9 items, recurse(9) over 8 items and so on.

您拥有的项目越多，Python在这些简单的行上花费的时间就越多.回调完全避免了该问题，因此我怀疑这是您的代码存在的问题.

The more items you have, the more time Python spends on these simple lines. Callbacks completely avoid that problem, so I'd suspect that is the problem with your code.

PEP 380 的优化实现可以解决此问题(请参见本段).同时，我认为从递归函数中产生收益不是一个好主意(至少如果它们进行深度递归)，它们只是不能很好地协同工作.

A optimized implementation of PEP 380 could fix this (see this paragraph). In the meantime I don't think it's a good idea to yield from recursive functions (at least if they recurse deeply), they just don't work well together.

这篇关于Python生成器与回调函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！