How can you use memoized functions in Roblox Lua?
I was really interested in this question Linked Arrays. According to that question, linked arrays make performance better. The asker linked what intrigued them to the topic. It was a Dev Forum post about Basics of Optimization by a user known as BlueTalsem. One of his ways of optimizing was memoizing expensive functions. Link here. I assumed that expensive functions are functions that make performance worse or take too much memory. I got interested. I found this git-hub page.
This is what I understood:
Memoized functions gets the results of a function. It's parameter is the function it gets the results of that argument. It has an optional argument which is its cashe. This is the place where the memoized function is stored. If not, it will default to its own table.
Memoized functions improve performance for memory. To get that memory back, you just simply make the memoized function nil.
When I was reading, I noticed this
local sum = function(...)
local result = 0
local params = { ... }
for i = 1, #params do
result = result + params[i]
end
return result
end
local memoized_sum = memoize(sum)
print(memoized_sum()) -- 0
print(memoized_sum(1)) -- 1
print(memoized_sum(1, 2)) -- 3
print(memoized_sum(3, 1)) -- 4
memoized_sum = nil
I have added the memoized_sum = nil to retrieve the memory back
The git-hub page said that the internal cache structure would be like this:
{
results = { 0 },
children = {
[1] = {
results = { 1 },
children = {
[2] = {
results = { 3 },
}
}
}
[3] = {
children = {
[1] = {
results = { 4 },
}
}
}
}
}
However, the problem is that there is no such function called memoize(). So, what can I do to make memoized functions and if I have misunderstood memoized functions or I still need to know more, please tell me by using answers
Thank you!
.
0
0
1 answer
Memoization, at its simplest, is storing the results of an expensive function in a memory cache and returning the cached result when the same inputs occur again. If you wanted to make a memoize function, all you would need to do is pass the function, the parameter, and the result into a memory cache (hint: dictionary/table) and index that value when the same input is used)
local memoryCache = {}
function memoize(func, ...)
local params = {...}
local index = {}
local funcCached = false
for i = 1, #memoryCache do -- finds the function
if memoryCache[i][1] = func then -- function
index = memoryCache[i]
funcCached = true
for k = 2, #index do -- finds the parameters
if index[k][1] = params then --parameters
return index[k][2] --result
end
end
end
end
local result = func(params)
if not funcCached then -- caches the function
local numIndex = #memoryCache + 1
memoryCache[numIndex] = {}
memoryCache[numIndex][1] = func
memoryCache[numIndex][2] = {}
memoryCache[numIndex][2][1] = params
memoryCache[numIndex][2][2] = result
else -- if the function is already cached, cache parameters
local numIndex2 = #index + 1
index[numIndex2] = {}
index[numIndex2][1] = params
index[numIndex2][2] = result
end
return result
end
--NOTE: This may not work. I cannot test it at the moment, but you get the idea and can do the rest yourself. Needs more checks most likely
This function basically takes in another function, checks if it has been cached already. If it is not cached, it adds the function to the memory cache.