标签: memoization

我还没有看到一种既定的方法来记忆一个带有关键字参数的函数,即类型的东西

def f(*args, **kwargs)

因为通常一个memoizer有一个dict缓存给定输入参数集的结果,并且kwargs是一个dict因此不可用的.我在这里讨论后尝试过使用

(args, frozenset(kwargs.items()))

作为缓存的关键dict,但这仅在值为kwargshashable 时才有效.此外,正如下面的答案中所指出的那样,frozenset它不是有序的数据结构.因此,此解决方案可能更安全:

(args, tuple(sorted(kwargs.items())))

但它仍然无法应对不可清除的元素.我所看到的另一种方法是使用string的表示kwargs在缓存中的关键:

(args, str(sorted(kwargs.items())))

我看到的唯一缺点是散列可能非常长的字符串的开销.据我所知,结果应该是正确的.有人能发现后一种方法有什么问题吗？下面的答案之一指出,这假定了关键字参数值的函数__str__或__repr__函数的某些行为.这似乎是一个显示阻止.

还有另一种更成熟的实现备忘的方法,可以应对**kwargs和不可消除的论证价值吗？

不知道谷歌究竟要解决这个问题,所以我会直接发布到SO:

1. Haskell中的变量是不可变的
2. 纯函数应该为相同的参数产生相同的值

从这两点可以推断,如果你somePureFunc somevar1 somevar2在代码中调用两次,那么在第一次调用期间计算值是有意义的.结果值可以存储在某种巨型哈希表(或类似的东西)中,并在后续调用函数时查找.我有两个问题:

1. GHC实际上是否进行了这种优化？
2. 如果确实如此,那么重复计算实际上比查找结果更便宜的情况是什么？

谢谢.

我有一些任务需要解决,目前最重要的部分是使脚本尽可能节省时间.我试图优化的一个要素是其中一个函数中的memoization.

所以我的问题是:以下3-4种方法中哪一种是在Python中实现memoization的最有效/最快的方法？

我只提供了代码作为示例 - 如果其中一种方法更有效,但在我提到的情况下,请分享您所知道的内容.

解决方案1 ​​ - 使用外部范围的可变变量

此解决方案通常显示为示例memoization,但我不确定它的效率如何.我听说使用全局变量(在这种情况下,它是从外部变量而不是全局变量)效率较低.

def main():
    memo = {}
    def power_div(n):
        try:
            return memo[n]
        except (KeyError):
            memo[n] = (n ** 2) % 4  # example expression, should not matter
            return memo[n]
    # extensive usage of power_div() here

解决方案2 - 使用默认的可变参数

我发现在过去使用默认的可变参数从外部作用域传递变量,当Python首先在本地作用域中搜索变量,然后在全局作用域中,跳过非局部作用域(在本例中为范围内)功能main()).因为默认参数仅在定义函数时初始化,并且只能在内部函数内部访问,因此它可能更有效吗？

def main():
    def power_div(n, memo={}):
        try:
            return memo[n]
        except (KeyError):
            memo[n] = (n ** 2) % 4  # example expression, should not matter
            return memo[n]
    # extensive usage of power_div() …

在具有惰性语义的纯函数语言(例如Haskell)中,计算结果被记忆,因此对具有相同输入的函数的进一步评估不会重新计算该值,而是直接从memoized值的缓存中获取它.

我想知道这些记忆值是否会在某个时间点被回收？

1. 如果是这样,这意味着必须在以后重新计算已记忆的值,并且记忆的好处并非如此退出恕我直言.
2. 如果没有,那么好吧,这很容易缓存所有内容......但它是否意味着程序 - 如果运行足够长的时间 - 将总是消耗越来越多的内存？

想象一个程序执行密集的数值分析:例如使用二分法算法找到数十万个数学函数列表的根.

每次程序评估具有特定实数的数学函数时,结果都将被记忆.但是在算法期间,只有很小的概率才会出现完全相同的实数,导致内存泄漏(或者至少是非常糟糕的使用).

我的想法是,也许memoized值只是"范围"到程序中的某些东西(例如到当前的continuation,调用堆栈等),但我无法找到关于这个主题的实际内容.

我承认我没有深入研究Haskell编译器实现(懒惰？),但是,有人可以向我解释它在实践中是如何工作的吗？

编辑:好的,我从最初的几个答案中理解了我的错误:纯语义意味着参考透明度,这反过来并不意味着自动记忆,但只是保证它没有问题.

我认为网上的一些文章对此有误导性,因为从初学者的角度来看,参考透明度属性似乎很酷,因为它允许隐式记忆.

显然||=不行

def x?
  @x_query ||= expensive_way_to_calculate_x
end

因为如果它原来是false或nil,然后expensive_way_to_calculate_x将得到反复执行.

目前我知道的最好方法是将值放入Array:

def x?
  return @x_query.first if @x_query.is_a?(Array)
  @x_query = [expensive_way_to_calculate_x]
  @x_query.first
end

有更传统或更有效的方法吗？

更新我意识到我想要记忆nil除了false- 这一直回到https://rails.lighthouseapp.com/projects/8994/tickets/1830-railscachefetch-does-not-work-with-false-boolean - 缓存价值 - 我向安德鲁马歇尔道歉,他给出了一个完全正确的答案.

通常我需要向ADT添加字段,只记忆一些冗余信息.但我还没有完全弄清楚如何做得好而有效.

显示问题的最佳方法是举个例子.假设我们正在使用无类型的lambda术语:

type VSym = String

data Lambda = Var VSym 
            | App Lambda Lambda
            | Abs VSym Lambda

有时我们需要计算一个术语的自由变量集:

fv :: Lambda -> Set VSym
fv (Var v)    = Set.singleton v
fv (App s t)  = (fv s) `Set.union` (fv t)
fv (Abs v t)  = v `Set.delete` (fv t)

很快我们意识到重复计算fv是我们应用的瓶颈.我们想以某种方式将它添加到数据类型中.喜欢:

data Lambda1 = Var (Set VSym) VSym
             | App (Set VSym) Lambda Lambda
             | Abs (Set VSym) VSym Lambda

但它使定义相当丑陋.几乎(Set VSym)比其他所有人都占用更多的空间.而且,它在所有使用的函数中打破了模式匹配Lambda.更糟糕的是,如果我们后来决定添加一些其他的memoizing字段,我们将不得不再次重写所有模式.

如何设计一个通用的解决方案,允许轻松,不引人注意地添加这些记忆字段？ …

我应该用吗？ if defined?

 return @current_user_session if defined?(@current_user_session)
 @current_user_session = UserSession.find

要么 ||=

@current_user_session ||= UserSession.find

我注意到if defined?最近使用的方法越来越多.一个人对另一个人有什么好处吗？就个人而言,我更喜欢||=可读性.我也认为Rails可能有一个memoize透明地提供这种行为的宏.是这样的吗？

我在Haskell中编写了0-1背包问题.到目前为止,我对于懒惰和普遍性水平感到自豪.

我首先提供了创建和处理惰性2d矩阵的函数.

mkList f = map f [0..]
mkTable f = mkList (\i -> mkList (\j -> f i j))

tableIndex table i j = table !! i !! j

然后我为一个给定的背包问题制作一个特定的表格

knapsackTable = mkTable f
    where f 0 _ = 0
          f _ 0 = 0
          f i j | ws!!i > j = leaveI
                | otherwise = max takeI leaveI
              where takeI  = tableIndex knapsackTable (i-1) (j-(ws!!i)) + vs!!i
                    leaveI = tableIndex knapsackTable (i-1) j

-- weight …

我正在尝试记住以下功能:

gridwalk x y
    | x == 0 = 1
    | y == 0 = 1
    | otherwise = (gridwalk (x - 1) y) + (gridwalk x (y - 1))

看着这个我想出了以下解决方案:

gw :: (Int -> Int -> Int) -> Int -> Int -> Int
gw f x y
    | x == 0 = 1
    | y == 0 = 1
    | otherwise = (f (x - 1) y) + (f x (y - 1))

gwlist :: [Int]
gwlist …

在以函数式语言编写memoization和continuation传递样式(CPS)函数的示例时,我最终使用了Fibonacci示例.然而,Fibonacci并没有真正受益于CPS,因为循环仍然必须经常以指数方式运行,而memoization它的第一次只有O(n)而后一次只有O(1).

结合CPS和记忆化既有的斐波那契数略有好处,但有没有解决,其中CPS是防止你用尽堆栈的最佳方式的例子,并提高了性能并在记忆化是不是一个解决方案？

或者:是否有何时选择其中一个或两者的指南？