如何在 Julia 1.0 中进行记忆化或记忆化

我一直在尝试用 Julia 来记忆斐波那契函数。这就是我想出来的。

原始未修改的代码（用于控制目的）

function fib(x)
    if x < 3
        return 1
    else
        return fib(x-2) + fib(x-1)
    end
end

这是我的第一次尝试

memory=Dict()

function memfib(x)
    global memory
    if haskey(memory,x)
        return memory[x]
    else
        if x < 3
            return memory[x] = 1
        else
            return memory[x] = memfib(x-2) + memfib(x-1)
        end
    end
end

我的第二次尝试

memory=Dict()

function membetafib(x)
    global memory
    return haskey(memory,x) ? memory[x] : x < 3 ? memory[x]=1 : memory[x] = membetafib(x-2) + membetafib(x-1)
end

我的第三次尝试

memory=Dict()

function memgammafib!(memory,x)
    return haskey(memory,x) ? memory[x] : x < 3 ? memory[x]=1 : memory[x] = memgammafib!(memory,x-2) + memgammafib!(memory,x-1)
end

还有其他我不知道的方法吗？

正如评论中指出的那样，记忆化.jl https://github.com/simonster/Memoize.jl包当然是最简单的选择。这需要您在定义时标记该方法。

然而，迄今为止最有效的方法是使用卡带.jl https://github.com/jrevels/Cassette.jl，它允许您将记忆添加到预先存在的函数中，例如

fib(x) = x < 3 ? 1 : fib(x-2) + fib(x-1)

using Cassette
Cassette.@context MemoizeCtx
function Cassette.overdub(ctx::MemoizeCtx, ::typeof(fib), x)
       get(ctx.metadata, x) do
           result = recurse(ctx, fib, x)
           ctx.metadata[x] = result
           return result
       end
   end

对正在发生的事情进行一些描述：

• MemoizeCtx是我们定义的盒式磁带“上下文”
• overdub https://jrevels.github.io/Cassette.jl/latest/api.html#Cassette.overdub is run instead of the original function definition
  • 我们用它来检查 arg 是否存在于元数据字典中。
  • recurse(...)告诉 Cassette 调用该函数，但忽略顶层overload.

现在我们可以通过记忆来运行该函数：

Cassette.overdub(MemoizeCtx(metadata=Dict{Int,Int}()), fib, 80)

现在更酷的是我们可以使用一个现有的函数来调用fib，并记住对的调用fib inside该函数：

function foo()
    println("calling fib")
    @show fib(80)
    println("done.")
end
Cassette.overdub(MemoizeCtx(metadata=Dict{Int,Int}()), foo)

（卡带对编译器来说仍然相当困难，因此第一次运行可能需要一段时间，但之后会很快）。