Как оптимизировать рекурсивный алгоритм, чтобы не повторять себя?

После того, как класс difflib.SequenceMatcher в стандартной библиотеке Python был непригоден для моих нужд, для решения проблемного пространства был написан общий "diff" -инг-модуль. После нескольких месяцев, чтобы больше думать о том, что он делает, рекурсивный алгоритм, похоже, ищет больше, чем нужно, путем повторного поиска тех же областей в последовательности, что и отдельный "поток поиска" также может быть рассмотрен.

Цель модуля diff - вычислить разницу и сходство между парой последовательностей (list, tuple, string, bytes, bytearray и т.д.). Первоначальная версия была намного медленнее, чем текущая форма кода, увидев увеличение скорости в десять раз. Есть ли у кого-нибудь предложение по внедрению метода обрезки поисковых пространств в рекурсивных алгоритмах для повышения производительности?

Ответы

Ответ 1

Техника, которую вы ищете, называется memoization.

Ответ 2

Если у вас есть дорогой метод, который вы, вероятно, будете вызывать несколько раз с теми же параметрами, вы можете просто кэшировать результат метода, используя параметры в качестве ключа.