我怎么写一般memoize功能？
https://stackoverflow.com/questions/129877
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian解决方案
我打赌这样的事情应该适用于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（）转换。哦，可能性。
其他提示
Mathematica有一种特别灵活的记忆方式，依赖哈希和函数调用使用相同语法的事实：
triangle[0] = 0;
triangle[x_] := triangle[x] = x + triangle[x-1]
就是这样。它的工作原理是因为模式匹配函数调用的规则总是在更一般的定义之前使用更具体的定义。
当然，正如已经指出的那样，这个例子有一个封闭形式的解决方案： triangle [x_]：= x *（x + 1）/ 2 。 Fibonacci数字是添加memoization如何大幅加速的典型例子：
fib[0] = 1;
fib[1] = 1;
fib[n_] := fib[n] = fib[n-1] + fib[n-2]
虽然它也有一个封闭形式的等价物，尽管比较麻烦： http://mathworld.wolfram。 COM / FibonacciNumber.html
我不同意建议这不适合进行记忆的人，因为你可以“只使用一个循环”。记忆点是任何重复函数调用都是O（1）时间。这比O（n）要好很多。实际上，您甚至可以编写一个场景，其中memoized实现的性能优于封闭式实现！
你也问你原来的问题是错误的问题;）
对于这种情况，这是一种更好的方式：
triangle（n）= n *（n - 1）/ 2
此外，假设公式没有这样一个简洁的解决方案，那么备忘录在这里仍然是一个糟糕的方法。在这种情况下，你最好只编写一个简单的循环。有关更全面的讨论，请参见此答案。
在C＃3.0中 - 对于递归函数，您可以执行以下操作：
public static class Helpers
{
public static Func<A, R> Memoize<A, R>(this Func<A, Func<A,R>, R> f)
{
var map = new Dictionary<A, R>();
Func<A, R> self = null;
self = (a) =>
{
R value;
if (map.TryGetValue(a, out value))
return value;
value = f(a, self);
map.Add(a, value);
return value;
};
return self;
}
}
然后你可以创建一个这样的memoized Fibonacci函数：
var memoized_fib = Helpers.Memoize<int, int>((n,fib) => n > 1 ? fib(n - 1) + fib(n - 2) : n);
Console.WriteLine(memoized_fib(40));
在Scala中（未经测试）：
def memoize[A, B](f: (A)=>B) = {
var cache = Map[A, B]()
{ x: A =>
if (cache contains x) cache(x) else {
val back = f(x)
cache += (x -> back)
back
}
}
}
请注意，这仅适用于arity 1的功能，但通过currying可以使其工作。更微妙的问题是任何函数 f 的 memoize（f）！= memoize（f）。解决这个问题的一个非常偷偷摸摸的方法就是如下：
val correctMem = memoize(memoize _)
我不认为这会编译，但它确实说明了这个想法。
更新:评论者已经指出，性记忆化是一个很好的方法来优化递归。诚然，我没有考虑这之前，因为我一般工作语文(C#)在广义的性记忆化并不是那么容易建立。采取后下，粮食盐中心。
我认为 卢克有可能拥有的最适当的解决方案 这个问题，但性记忆化不是一般的解决任何问题的堆溢出。
堆的溢出通常引起递归去深度超过该平台可以处理。语言有时支持"尾递归"，它重新采用目前的呼吁，而不是创建一个新的环境递归的呼吁。但是，很多主流的语言/平台都不支持这一点。C#没有固有的支持结尾递归为例。64位版本的.净抖动可以申请它作为一个优化的IL水平，这是所有但是无用的，如果你需要支助的32位的平台。
如果你的语言不支持尾递归，您最好的选择，避免堆溢出是任转换到一个明确的循环(更优雅，但有时需要)，或者找到一个非迭代的算法，如卢克提供对这个问题。
function memoize (f)
local cache = {}
return function (x)
if cache[x] then
return cache[x]
else
local y = f(x)
cache[x] = y
return y
end
end
end
triangle = memoize(triangle);
请注意，为避免堆栈溢出，仍需要三角形播种。
这里的东西可以在不将参数转换为字符串的情况下工作。
唯一需要注意的是它无法处理nil参数。但是接受的解决方案无法区分值 nil 和字符串＆quot; nil“，所以这可能没问题。
local function m(f)
local t = { }
local function mf(x, ...) -- memoized f
assert(x ~= nil, 'nil passed to memoized function')
if select('#', ...) > 0 then
t[x] = t[x] or m(function(...) return f(x, ...) end)
return t[x](...)
else
t[x] = t[x] or f(x)
assert(t[x] ~= nil, 'memoized function returns nil')
return t[x]
end
end
return mf
end
我的灵感来自这个问题的执行(又一)灵活memoize功能在Lua。
https://github.com/kikito/memoize.lua
主要优点：
- 接受一个变量的参数数目
- 不使用tostring;相反，它组织的高速缓存在一棵树的结构，使用的参数穿越它。
- 工作的现有职能返回 多个值.
贴这里的代码作为参考：
local globalCache = {}
local function getFromCache(cache, args)
local node = cache
for i=1, #args do
if not node.children then return {} end
node = node.children[args[i]]
if not node then return {} end
end
return node.results
end
local function insertInCache(cache, args, results)
local arg
local node = cache
for i=1, #args do
arg = args[i]
node.children = node.children or {}
node.children[arg] = node.children[arg] or {}
node = node.children[arg]
end
node.results = results
end
-- public function
local function memoize(f)
globalCache[f] = { results = {} }
return function (...)
local results = getFromCache( globalCache[f], {...} )
if #results == 0 then
results = { f(...) }
insertInCache(globalCache[f], {...}, results)
end
return unpack(results)
end
end
return memoize
这是一个通用的C＃3.0实现，如果有帮助的话：
public static class Memoization
{
public static Func<T, TResult> Memoize<T, TResult>(this Func<T, TResult> function)
{
var cache = new Dictionary<T, TResult>();
var nullCache = default(TResult);
var isNullCacheSet = false;
return parameter =>
{
TResult value;
if (parameter == null && isNullCacheSet)
{
return nullCache;
}
if (parameter == null)
{
nullCache = function(parameter);
isNullCacheSet = true;
return nullCache;
}
if (cache.TryGetValue(parameter, out value))
{
return value;
}
value = function(parameter);
cache.Add(parameter, value);
return value;
};
}
}
（引自法国博客文章）
在发布不同语言的备忘录的过程中，我想用非语言改变的C ++示例回复@ onebyone.livejournal.com。
首先，单个arg函数的memoizer：
template <class Result, class Arg, class ResultStore = std::map<Arg, Result> >
class memoizer1{
public:
template <class F>
const Result& operator()(F f, const Arg& a){
typename ResultStore::const_iterator it = memo_.find(a);
if(it == memo_.end()) {
it = memo_.insert(make_pair(a, f(a))).first;
}
return it->second;
}
private:
ResultStore memo_;
};
只需创建一个memoizer实例，输入你的函数和参数。请确保不要在两个不同的函数之间共享相同的备忘录（但您可以在同一函数的不同实现之间共享它）。
接下来，一个驱动程序功能，以及一个实现。只有驱动功能需要公开 int fib（int）; //司机 int fib_（int）; //实施
实现：
int fib_(int n){
++total_ops;
if(n == 0 || n == 1)
return 1;
else
return fib(n-1) + fib(n-2);
}
和司机，要记住
int fib(int n) {
static memoizer1<int,int> memo;
return memo(fib_, n);
}
在codepad.org上永久链接显示输出。测量呼叫次数以验证正确性。 （在这里插入单元测试......）
这只会记住一个输入功能。推广多个参数或不同的参数作为读者的练习。
在Perl中，通用记忆很容易获得。 Memoize模块是perl核心的一部分，具有高可靠性，灵活性和易用性。
该手册的示例：
# This is the documentation for Memoize 1.01
use Memoize;
memoize('slow_function');
slow_function(arguments); # Is faster than it was before
您可以在运行时添加，删除和自定义函数的memoization！您可以为自定义纪念计算提供回调。
Memoize.pm甚至还有使memento缓存持久化的工具，因此不需要在每次调用程序时重新填充它！
有关通用Scala解决方案，请参阅此博客文章，最多4个参数。
扩展这个想法，也可以使用两个输入参数来记忆函数：
function memoize2 (f)
local cache = {}
return function (x, y)
if cache[x..','..y] then
return cache[x..','..y]
else
local z = f(x,y)
cache[x..','..y] = z
return z
end
end
end
请注意，参数顺序在缓存算法中很重要，因此如果参数顺序在要记忆的函数中无关紧要，那么在检查缓存之前对参数进行排序会增加获得缓存命中的几率。
但重要的是要注意某些功能无法获得有利可图的记忆。我写了 memoize2 来查看是否递归欧几里德算法以查找可以加快最大的除数。
function gcd (a, b)
if b == 0 then return a end
return gcd(b, a%b)
end
事实证明， gcd 对备忘录的反应不佳。它的计算远比缓存算法便宜。对于大数字，它会很快终止。过了一会儿，缓存变得非常大。这个算法可能会尽可能快。
没有必要进行递归。第n个三角形数是n（n-1）/ 2，所以......
public int triangle(final int n){
return n * (n - 1) / 2;
}
请不要递言。要么使用x *（x + 1）/ 2公式，要么只是迭代值并随时记忆。
int[] memo = new int[n+1];
int sum = 0;
for(int i = 0; i <= n; ++i)
{
sum+=i;
memo[i] = sum;
}
return memo[n];
