我感兴趣的是这样的场景,我们有一些函数f,它是递归的,我们没有被提供源代码。
我想要一个函数记忆器: function ->函数,它接受f,并返回一个函数g,使得g=f(在给定相同参数的情况下,它们返回相同的值),当被调用时,它首先检查被调用的参数是否在它的‘缓存’(它以前计算过的结果的内存)中,如果是,则返回结果,否则它应该计算f,应该f使用一些参数调用自己,这等同于使用这些参数调用g,我希望f首先检查g的缓存是否包含这些参数,如果包含这些参数,则返回结果,否则...
在给定f的源代码的情况下,这(在Javascript中)很容易做到,我只是以一种显而易见的方式定义了memoize,并执行如下操作
let f = memoize((...args) => {/* source code of f */});
但这对我来说一点都不吸引(主要是因为我可能想要一个相同函数的记忆和非记忆版本,然后我必须编写相同的函数两次),如果我不知道如何实现f,就不会工作。
以防我问的不清楚,
我想要一个函数memoize,它接受如下函数
fact = n => n === 0 ? 1 : n * fact(n - 1);
并返回某个新函数g,使得所有n的事实(N)= g(n),并且例如当计算g(10)时,该函数存储在计算g(10)时计算的事实(0)、…、事实(10)的值,然后如果我请求例如g(7),则它在高速缓存中找到结果并将其返回给我。
我认为,从概念上讲,检测何时调用f是可能的,因为我有它的地址,也许我可以用一个新函数替换所有对f的调用,在这个新函数中,我计算f并存储结果,然后将值传递到它通常会去的地方。但我不知道如何做到这一点(这听起来很不愉快)。
发布于 2018-10-19 11:01:47
在我有限的经验中,我们确实可以访问JavaScript源代码。因此,我们可以尝试为memoized函数生成新的源代码。
// Redefine Function.prototype.bind
// to provide access to bound objects.
// https://stackoverflow.com/questions/7616461/generate-a-hash-from-string-in-javascript
var _bind = Function.prototype.apply.bind(Function.prototype.bind);
Object.defineProperty(Function.prototype, 'bind', {
value: function(obj) {
var boundFunction = _bind(this, arguments);
boundFunction.boundObject = obj;
return boundFunction;
}
});
// Assumes the parameters for the function,
// f, can be consistently mapped.
function memo(f){
if (!(f instanceof Function))
throw TypeError('Argument is not an instance of Function.');
// Generate random variable names
// to avoid conflicts with unknown
// source code
function randomKey(numBytes=8){
let ranges = [[48, 10], [65, 26], [97, 26]];
let key = '_';
for (let i=0; i<numBytes; i++){
let idx = Math.floor(Math.random() * ranges.length);
key += String.fromCharCode(ranges[idx][0] + Math.random() * ranges[idx][1]);
}
return key;
}
let fName = f.name;
let boundObject;
let fCode;
const nativeCodeStr = '(){[nativecode]}';
// Possible Proxy
try {
fCode = f.toString();
} catch(error){
if (error.constructor == TypeError){
if (Function(`return ${ fName }.toString()`)() != nativeCodeStr){
throw TypeError(`Possible Proxy detected: function has a name but no accessible source code. Consider memoizing the target function, ${ fName }.`);
} else {
throw TypeError(`Function has a name but no accessible source code. Applying toString() to its name, ${ fName }, returns '[native code]'.`);
}
} else {
throw Error('Unexpected error calling toString on the argument.');
}
}
if (!fName){
throw Error('Function name is falsy.');
// Bound functions
// Assumes we've monkey-patched
// Function.prototype.bind previously
} else if (fCode.replace(/^[^(]+|\s+/g, '') == nativeCodeStr){
if (/^bound /.test(fName)){
fName = fName.substr(6);
boundObject = f.boundObject;
// Bound functions return '[native code]' for
// their toString method call so get the code
// from the original function.
fCode = Function(`return ${ fName }.toString()`)();
} else {
throw Error("Cannot access source code, '[native code]' provided.");
}
}
const fNameRegex = new RegExp('(\\W)' + fName + '(\\W)', 'g');
const cacheName = randomKey();
const recursionName = randomKey();
const keyName = randomKey();
fCode = fCode.replace(/[^\(]+/,'')
.replace(fNameRegex, '$1' + recursionName + '$2')
.replace(/return/g, `return ${ cacheName }[${ keyName }] =`)
.replace(/{/, `{\n const ${ keyName } = Array.from(arguments);\n\n if (${ cacheName }[${ keyName }])\n return ${ cacheName }[${ keyName }];\n`);
const code = `function(){\nconst ${ cacheName } = {};\n\nfunction ${ recursionName + fCode }\n\nreturn ${ recursionName }.apply(${ recursionName }, arguments);}`;
let g = Function('"use strict";return ' + code)();
if (boundObject){
let h = (g).bind(boundObject);
h.toString = () => code;
return h;
} else {
return g;
}
} // End memo function
function fib(n) {
if (n <= 1) return 1;
return fib(n - 1) + fib(n - 2);
}
const h = fib.bind({a: 37});
const g = memo(h);
console.log(`g(100): ${ g(100) }`);
console.log(`g.boundObject:`, g.boundObject);
console.log(`g.toString():`, g.toString());
try{
memo(function(){});
} catch(e){
console.log('Caught error memoizing anonymous function.', e)
}
const p = new Proxy(fib, {
apply: function(target, that, args){
console.log('Proxied fib called.');
return target.apply(target, args);
}
});
console.log('Calling proxied fib.');
console.log(`p(2):`, p(2));
let memoP;
try {
memoP = memo(p);
} catch (e){
console.log('Caught error memoizing proxied function.', e)
}
https://stackoverflow.com/questions/52881589
复制相似问题