如何在Julia 1.0中进行记忆或记忆 [英] How to do memoization or memoisation in Julia 1.0

问题描述

我一直试图用朱莉娅(Julia)的斐波那契函数进行记忆.这就是我想出的.

I have been trying to do memorisation in Julia for the Fibonacci function. This is what I came up with.

未经修改的原始代码(出于控制目的)

The original unmodified code (for control purposes)

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

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

Are there other ways of doing so that I am not aware of?

推荐答案

正如评论中指出的， Memoize.jl 软件包当然是最简单的选择.这要求您在定义时标记该方法.

As pointed out in the comments, the Memoize.jl package is certainly the easiest option. This requires you to mark the method at definition time.

但是，到目前为止，最强大的方法是使用 Cassette.jl ，您可以将备忘录添加到现有功能中，例如

By far the most powerful approach, however, is to use Cassette.jl, which lets you add memoization to pre-existing functions, e.g.

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

有关正在发生的事情的一些描述:

A little bit of a description of what is going on:

• MemoizeCtx是我们正在定义的盒式磁带上下文"
运行
• overdub 而不是运行原始功能定义
  • 我们用它来检查元数据字典中是否存在arg.
  • recurse(...)告诉Cassette调用该函数，但忽略顶级overload.
  • MemoizeCtx is the Cassette "context" which we are defining
  • overdub is run instead of the original function definition
    • We use this to check if the arg exists in the metadata dictionary.
    • recurse(...) tells Cassette to call the function, but ignore the top level overload.

    现在，我们可以通过记忆功能运行该功能:

    Now we can run the function with memoization:

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

    现在更酷的是，我们可以采用一个调用fib的现有函数，并记住对该函数的fib 内部调用:

    Now what's even cooler is that we can take an existing function which calls fib, and memoize the call to fib inside that function:

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

    (盒式磁带在编译器上仍然相当困难，因此第一次运行可能需要一段时间，但之后会很快).

    (Cassette is still pretty hard on the compiler, so this may take a while to run the first time, but will be fast after that).

    这篇关于如何在Julia 1.0中进行记忆或记忆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！