如何优化递归算法以使其不重复? [英] How to optimize a recursive algorithm to not repeat itself?

问题描述

在Python的标准库中发现difflib.SequenceMatcher类不适合我的需求后，编写了一个通用的"diff" -ing模块来解决问题空间.在经过几个月的思考后，递归算法似乎正在按需要搜索更多内容，方法是按照一个单独的搜索线程"可能也已经检查过的顺序重新搜索相同的区域.

After finding the difflib.SequenceMatcher class in Python's standard library to be unsuitable for my needs, a generic "diff"-ing module was written to solve a problem space. After having several months to think more about what it is doing, the recursive algorithm appears to be searching more than in needs to by re-searching the same areas in a sequence that a separate "search thread" may have also examined.

diff模块的目的是计算一对序列(列表，元组，字符串，字节，字节数组等)之间的差异和相似性.初始版本比代码的当前形式慢很多，速度提高了十倍.有没有人建议在递归算法中实现修剪搜索空间的方法以提高性能?

The purpose of the diff module is to compute the difference and similarities between a pair of sequences (list, tuple, string, bytes, bytearray, et cetera). The initial version was much slower than the code's current form, having seen a speed increase by a factor of ten. Does anyone have a suggestion for implementing a method of pruning search spaces in recursive algorithms to improve performance?

推荐答案

您正在寻找的技术称为记忆化.

The technique you are looking for is called memoization.

这篇关于如何优化递归算法以使其不重复?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！