Python 生成器与回调函数

Question

我有一个类，用递归和回溯算法来解决精确覆盖问题。最开始，我在初始化这个类的时候传入了一个回调函数，这个函数会在找到解决方案时被调用。后来我看到别人用yield语句来传出解决方案，也就是说，他们的代码是一个Python生成器。我觉得这个主意挺有意思的，于是我也做了一个新的版本，使用了yield。然后我对这两个版本进行了比较测试，结果让我很惊讶，生成器版本的运行速度比回调版本慢了5倍。需要注意的是，除了把回调换成yield，代码是完全一样的。

这是怎么回事呢？我猜测，生成器在使用yield时需要保存状态信息，然后在下一次调用时再恢复这些状态，这个保存和恢复的过程可能导致生成器版本的运行速度变慢。如果真是这样，生成器需要保存和恢复多少状态信息呢？

有没有Python专家能给点建议？

--编辑于7:40 PDT

这是使用yield的求解代码。把下面的第一个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的单次调用。

Answer 1

我在评论中提到的意思是（“从递归函数中返回值听起来需要额外的循环来把结果传递给调用者”），就是这一行：

          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（见这一段）。在此之前，我认为从递归函数中返回值并不是个好主意（至少在递归层数很深的时候），它们并不太适合一起使用。