Memoize函数传递函数和returns函数JavaScript

Question

我在使用此功能时遇到多个问题。这是数据结构和算法 class 的附加问题的一部分，我在这个问题上投入了很多时间，我真的很想让它工作并了解发生了什么。

有一个主要问题，引起了几个小问题...这个问题的名称是JavaScript。我们以前从未在 JavaScript 中编程过，但出于某种原因我们不得不使用它。

函数必须通过测试（这个和斐波那契），其结构如下：

var fn = (n) => 2 * n
var m_fn = memoize(fn)
expect(m_fn(18)).to.equal(fn(18))

所以我必须将我想要记忆的函数作为记忆函数的参数传递，并且记忆函数必须 return 一个函数。我不允许以任何其他方式这样做。

我阅读了所有内容并研究了 memoize 函数，但是所有的实现都采用了不同的方法。

基本上，我明白我必须做什么，但我不太明白怎么做。我知道 memoize 函数应该做什么，但我不明白如何使用我的 memoize 函数调整原始函数。这是我有的，所以 far/what 我没有：

我知道这是错误的。但我想我错过了一些重要的东西。我应该 return 一个函数，但我正在 returning 值...

测试中写了var m_fn = memoize(fn)，所以memoize函数通过fn，然后return是一个新函数，但是在我的memoize中，我是return正在计算 fn(n) 的值，所以我做错了什么...

/**
* Creates a memoized version of the function fn. It is assumed that fn is a referentially transparent
* function.
* @param {function} fn Some referentially transparent function that takes a basic datatype (i.e. number / string)
* @returns {function} A new function that is the memoized version of fn. It never calculates the result of
* a function twice.
*/
memoize: (fn) => { //here we enter the function that we want to memoize
 var memory = []; //we need to create an array to hold the previously calculated values, length n (parameter of fn)

 if(this.n > memory.length){ //Check to see if this particular value is in the array already.  
   return memory[this.n]; //How do I access the integer parameter that was passed through fn though? Is this correct?
 } else{ // if not, we want to save it and return it
   var result = fn(this.n);
   memory.push(result);
   return result;
 }

}

Answer 1

查看您的代码和代码内注释并假设我的解释正确，您真的很接近解决方案。正如您在问题中所说，您需要 return 一个函数 return 值而不是 return 值。

解释见评论：

function memoize(f) {
  // An array in which to remember objects with the input arg and result 
  var memory = [];
  
  // This is the function that will use that array; this is the
  // return value of memoize
  return function(arg) {
    // This code runs when the function returned by memoize is called
    // It's *here* that we want to process the argument, check the `memory`
    // array, call `f` if necessary, etc.
    var entry;
    
    // See if we have a previously-saved result for `arg`
    var entry = memory.find(entry => entry.arg === arg);
    if (!entry) {
      // No -- call `fn`, remember the `arg` and result in an object
      // we store in memory``
      entry = {arg, result: f(arg)};
      memory.push(entry);
    }
    
    // We have it (now), return the result
    return entry.result;
  };
}
function fn(arg) {
  console.log("fn called with " + arg);
  return 2 * arg;
}
var m_fn = memoize(fn);
console.log(m_fn(18));
console.log(m_fn(18));
console.log(m_fn(20));
console.log(m_fn(20));

注意：您的代码中有一个箭头函数，所以我认为可以使用上面的 ES2015 功能。但是，实际上并没有太多，只是传递给 memory.find 的箭头函数，Array#find 将可用的假设，以及用于创建入口对象的语法（在 ES5 中我们需要 entry = {arg: arg, result: f(arg)} 代替）。

请注意，如果我们可以假设 arg 将是一个字符串或数字或其他可以可靠地转换为字符串的值，我们可以使用对象而不是数组来存储数据。

实际上，鉴于这是 ES2015，我们可以使用 Map:

function memoize(f) {
  // An Map in which to remember objects with the input arg and result 
  const memory = new Map();
  
  // This is the function that will use that array; this is the
  // return value of memoize
  return function(arg) {
    // This code runs when the function returned by memoize is called
    // It's *here* that we want to process the argument, check the `memory`
    // array, call `f` if necessary, etc.
    let result;
    
    // See if we have a previously-saved result for `arg`
    if (!memory.has(arg)) {
      // No -- call `fn`, remember the `arg` and result in an object
      // we store in memory``
      result = f(arg);
      memory.set(arg, result);
    } else {
      // Yes, get it
      result = memory.get(arg);
    }
    
    // We have it (now), return the result
    return result;
  };
}
function fn(arg) {
  console.log("fn called with " + arg);
  return 2 * arg;
}
var m_fn = memoize(fn);
console.log(m_fn(18));
console.log(m_fn(18));
console.log(m_fn(20));
console.log(m_fn(20));

请注意，在这两种情况下，我都将代码编写得很冗长以便于评论和易于理解。特别是 Map 的 ES2015 版本可以相当短很多。

Answer 2

的确，你需要return一个函数。

其次，数组不是 memory 的理想结构，因为在其中查找参数值需要线性时间。我建议为此使用 Map ，这是实现此类目的的理想选择。它具有 has()、get() 和 set() 方法，其中运行在接近恒定的时间内：

function memoize(fn) {
    var memory = new Map();
    return function(arg) {
        if (memory.has(arg)) {
            console.log('using memory');
            return memory.get(arg);
        } else {
            var result = fn(arg);
            memory.set(arg, result);
            return result;
        }
    };
}

var fn = (n) => 2 * n
var m_fn = memoize(fn)

console.log(fn(18));
console.log(m_fn(18));
console.log(m_fn(18)); // outputs also "using memory"

Answer 3

您可以使用 Map 作为内存。

var memoize = f => 
        (map => v => (!map.has(v) && map.set(v, f(v)), map.get(v)))(new Map),
    fn = (n) => 2 * n,
    m_fn = memoize(fn);

console.log(m_fn(18), fn(18));

Memoize函数传递函数和returns函数JavaScript

Memoize function passes function and returns function JavaScript

javascript

parameters

memoization