Генератор Python против функции обратного вызова
У меня есть класс, который решает проблему с точной оболочкой, используя рекурсивный алгоритм обратного отслеживания. Первоначально я реализовал класс с функцией обратного вызова, которую я передал объекту во время инициализации. Этот обратный вызов вызывается всякий раз, когда найдено решение. Если посмотреть на чужую реализацию одной и той же проблемы, я увидел, что они использовали инструкции yield для принятия решения, другими словами, их код был генератором питона. Я думал, что это интересная идея, поэтому я сделал новую версию своего класса для использования доходностей. Затем я провел сравнительные тесты между двумя версиями, и, к моему удивлению, я обнаружил, что версия генератора работает в 5 раз медленнее, чем версия обратного вызова. Обратите внимание, что, за исключением переключения с выходом для обратного вызова, код идентичен.
Что здесь происходит? Я предполагаю, что, поскольку генератор должен сохранять информацию о состоянии перед уступкой, а затем восстанавливать это состояние при перезапуске при следующем вызове, именно это сохранение / восстановление приводит к тому, что версия генератора работает намного медленнее. Если это так, то сколько информации о состоянии требуется генератору для сохранения и восстановления?
Любые идеи от экспертов python?
–Edited 7:40 PDT
Вот код решателя, который использует выход. Замените первый выход ниже вызовом функции обратного вызова и измените следующий цикл со вторым выходом только на рекурсивный вызов, чтобы решить исходную версию этого кода.
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
В версии обратного вызова цикл исчезает с помощью только одного вызова для решения.
One Solution collect form web for “Генератор Python против функции обратного вызова”
То, что я имел в виду в своем комментарии, («уступка из рекурсивной функции звучит так, как будто она требует дополнительных для петель, чтобы передать результаты до вызывающего»), эта строка:
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 может исправить это (см. Этот параграф ). В то же время я не думаю, что это хорошая идея уступить из рекурсивных функций (по крайней мере, если они рекурсивно задерживаются), они просто плохо работают вместе.