如何编写通用的记忆功能? [英] How do I write a generic memoize function?
问题描述
我正在编写一个函数来查找三角形数和自然的写法是递归的:
I'm writing a function to find triangle numbers and the natural way to write it is recursively:
function triangle (x)
if x == 0 then return 0 end
return x+triangle(x-1)
end
但尝试计算前 100,000 个三角形数失败,一段时间后堆栈溢出.这是 memoize 的理想函数,但我想要一个解决方案,可以记住我传递给它的任何函数.
But attempting to calculate the first 100,000 triangle numbers fails with a stack overflow after a while. This is an ideal function to memoize, but I want a solution that will memoize any function I pass to it.
推荐答案
我敢打赌这样的事情应该适用于 Lua 中的可变参数列表:
I bet something like this should work with variable argument lists in Lua:
local function varg_tostring(...)
local s = select(1, ...)
for n = 2, select('#', ...) do
s = s..","..select(n,...)
end
return s
end
local function memoize(f)
local cache = {}
return function (...)
local al = varg_tostring(...)
if cache[al] then
return cache[al]
else
local y = f(...)
cache[al] = y
return y
end
end
end
您可能还可以使用带有 __tostring 的元表做一些聪明的事情,以便可以使用 tostring() 转换参数列表.哦,可能性.
You could probably also do something clever with a metatables with __tostring so that the argument list could just be converted with a tostring(). Oh the possibilities.
这篇关于如何编写通用的记忆功能?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!