Как сделать запоминание или запоминание в Julia 1.0 - PullRequest
Новая
       14

Как сделать запоминание или запоминание в Julia 1.0

0 голосов
/ 28 августа 2018

Я пытался сделать запоминание в Джулии для функции Фибоначчи. Это то, что я придумал.

Оригинальный неизмененный код (для целей контроля) 

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

Есть ли другие способы сделать это, о которых я не знаю?

Ответы [ 2 ]

0 голосов
/ 29 августа 2018

Самый простой способ сделать это - использовать get!

const fibmem = Dict{Int,Int}()
function fib(n)
    get!(fibmem, n) do
        n < 3 ? 1 : fib(n-1) + fib(n-2)
    end
end

Обратите внимание на спецификатор const снаружи fibmem. Это устраняет необходимость в global и ускоряет выполнение кода, поскольку позволяет компилятору использовать вывод типов в fib.

0 голосов
/ 28 августа 2018

Как отмечено в комментариях, пакет Memoize.jl , безусловно, является самым простым вариантом. Это требует, чтобы вы отметили метод во время определения.

Однако, безусловно, самый мощный подход заключается в использовании 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 выполняется вместо исходного определения функции
    • Мы используем это, чтобы проверить, существует ли arg в словаре метаданных.
    • recurse(...) говорит кассете вызвать функцию, но игнорирует верхний уровень overload.

Теперь мы можем запустить функцию с памяткой: 

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

Что еще круче, так это то, что мы можем взять существующую функцию, которая вызывает fib, и запомнить вызов fib внутри этой функции: 

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

(Кассета все еще довольно сложна для компилятора, поэтому запуск в первый раз может занять некоторое время, но после этого будет быстрым).

...