algorithm - 确定函数记忆的好处的算法

Question

问题

假设我有一些只有引用透明函数的编程语言。众所周知，这些函数中的任何一个都可以被记忆。然而，记忆函数在时间或空间方面并不总是值得的。决定自动记忆函数是否会节省空间或时间的算法是什么？

例子

# likely to benefit from memoization
def fact(n):
    return 1 if n == 0 else n * fact(n - 1)

# unlikely to benefit from memoization
def inc(x):
    return x + 1

我的用例

我有一个 Lisp 解释器作为副项目，它将自身限制为 Lisp 的纯功能子集。我想记忆函数，但我不想盲目地决定应该记忆什么，不应该记忆什么。

附加信息

该解决方案可以使用静态代码分析运行，也可以在程序的生命周期内运行，或者可以在程序的多次运行中运行。

解决方案不一定是完美的；它可能只是一种启发式方法，在很多时候都是正确的。