如何優化遞歸算法不重複自身？

Question

在Python的標準庫中發現difflib.SequenceMatcher類不適合我的需求後，編寫了一個通用「差異」模塊來解決問題空間。經過幾個月的時間思考更多關於它在做什麼之後，遞歸算法似乎在搜索更多的需求，通過重新搜索一個單獨的「搜索線程」也可能檢查過的序列中的相同區域。

diff模塊的目的是計算一對序列（列表，元組，字符串，字節，bytearray等）之間的差異和相似性。最初的版本比代碼的當前版本慢得多，看到速度增加了十倍。有沒有人有建議實施一種修剪搜索空間的遞歸算法來提高性能？

Answer 1

您正在尋找的技術被稱爲memoization。

Answer 2

如果你有任何昂貴的方法，你可能會調用多次使用相同的參數，那麼你可以緩存方法的結果，使用參數作爲一個關鍵。