Использование кеширования вместо запоминания для ускорения функции - PullRequest
Новая
       4

Использование кеширования вместо запоминания для ускорения функции

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

Несмотря на то, что запоминание функции является хорошей идеей, она может вызвать сбой программы, поскольку программе может не хватить памяти.

Следовательно, это НЕ БЕЗОПАСНЫЙ ВАРИАНТ для использования в производственной программе.

Вместо этого я разработал кеширование с фиксированными слотами памяти ниже с мягким и жестким ограничением. Когда количество слотов в кэш-памяти превышает жесткое ограничение, будет удалено наименьшее количество используемых слотов, пока количество слотов не уменьшится до мягкого предела. 

struct cacheType
    softlimit::Int
    hardlimit::Int
    memory::Dict{Any,Any}
    freq::Dict{Any,Int}
    cacheType(soft::Int,hard::Int) = new(soft,hard,Dict(),Dict())
end

function tidycache!(c::cacheType)
    memory_slots=length(c.memory)
    if memory_slots > c.hardlimit
        num_to_delete = memory_slots - c.softlimit
        # Now sort the freq dictionary into array of key => AccessFrequency
        # where the first few items have the lowest AccessFrequency
        for item in sort(collect(c.freq),by = x -> x[2])[1:num_to_delete]
            delete!(c.freq, item[1])
            delete!(c.memory, item[1])
        end
    end
end

# Fibonacci function  
function cachefib!(cache::cacheType,x)
    if haskey(cache.memory,x)
        # Increment the number of times this key has been accessed
        cache.freq[x] += 1
        return cache.memory[x]
    else
        # perform housekeeping and remove cache entries if over the hardlimit
        tidycache!(cache)
        if x < 3
            cache.freq[x] = 1
            return cache.memory[x] = 1
        else
            result = cachefib!(cache,x-2) + cachefib!(cache,x-1)
            cache.freq[x] = 1
            cache.memory[x] = result
            return result
        end
    end
end

c = cacheType(3,4)
cachefib!(c,3)
cachefib!(c,4)
cachefib!(c,5)
cachefib!(c,6)
cachefib!(c,4)
println("c.memory is ",c.memory)
println("c.freq is ",c.freq)

Я думаю, что это было бы наиболее полезно в производственной среде, чем просто использование запоминания без ограничений потребления памяти, что может привести к сбою программы.

На языке Python они имеют

@functools.lru_cache (maxsize = 128, напечатано = False)

Декоратор, чтобы обернуть функцию запоминающимся вызовом, который сохраняет до максимума самые последние вызовы. Это может сэкономить время, когда дорогая или связанная с вводом / выводом функция периодически вызывается с одинаковыми аргументами.

Поскольку для кэширования результатов используется словарь, позиционные и ключевые аргументы функции должны быть хэшируемыми.

Есть ли эквивалент в языке Юлии?

1 Ответ

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

Существует LRUCache.jl , который обеспечивает тип LRU, который в основном действует как Dict. К сожалению, это не похоже на работу с пакетом Memoize.jl, но вы можете использовать мой ответ на ваш другой вопрос : 

using LRUCache

const fibmem = LRU{Int,Int}(3) # store only 3 values
function fib(n)
    get!(fibmem, n) do
        n < 3 ? 1 : fib(n-1) + fib(n-2)
    end
end
...