Python 生成器与回调函数

Question

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

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

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

在回调版本中，只需一次调用即可解决该循环。

Answer 1

我在评论中的意思是（“从递归函数中产生听起来需要额外的 for 循环才能将结果传递给调用者”）是这一行：

          for tf in self.solve():
             yield tf

这些行递归地循环更深层递归阶段的结果。这意味着在递归的每个级别上都会迭代单个结果，从而导致大量不必要的循环。

让我用这个例子来说明：

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 个项目，等等在。

你拥有的项目越多，Python 在这些简单的代码上花费的时间就越多。回调完全避免了这个问题，所以我怀疑这是你的代码的问题。

PEP 380 的优化实现可以解决此问题（请参阅本段）。与此同时，我认为从递归函数中产生结果并不是一个好主意（至少如果它们深度递归的话），它们只是不能很好地协同工作。