Генератор Python против функции обратного вызова

Question

У меня есть класс, который решает точную проблему покрытия, используя рекурсивный алгоритм обратного отслеживания. Первоначально я реализовал класс с функцией обратного вызова, которую передал объекту во время инициализации. Этот обратный вызов вызывается всякий раз, когда найдено решение. Рассматривая чью-либо реализацию той же проблемы, я увидел, что они использовали операторы yield для передачи решения, иными словами, их код был генератором Python. Я подумал, что это интересная идея, поэтому я сделал новую версию своего класса, чтобы использовать выходы. Затем я провел сравнительные тесты между двумя версиями и, к своему удивлению, обнаружил, что версия генератора работала в 5 раз медленнее, чем версия с обратным вызовом. Обратите внимание, что за исключением переключения доходности для обратного вызова, код идентичен.

Что здесь происходит? Я предполагаю, что поскольку генератору необходимо сохранить информацию о состоянии перед выдачей, а затем восстановить это состояние при перезапуске при следующем вызове, именно это сохранение / восстановление и делает версию генератора намного медленнее. Если это так, то сколько информации о состоянии требуется генератору сохранить и восстановить?

Есть идеи от экспертов по питону?

- отредактировано 7:40 PDT

Вот код решателя, который использует 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 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 может исправить это (см. этот параграф ).Между тем я не думаю, что это хорошая идея - извлекать пользу из рекурсивных функций (по крайней мере, если они глубоко рекурсируют), они просто не очень хорошо работают вместе.