Python生成器 vs 回调函数

Question

Python生成器 vs 回调函数

8

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

这里发生了什么？我猜测，因为生成器需要在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，循环就被去掉了。

- sizzzzlerz

1

请提供一个（简化但完整的）示例以及您如何测量时间。 - user395760

1

从递归函数中使用 yield 看起来需要额外的 for 循环将结果传递给调用者，是这样吗？也许你的意思是使用协程，通过 send 传递结果？ - Jochen Ritzel

通常会找到多少个解？（您是经常产生很多解还是相对较少？） - FogleBird

就记录而言，我的两个小测试（http://www.ideone.com/7XCro，http://www.ideone.com/VuKRn，http://www.ideone.com/DhTJF）似乎表明yield和回调之间的性能差异很小，而回调在执行更多工作时会慢慢改进。我迫不及待地想看到OP的反例。 - user395760

我添加了生成器版本代码的相关代码。我还展示了主函数如何调用求解器以及我如何计时。关于FogleBirds的问题，两个版本找到的解集完全相同，对于给定的问题是正确的。 - sizzzzlerz

好的，我仍然无法复现。我写了一个重度递归版本的之前的基准测试，但回调/生成器性能有很大不同。我建议您使用timeit（它不像其他程序那样脆弱，因为它运行多次并采取一些对抗其他程序占用大部分CPU时间的措施）。也许按行进行分析也有所帮助。 - user395760

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jochen Ritzel · Accepted Answer

我在评论中所指的是这句话：“从递归函数中产生结果似乎需要额外的循环来将结果传递给调用者”。

          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的优化实现可以解决这个问题（请参见this paragraph）。同时，我认为不应该从递归函数中使用yield（至少如果它们深度递归），它们并不搭配得很好。