如何优化递归算法以避免重复？
在发现Python标准库中的difflib.SequenceMatcher类不太适合我的需求后，我写了一个通用的“差异”模块来解决这个问题。经过几个月的思考，我发现这个递归算法在搜索时似乎有些多余，因为它会重复搜索一些区域，而这些区域可能已经被其他“搜索线程”检查过了。
这个diff模块的目的是计算一对序列（比如列表、元组、字符串、字节、字节数组等等）之间的差异和相似之处。最初的版本速度比现在的版本慢得多，现在的速度提高了十倍。有没有人能给出建议，如何在递归算法中实现一种修剪搜索空间的方法，以提高性能呢？
2 个回答
0
如果你有一个比较耗时的方法，而且你可能会用相同的参数多次调用它，那么你可以把这个方法的结果存起来，使用这些参数作为一个“钥匙”。这样，下次再用相同的参数时，就可以直接拿出之前的结果，而不用再去计算一次。
6
你要找的这个技巧叫做记忆化。